翻烙饼问题

问题

一堆大小不一的烙饼，每次只能翻转最上面的几个饼，通过几次翻转使小的烙饼在上面大的烙饼在下面，寻找翻转次数最少的方法

分析

这是一个排序问题，但是只能通过翻转实现。把一叠饼的顺序看成一个状态。每一次的翻转，可以看成一种状态引发出另一个状态，在不同地方翻转会生出不同的状态，不同状态继续翻转生成更多的状态，把初始状态看成根节点，这样会生成一棵无止境的树。寻找翻转次数最少的方法即寻找靠近根节点的状态为已经有序的节点。
为了减少查找的次数，要是能找到一个边界，超出这个边界的节点不用搜索就好了，也就是剪枝。
书中提供了两个边界：
1.上边界（至多可以翻几次使烙饼有序）

• 翻最大的饼，把最大的饼翻到最上面，然后翻到最下面（2次）
• 对剩余的饼重复上述操作
• 如果只有2张饼，至多翻1次可使饼有序
• 这样的话，翻的次数为2*(n-2)+1,n>=2

最后的最优解肯定是少于上边界的，
2.下边界（至少还要翻几次使现状态的烙饼有序）
如果现阶段的已经翻的次数+下边界>上边界的话，也不用考虑这条路径了，肯定不是最优解

思路

初始化最优解为边界1，遍历所有在界限内的状态，如果找到了比当前最优解好的路径，就更新最优解。采用深度优先遍历。

代码

因为我平时写的大多是javaScript，所以代码是javaScript实现的，可能和书上的有些出入。
需要存储的信息：

// 基本的信息
function Cake() {
    this.cake_arr = [];    // 原始顺序
    this.reverse_arr = []; // 翻转中的顺序
    this.swap_arr = [];    // 记录翻转的路径，从第几个到第几个饼进行翻转
    this.best_swap_arr = []; // 记录最优的路径
    this.max_swap = 0;       // 最多翻转次数
    this.search_times = 0;   // 搜索次数
}

两个边界：

// 上边界
// 之前分析的是2*n - 3，但是考虑到n为0，1，2的情况，放大一些也没关系
Cake.prototype.findUpperBound = function(arr) {
    return 2 * arr.length;
}
// 下边界
// 有序 == 数组相邻元素的值相邻
// 每次翻转至多增加一个相邻对
// 不相邻的对数即为翻转次数的下界
Cake.prototype.findLowerBound = function(arr) {
    var num = 0;
    for (var i = 1; i < arr.length; i++) {
        var d = arr[i] - arr[i - 1];
        if (d != 1 && d != -1) {
            num++;
        }
    };
    return num;
}

辅助的方法：

// 判断数组是否有序
Cake.prototype.isSorted = function (arr) {
    for (var i = 1; i < arr.length; i++) {
        if (arr[i] < arr[i - 1]) {
            return false;
        }
    };
    return true;
}
// 翻转数组
// begin: 为翻转部分的起始位置
// end为: 翻转部分的结束位置
Cake.prototype.reverse = function (arr,begin,end) {
    for (var i = begin, j = end; i < j; i++, j--) {
        var tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
}
// 打印结果信息
Cake.prototype.printResult = function () {
    console.log('搜索次数为:' + this.search_times + '次');
    console.log('交换次数为:' + this.max_swap + '次');
    console.log('交换次序为:');       
    for (var i = 0; i < this.max_swap; i++) {
        console.log(this.best_swap_arr[i]);
    };
}

核心的方法：

// 遍历所有的状态
Cake.prototype.search = function(step) {
    this.search_times++;
    // 边界退出条件
    if (step + this.findLowerBound(this.reverse_arr) > this.max_swap) return;
    // 找到一个解
    if (this.isSorted(this.reverse_arr)) {
        if (step < this.max_swap) {
            // 更新最优解
            this.max_swap = step;
            for (var i = 0; i < this.max_swap; i++) {
                this.best_swap_arr[i] = this.swap_arr[i];
            };
        }
        return;
    }
    // 深度遍历所有状态
    for (var i = 1; i < this.reverse_arr.length; i++) {
        this.reverse(this.reverse_arr,0,i);  // 翻转生成新的状态，开始遍历一棵树
        this.swap_arr[step] ="翻转第" + (0 + 1) + "个到第" + (i + 1) + "个饼";   //记录翻转的路径
        this.search(step + 1);  //向下遍历，深度优先遍历
        this.reverse(this.reverse_arr,0,i);  // 回到上级节点状态，方便遍历另一棵树
    };
}

// 入口函数
Cake.prototype.sort = function(arr) {
    // 初始化
    for (var i = 0; i < arr.length; i++) {
        this.reverse_arr[i] = arr[i];
        this.cake_arr[i] = arr[i]
    };
    this.max_swap = this.findUpperBound(arr);
    // 遍历找最优解
    this.search(0);
    // 输出最优的方法
    this.printResult();
}

扩展问题

1.可以把上面的一摞饼放头上，然后再处理其它饼，算法的改动？
可以把一摞饼放头上，意味着翻转的部分可以是这摞饼的任意一部分，翻转部分的起点不一定是首个元素了，遍历的时候，还得遍历不同首部，以包括所有的情况

for (var i = 1; i < this.reverse_arr.length; i++) {
    for (var j = 0; j < i; j++) {
        this.reverse(this.reverse_arr,j,i);  // 翻转生成新的状态，开始遍历一棵树
        this.swap_arr[step] ="翻转第" + (j + 1) + "个到第" + (i + 1) + "个饼";   //记录翻转的路径
        this.search(step + 1);  //向下遍历，深度优先遍历
        this.reverse(this.reverse_arr,j,i);  // 回到上级节点状态，方便遍历另一棵树
    }
};

2.饼的正反有序，算法的改动？
是否有序有变化，需要修改isSorted函数；而翻转的过程，饼的正反也变动了，需要修改reverse函数，而且翻转最上面的1个饼，也会使饼的状态变化，所以需要修改遍历的起始范围。
烙饼的格式：

{
    val: 12,   // 半径的序号
    0: false,  // true表示朝上的面的为正面，false表示为反面
}

是否有序：

Cake.prototype.isSorted = function (arr) {
    for (var i = 1; i < arr.length; i++) {
        if (arr[i]["val"] < arr[i - 1]["val"]) {
            return false;
        }
        if (arr[i][0] == false ) {
            return false;
        }
    };
    if (arr.length && arr[0][0] == false) {
        return false;
    }
    return true;
}

翻转函数：

Cake.prototype.reverse = function (arr,begin,end) {
    for (var i = begin, j = end; i < j; i++, j--) {
        var tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
    for (var i = begin; i <= end; i++) {
        arr[i][0] = !arr[i][0];
    }
}

遍历的上界：
每次把最大的饼翻上来，再翻一次使之反面朝上，再翻一次使之到底部（3次）
重复操作，必能完成翻饼的任务

Cake.prototype.findUpperBound = function(arr) {
    return 3 * arr.length;
}

遍历的起始位置：

for (var i = 0; i < this.reverse_arr.length; i++) {
	// ...
};

3.希望翻转的烙饼数最小？
遍历的时候不是找离根节点最近的点，更新最优解的条件变了，同时边界也变了，这里我取的上边界为(n*n+n)，下边界为(1.5n-0.5)，这个边界不是很理想，以致对[3,2,1,6,5,4,7,0]的序列程序搜索了6861032次，但是我没想到其它的边界条件

var sum = 0;
for (var i = 0; i < step; i++) {
    sum += this.swap_arr[i];
}
// 边界退出条件
if (sum + this.findLowerBound(this.reverse_arr) > this.max_swap) return;
// 找到一个解
if (this.isSorted(this.reverse_arr)) {
    if (sum < this.max_swap) {
        // 更新最优解
        this.max_swap = sum;
        this.step = step;
        for (var i = 0; i < step; i++) {
            this.best_swap_arr[i] = this.swap_arr[i];
        };
    }
    console.log(sum);
    return;
}

搜索函数加了一点改进：

// 深度遍历所有状态
for (var i = 1; i < this.reverse_arr.length; i++) {
    this.swap_arr[step] = i;   //记录翻转的路径
    if (step && this.swap_arr[step - 1] == i) continue;   // 不走一步，退一步，减少搜索的次数
    this.reverse(this.reverse_arr,0,i);  // 翻转生成新的状态，开始遍历一棵树
    this.search(step + 1);  //向下遍历，深度优先遍历
    this.reverse(this.reverse_arr,0,i);  // 回到上级节点状态，方便遍历另一棵树
};

总结

翻烙饼的问题就这样了，下次再见了