编程之美《编程之美》读书笔记二: 一摞烙饼的排序问题

早在一年前，当时我的一个很牛的胖师兄受邀参加Google中国的面试，一开始问他考什么问题他就用签了保密协议打发我们。但当最后他得知无缘Google的时候，终于打开话匣子，跟我们这些小字辈滔滔不绝地传授了一些“面经”。我记得其中就有一道题就是这个一摞烙饼问题，还有一道概率题在我面试MSRA的时候也被问到，可恨我当时没在意，后来面试吃了亏。

言归正传，一摞烙饼问题其实是一个很有意思的问题，它的描述是让一摞随机顺序的烙饼通过单手翻转的方式进行排序，以达到这摞烙饼由小到大顺序放置在盘子上的目的，其特点是每次翻转都会导致第一个烙饼到所要反转的那个烙饼之间的顺序变为逆序。我们的目的是求出次数最少的翻转方案以及翻转次数，很显然这是一个最优化问题，我们本能想到的是动态规划、贪心以及分支限界三种方法。

书中给出的递归算法或称之为分支限界法（即遍历+剪枝=分支限界）秉承了递归算法传统的简单、明了，但效率偏低的特点。这个问题的实质，我们在每一次反转之前其实是需要做出一种选择，这种选择必须能够导致全局最优解。递归算法就是递归的构建所有解（实际是一颗搜索树），并在遍历过程中不断刷新LowerBound和UpperBound，以及当前的最优解（剪枝），并最终找到一个最整体优解。在这种策略下，提高算法的效率只能寄希望于剪枝方法的改进。但是这种方法显然不是多项式时间的，有没有多项式时间的算法呢？

书中P22页提到动态规划，但最后却给出了解决最优化问题普遍适用但效率可能是最差的递归方法。这不禁让人疑惑：这也不美啊！？如果我们能证明该问题满足动态规划或贪心算法的使用条件，解决问题的时间复杂度将会降到多项式时间甚至N^2。但书中提到动态规划却最终没有使用，又没有讲明原因，我觉得是一种疏失（应该不算错误）。那我们就来想一下为什么没有动态规划或贪心算法的原因。

我们知道动态规划方法是一种自底向上的获取问题最优解的方法，它采用子问题的最优解来构造全局最优解。利用动态规划求解的问题需要满足两个条件：即（1）最优子结构 （2）子结构具有重叠性。条件（1）使我们可以利用子问题的最优解来构造全局最优解，而条件（2）是我们在计算过程中可以利用子结构的重叠性来减少运算次数。此外，《算法导论》上还以有向图的无权最短路径和无权最长路径为例提出条件（3）子问题必须独立。

首先我们假定烙饼问题存在优化子结构。假如我们有N个烙饼，把他们以其半径由小到大进行编号。优化子结构告诉我们对于i个烙饼，我们只需要先排列前(i-1)个，然后再将第i个归位；或先排列第2到i个，最后将第一个归位；又或是找到一个位置k[i m_nMaxSwap

step >= m_nMaxSwap)。这个错误运行时也应该查出来啊，再次不理解。

[4]修改完[2]和[3]之后，P28页的例子的运行次数应该是141787次而如果[2]不修改的话运行次数应该为164872

以下是修改后的Java代码，其中所有些数组长度的变量在Java里没用，不过为了保持原文的一致性，这里就没把它们删掉：

public class CakeTuneProblem {

int[] m_cakeArray; // 烙饼信息数组

int m_nCakeCnt; // 烙饼个数

int m_nMaxSwap; // 最多交换次数最多为2*(m_nCakeCnt-1)

int[] m_swapArray; // 交换结果数组

int[] m_reverseCakeArray; // 当前翻转烙饼信息数组

int[] m_reverseCakeArraySwap; // 当前翻转烙饼交换信息数组

int m_nSearch; //当前搜索次数信息

public CakeTuneProblem(){

m_nCakeCnt = 0;

m_nMaxSwap = 0;

}

void run(int[] pCakeArray){

init(pCakeArray);

m_nSearch = 0;

search(0);

}

void output(){

for(int i = 0; i < m_nMaxSwap; i++)

System.out.print(m_swapArray[i]+"");

System.out.println(" Search Times:"+m_nSearch);

System.out.println("Total Swap Times:"+m_nMaxSwap);

}

void init(int[] pCakeArray){

assert( pCakeArray != null);

assert( pCakeArray.length > 0);

m_nCakeCnt = pCakeArray.length;

m_cakeArray = new int[m_nCakeCnt];

for(int i = 0; i < m_nCakeCnt; i++)

m_cakeArray[i] = pCakeArray[i];

m_nMaxSwap = upperBound(m_nCakeCnt);

m_swapArray = new int[m_nMaxSwap];

m_reverseCakeArray = new int[m_nCakeCnt];

for(int i = 0; i < m_nCakeCnt; i++)

m_reverseCakeArray[i] = m_cakeArray[i];

m_reverseCakeArraySwap = new int[m_nMaxSwap];

}

int lowerBound(int[] pCakeArray)

{

int t ret = 0;

for(int i = 1; i < pCakeArray.length; i++){

t = pCakeArray[i] - pCakeArray[i-1];

if( (t==1)

(t == -1)){

}

else{

ret ++;

}

}

return ret;

}

int upperBound(int nCakeCnt){

//return (nCakeCnt-1)*2;

return (nCakeCnt)*2;

}

void search(int step){

int i nEstimate;

m_nSearch++;

//剪枝条件

nEstimate = lowerBound(m_reverseCakeArray);

if( step + nEstimate > m_nMaxSwap

step >= m_nMaxSwap)

return;

if( isSorted( m_reverseCakeArray)){

if( step < m_nMaxSwap){

m_nMaxSwap = step;

for(i = 0; i < m_nMaxSwap; i++)

m_swapArray[i] = m_reverseCakeArraySwap[i];

}

return;

}

for(i = 1; i < m_nCakeCnt; i++){

revert(0i);

m_reverseCakeArraySwap[step] = i;

search(step+1);

revert(0i);

}

}

boolean isSorted(int[] pCakeArray)

{

for(int i = 1; i < pCakeArray.length; i++)

if( pCakeArray[i-1] > pCakeArray[i])

return false;

return true;

}

void revert(int nBegin int nEnd)

{

assert( nEnd > nBegin);

int t = 0;

for( int i=nBegin j=nEnd; i