[科普中国]-煎饼排序

煎饼排序是数量问题的口语术语，当刮刀可以插入堆叠中的任何点并用于翻转其上方的所有薄饼时，按照尺寸的顺序对无序堆叠的薄煎饼进行分类。 煎饼数是给定数量的煎饼所需的最小翻转数。 在这种形式下，问题首先由美国几何学家Jacob E. Goodman讨论过。它是排序问题的变体，其中唯一允许的操作是反转序列的某些前缀的元素。 与传统的排序算法不同，传统的排序算法试图以尽可能少的比较进行排序，目标是尽可能少地对序列进行排序。 该问题的一个变体涉及烧焦的煎饼，其中每个煎饼具有烧焦的一面，并且所有的煎饼必须另外在底部烧焦的一面。

煎饼问题烧焦的煎饼问题在一种称为烧焦煎饼问题的变体中，堆中每个煎饼的底部被烧掉，并且必须在每个煎饼的烧焦面向下完成分类。它是一个有符号的排列，如果一个煎饼我被“烧焦了”，一个负面元素i`代替我的排列。 2008年，一群本科生建造了一台细菌计算机，通过编程大肠杆菌来翻转类似烧焦煎饼的DNA片段，可以解决烧焦煎饼问题的一个简单例子。 DNA具有取向（5'和3'）和顺序（编码前的启动子）。即使由DNA翻转表达的处理能力低，文化中的大量细菌也提供了大型并行计算平台。当他们通过抗生素抗性解决问题时，细菌会报告。

相同的煎饼堆栈问题这源于印度面包（Roti或薄煎饼）的烹饪方式。最初，所有的烤肉都堆放在一列中，厨师用刮刀翻转烤肉，这样每个烤肉的每一面都会在某些点接触烤火。有几种变体是可能的：rotis可以被认为是单面或双面的，并且可以禁止或不两次烘烤同一面。 Arka Roychowdhury首先探讨了这个问题的版本。

字符串上的煎饼问题上面的讨论假定每个煎饼是唯一的，即，执行前缀反转的序列是置换。然而，“字符串”是符号可以重复的序列，并且这种重复可以减少排序所需的前缀反转的数量。 Chitturi和Sudborough（2010年）和Hurkens等人。 （2007）独立地表明，将具有最小前缀反转次数的兼容字符串转换为另一种字符串的复杂性是NP完全的。他们也给了同样的限制1。 Hurkens等人。给出了一个精确的算法来排序二进制和三进制字符串。 Chitturi（2011）证明了将兼容的带符号字符串转换为另一个具有最小签名前缀反转次数的复杂性 - 字符串上烧焦的煎饼问题-是NP完全的。

历史煎饼分拣问题首先由雅各布·E·古德曼（Jacob E. Goodman）提出，用笔名“哈利·加勒特”（Harry Dweighter）（匆忙的服务员）撰写。虽然经常被视为一种教育设备，但煎饼分类也出现在并行处理器网络的应用中，它可以在处理器之间提供有效的路由算法。

这个问题值得注意的是微软创始人比尔盖茨（作为威廉盖茨）唯一着名的数学论文题目，题为“按前缀逆转排序的界限”。它出版于1979年，它描述了一种有效的煎饼分选算法。此外，由Futurama联合创始人David X. Cohen（作为David S. Cohen）发表的最着名的论文涉及烧焦的煎饼问题。他们的合作者分别是Christos Papadimitriou（当时在哈佛大学，现在在哥伦比亚大学）和Manuel Blum（当时在伯克利，现在在卡内基梅隆大学）。

最近还研究了通过逆转进行符号排序和通过逆转进行排序的相关问题。虽然已经通过反转找到了有效的精确算法用于带符号的排序，已经证明通过反转排序的问题甚至难以逼近某个常数因子，并且也被证明在多项式时间内是近似的。在近似因子1.375内。

本词条内容贡献者为:

李嘉骞 - 博士 - 同济大学