烧饼的排序

问题描述： 有一摞烙饼，因为一只手端着盘子，所以只能用另外一只手来给烙饼排序，将烙饼由大到小排好序。这样就要求我们在给烙饼排序的时候总是将最上面的N个烙饼一起翻转。如果最下面的烙饼是最大的，那么只需要解决上面的N-1个烙饼，同理可以最后到解决两个烙饼的排序。

 

简单的排序方法：先找到最大的烙饼，将其和其以上的烙饼一起翻转，这样最大的烙饼就在盘子的最上面了，然后翻转所有的烙饼，这样最大的烙饼就在盘子的最下面了。同样的，处理剩下的N-1个烙饼，知道最后所有的烙饼都排好序。可以知道我们最多需要进行2*（N-1）次翻转就可以将所有的烙饼排好序。

 

问题？ 如果减少烙饼的反转次数，达到一个最优的解。 加入这堆老兵中有几个不同的部分相对有序，凭直接来猜测，可以把笑一下的烙饼进行翻转，每次考虑翻转烙饼的时候总是把相邻的烙饼尽可能的放到一起。

 

解决方法： 通过穷举法来找所有可能方案中的最优方案，自然会用到动态规划或者递归的方法来实现。可以从不同的翻转策略开始，比如第一次先翻最小的，然后递归的把所有的可能都全部翻转一次。

 

既然2（N-1）是一个最多的翻转次数，就可以得知，如果算法中的翻转次数超过了2（N-1），我们就应该放弃这个算法。

 

我们总是希望UpperBound越小越好，而LowerBound则越大越好，这样就可以尽可能的减少搜索的次数，是算法的性能更好。

 

代码如下：（代码可能需要仔细的阅读，才能明白算法的含义）

#pragma once
class CPrefixSorting
{
public:
    ~CPrefixSorting(void);
    CPrefixSorting()
    {
        m_nCakeCnt=0;
        m_nMaxSwap=0;
    }

    // 计算烙饼翻转信息
    // @param
    // pCakeArray  存储烙饼索引数组
    // nCakeCnt    烙饼个数
    //
    void Run(int* pCakeArray, int nCakeCnt)
    {
        Init(pCakeArray,nCakeCnt);
        m_nSearch=0;
        Search(0);
    }

    // 输出烙饼的翻转次数，翻转信息
    void Output()
    {
        for(int i=0;i<m_nMaxSwap;i++)
        {
            printf("%d",m_SwapArray[i]);
        }
        printf("\n |Search Times|:%d\n",m_nSearch);
        printf("Total Swap times=%d\n",m_nMaxSwap);
    }

private:
    int* m_CakeArray; // 烙饼信息数组
    int m_nCakeCnt; // 烙饼的个数
    int m_nMaxSwap; // 最多交换次数，根据前面的推断，最多为m_nCakeCnt*2
    int* m_SwapArray;     // 交换结果数组
    int* m_ReverseCakeArray; // 当前翻转烙饼信息数组
    int* m_ReverseCakeArraySwap; // 当前翻转烙饼交换结果数组
    int m_nSearch;             // 当前搜索次数信息

    // 初始化数组信息
    // @param
    // pCakeArray   存储烙饼索引数组
    // nCakeCnt     烙饼个数
    //
    void Init(int* pCakeArray,int nCakeCnt)
    {
        m_nCakeCnt=nCakeCnt;

        // 初始化烙饼数组
        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+1];

        // 初始化中间交换结果信息
        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 UpperBound(int nCakeCnt)
    {
        return nCakeCnt*2;
    }

    // 当前翻转的下届
    int LowerBound(int* pCakeArray, int nCakeCnt)
    {
        int t,ret=0;
        // 根据当前数组的排序信息情况来判断最少需要交换多少次
        for(int i=1;i<nCakeCnt;i++)
        {
            // 判断位置相邻的两个烙饼是否为尺寸排序上相等的
            t=pCakeArray[i]-pCakeArray[i-1];
            if((t==1)||(t==-1))
            {}
            else
            {
                ret++;
            }
        }

        return ret;
    }

    // 排序的主函数
    void Search(int step)
    {
        int i, nEstimate;
        m_nSearch++;

        // 估算当前搜索所需要的最小的交换次数
        nEstimate=LowerBound(m_ReverseCakeArray,m_nCakeCnt);
        if(step+nEstimate>m_nMaxSwap)
        {
            return;
        }

        // 如果已经排好序，即翻转完成后，输出结果
        if(IsSorted(m_ReverseCakeArray, m_nCakeCnt))
        {
            if(step<m_nMaxSwap)
            {
                m_nMaxSwap=step;// 修改最大的翻转次数，让m_nMaxSwap记录最小的翻转次数
                for(i=0;i<m_nMaxSwap;i++)
                {
                    m_SwapArray[i]=m_ReverseCakeArraySwap[i];
                }
            }
            return;
        }

        // 递归进行翻转
        for(i=1;i<m_nCakeCnt;i++)
        {
            Reverse(0,i);
            m_ReverseCakeArraySwap[step]=i;
            Search(step+1);
            Reverse(0,i);
        }
    }

    // 判断是否已经排好序
    bool IsSorted(int* pCakeArray, int nCakeCnt)
    {
        for(int i=1;i<nCakeCnt;i++)
        {
            if(pCakeArray[i-1]>pCakeArray[i])
            {
                return false;
            }
        }
        return true;
    }

    // 翻转烙饼信息
    // 非常经典的数组翻转算法
    void Reverse(int nBegin,int nEnd)
    {
        int i,j,t;
        for(i=nBegin,j=nEnd;i<j;i++,j--)
        {
            t=m_ReverseCakeArray[i];
            m_ReverseCakeArray[i]=m_ReverseCakeArray[j];
            m_ReverseCakeArray[j]=t;
        }
    }
};

// CPrefixSorting.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include "stdio.h"
#include "iostream"
#include "PrefixSorting.h"

using namespace std;


int _tmain(int argc, _TCHAR* argv[])
{
    cout<<"--->begin"<<endl;
    CPrefixSorting panCakeSort;
    int panCake[5]={3,5,1,4,2};
    panCakeSort.Run(panCake,5);
    panCakeSort.Output();
    return 0;
}

书上用的是分枝限界算法（遍历+剪纸）。
问题的关键在于“如何可以有效地剪枝”。
薛迪的博客分析的很好。他的第一篇博客“一摞烙饼的排序问题”做了如下分析：本题是一道最优化问题，可以考虑的算法有：搜索法、DP算法和Greedy算法。然后，他分析了为何本题不能使用DP算法——因为本题不满足最有子结构的性质。（DP算法需要满足：最有子结构、重复子问题、独立子问题三个性质）。
他的第二篇博客《烙饼问题与搜索树》讲述了对于最优化问题的最一般的解法：“利用搜索树来求解”。他在本文中指出了“利用剪枝来加快求解速度”的关键在于“如何才能有效地剪枝”。随后，他有描述了几种剪枝策略：1）爬山法：在深度优先搜索过程中使用贪心算法确定搜索方向，其关键在于测度函数f(n)的定义（测度函数是用来度量从该节点到目标节点的代价的函数）；2）best-first搜索策略（最佳优先搜索策略）：结合了深度优先和广度优先的优点，利用评价函数（用来度量从根节点到该节点的代价的函数），在目前产生的所有节点中选择具有最小代价的节点进行扩展，具体用最小堆来实现搜索树；3）A*算法：其搜索树中国每一个节点的代价是f*(n)=g(n)+h*(n)，g(n)是从根节点到节点n的代价，可以求出确定值；h*(n)是从n节点到目标节点的代价，这是估计值。如果A*算法找到了一个解，那么它一定是优化解。

自己的理解：
对于书上的搜索算法，在搜索树中有很多重复的子问题，如何避免子问题的重复计算也是一个优化的重点。
1）对于一组数字：a1,a2,a3,a4,…,an。如果第i次翻转的是前k个，则结果是：ak,…,a1, a(k+1) ,.., an。如果第i+1次翻转的也是前k个，则结果是：a1,…,ak, a(k+1) ,.., an。出现了重复字问题。这类重复字问题的避免非常简单：在search中加入一条语句即可：
void search(int step){
   int i, nEstateTime;

   m_nSearch ++;

   nEstateTime = lowerBound(m_ReverseCakeArray, m_nCakeCnt);
   if (step + nEstateTime > m_nMaxSwap)
    return;

   if (isSorted(m_ReverseCakeArray, m_nCakeCnt))
   {
    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 ++)
   {
    if (i != m_ReverseCakeArraySwap[step - 1])
    {  
     revert(0, i);
     m_ReverseCakeArraySwap[step] = i;
     search(step + 1);
     revert(0, i);
    }
   }
}

补充：

书上程序的低效主要是由于进行剪枝判断时，没有考虑好边界条件，可进行如下修改：

1  if(step + nEstimate > m_nMaxSwap)  > 改为 >=。

2  判断下界时，如果最大的烙饼不在最后一个位置，则要多翻转一次，因而在LowerBound函数return ret; 前插入一行：

if (pCakeArray[nCakeCnt-1] != nCakeCnt-1) ret++; 。

3  n个烙饼，翻转最大的n-2烙饼最多需要2*(n-2)次，剩下的2个最多1次，因而上限值为2*n-3，因此，m_nMaxSwap初始值可以取2*n-3+1=2*n-2，这样每步与m_nMaxSwap的判断就可以取大等于号。

4  采用书上提到的确定“上限值”的方法，直接构建一个初始解，取其翻转次数为m_nMaxSwap的初始值。

1和2任改一处，都能使搜索次数从172126降到两万多，两处都改，搜索次数降到3475。若再改动第3处，搜索次数降到2989；若采用4的方法（此时初始值为10），搜索次数可降到1045。