煎饼排序

煎饼排序（英语：Pancake sorting）指的是将大小不同的一摞煎饼按大小排序的数学问题，其中煎饼铲子每次只能从任意位置铲起上方全部煎饼并翻面。“煎饼数”（英语：pancake number）是指给定煎饼的张数时，最坏情况下需要的最少翻面次数。这个问题最早由美国几何学家雅可比·古德曼提出。它属于排序问题的变种。煎饼排序的目标和传统排序算法最小化比较次数不同，因为它每次操作只允许反转序列的前缀，所以需要最小化反转前缀次数。焦煎饼排序是煎饼排序的变种问题，每张煎饼都有一面是烤焦的，最终除了按照大小排序以外还要让所有焦面向下。

煎饼问题

最初的煎饼问题

对于任意一叠n张煎饼，人们已经证明最小翻转次数在 ${\frac {15}{14}} n$ 到 ${\frac {18} {11} }n$ 之间（约为1.07n到1.64n之间），但精确值仍未知。

最简单的算法在最坏情况下需要2n − 3次翻转。这种算法是选择排序的变体，每轮用一次翻转把未排序的煎饼中最大者翻到顶上，再用一次翻转把它翻到最终所在处（目前未排序煎饼和已排序煎饼的交界处），然后对剩余未排序煎饼重复此过程。剩下两个煎饼时只需一次翻转即完成排序。

1979年比尔·盖茨和赫里斯托斯·帕帕季米特里乌给出了一个上界${ {\frac {5n+5}{3}} }$
。
三十年后德克萨斯州大学达拉斯分校萨薄若（Sudborough）教授领导的一组研究者将这个上界改进为${\frac {18} {11} } n$。

2011年，劳伦特·比尔托（Laurent Bulteau）、纪尧姆·佛丁（Guillaume Fertin）和伊雷娜·鲁苏（Irena Rusu）证明了给定一叠煎饼的长度分布，找到最短解法是NP困难的，最终解决了这个已提出三十余年的问题。

焦煎饼问题

焦煎饼问题（英语：Burnt pancake problem）是煎饼问题的一种变体，其中每个煎饼有一面是焦的，排序后必须使所有煎饼焦的一面朝下。这是一类带符号的排列问题（英语：signed permutation），如果某个煎饼焦的一面朝上，就在排列中给它加一个符号，最后结果必须不含符号。2008年，一组本科生对大肠杆菌编程，构造细菌计算机让其翻转类似焦煎饼的DNA序列，解决了一个简单的焦煎饼问题。DNA具有方向性（5’端和3’端）和顺序（启动子和编码区）。虽然细菌对DNA翻转的处理能力较弱，但单次培养中为数众多的细菌提供了庞大的并行计算平台。当细菌带有抗生素抗药性时，DNA序列的排序问题即告解决。

字符串中的煎饼问题

如果将煎饼摞视为一个字符串，每次翻转相当于取一段前缀并将其反转，这是一个排列操作。不过，前述讨论假定每个煎饼都是不同的，但是字符串可以包含相同字符，因此前缀反转所需次数可能会减少。赫肯斯（Hurkens）等人在2007年构造了二元和三元字符串前缀反转排序的多项式时间精确算法，并证明了用最少的前缀反转次数将一个二元字符串变换为另一个二元字符串是NP困难的。池图瑞（Chitturi）等人于2010年将上述结论推广到了一般字符串，证明了它是NP完全的，并给出了最少次数的上下界。池图瑞在2011年证明了带符号的字符串前缀反转排序（即字符串中的焦煎饼问题）也是NP完全的。

历史

煎饼排序问题最初由雅可比·古德曼提出，他当时用了假名“哈利·德威特”（原文“Harry Dweighter”，音近“harried waiter”，即“忙乱的侍应”）。

煎饼问题更多地在教育中见到，但也会在并行处理网络中用到，它的解答对应着处理器之间高效的最短路算法。这个问题也在计算生物学中有所应用。

微软公司创立者比尔·盖茨就这个问题在1979年发表过一篇题为《前缀逆转排序的边界问题》（英语：Bounds for Sorting by Prefix Reversal）的论文，这是他唯一广为人知的数学论文。在这篇论文中盖茨描述了一种高效的煎饼排序算法。另外，《飞出个未来》的主创之一大卫·科恩研究了焦煎饼问题。他们两位的合作者分别是赫里斯托斯·帕帕季米特里乌（当时在哈佛大学任职，目前在哥伦比亚大学）与曼纽尔·布卢姆（当时在加利福尼亚大学柏克莱分校任职，目前在卡内基·梅隆大学）。

之后，相关的字符串子串反转排序问题也得到了研究。不过，带符号的子串反转排序问题有平方时间的精确算法，但（不带符号的）子串反转问题不存在多项式时间的精确算法，其多项式时间近似算法的近似因子下界为1.0008，上界为1.5，后来找到了近似因子为1.375的多项式时间近似算法。

煎饼图

n-煎饼图的顶点用1到n的全排列编号，两个顶点之间有边当且仅当两个顶点对应的排列可以由前缀反转得到。它是n!个顶点的正则图，度数为n−1。煎饼排序问题等价于求取煎饼图的直径。

n-煎饼图记为Pn，可以使用n个Pn−1递归地构建：给每个子煎饼图分别编号1、2、……、n，编号为i的子图每个顶点对应的排列为1－n这n个数除去i的全排列，末尾加上i。

三阶及以上的煎饼图围长恒为6：

$${\displaystyle g(P_{n})=6{\text{, if }}n>2}$$

Pn的亏格γ(Pn)为：

$${\displaystyle n!\left({\frac {n-4}{6}}\right)+1\leq \gamma (P_{n})\leq n!\left({\frac {n-3}{4}}\right)-{\frac {n}{2}}+1}$$

煎饼图有许多有趣的性质，例如对称性和上文所述的递归结构。另外，它是凯莱图，因此也是顶点传递图。随着维度的增加，煎饼图的度数和直径都以低于对数的速度增长，因此它比超方形图等图更为稀疏。人们对其在并行计算的互连网络模型的应用非常关注。如果把煎饼图视为互连网络的模型，它的直径大小可以衡量通信延迟高低。

原文地址：https://zh.wikipedia.org/wiki/%E7%85%8E%E9%A4%85%E6%8E%92%E5%BA%8F

在知识共享 署名-相同方式共享 3.0协议之条款下提供