[科普中國]-煎餅排序

煎餅排序是數(shù)量問題的口語術(shù)語，當刮刀可以插入堆疊中的任何點并用于翻轉(zhuǎn)其上方的所有薄餅時，按照尺寸的順序?qū)o序堆疊的薄煎餅進行分類。 煎餅數(shù)是給定數(shù)量的煎餅所需的最小翻轉(zhuǎn)數(shù)。 在這種形式下，問題首先由美國幾何學家Jacob E. Goodman討論過。它是排序問題的變體，其中唯一允許的操作是反轉(zhuǎn)序列的某些前綴的元素。 與傳統(tǒng)的排序算法不同，傳統(tǒng)的排序算法試圖以盡可能少的比較進行排序，目標是盡可能少地對序列進行排序。 該問題的一個變體涉及燒焦的煎餅，其中每個煎餅具有燒焦的一面，并且所有的煎餅必須另外在底部燒焦的一面。

煎餅問題燒焦的煎餅問題在一種稱為燒焦煎餅問題的變體中，堆中每個煎餅的底部被燒掉，并且必須在每個煎餅的燒焦面向下完成分類。它是一個有符號的排列，如果一個煎餅我被“燒焦了”，一個負面元素i`代替我的排列。 2008年，一群本科生建造了一臺細菌計算機，通過編程大腸桿菌來翻轉(zhuǎn)類似燒焦煎餅的DNA片段，可以解決燒焦煎餅問題的一個簡單例子。 DNA具有取向（5'和3'）和順序（編碼前的啟動子）。即使由DNA翻轉(zhuǎn)表達的處理能力低，文化中的大量細菌也提供了大型并行計算平臺。當他們通過抗生素抗性解決問題時，細菌會報告。

相同的煎餅堆棧問題這源于印度面包（Roti或薄煎餅）的烹飪方式。最初，所有的烤肉都堆放在一列中，廚師用刮刀翻轉(zhuǎn)烤肉，這樣每個烤肉的每一面都會在某些點接觸烤火。有幾種變體是可能的：rotis可以被認為是單面或雙面的，并且可以禁止或不兩次烘烤同一面。 Arka Roychowdhury首先探討了這個問題的版本。

字符串上的煎餅問題上面的討論假定每個煎餅是唯一的，即，執(zhí)行前綴反轉(zhuǎn)的序列是置換。然而，“字符串”是符號可以重復(fù)的序列，并且這種重復(fù)可以減少排序所需的前綴反轉(zhuǎn)的數(shù)量。 Chitturi和Sudborough（2010年）和Hurkens等人。 （2007）獨立地表明，將具有最小前綴反轉(zhuǎn)次數(shù)的兼容字符串轉(zhuǎn)換為另一種字符串的復(fù)雜性是NP完全的。他們也給了同樣的限制1。 Hurkens等人。給出了一個精確的算法來排序二進制和三進制字符串。 Chitturi（2011）證明了將兼容的帶符號字符串轉(zhuǎn)換為另一個具有最小簽名前綴反轉(zhuǎn)次數(shù)的復(fù)雜性 - 字符串上燒焦的煎餅問題-是NP完全的。

歷史煎餅分揀問題首先由雅各布·E·古德曼（Jacob E. Goodman）提出，用筆名“哈利·加勒特”（Harry Dweighter）（匆忙的服務(wù)員）撰寫。雖然經(jīng)常被視為一種教育設(shè)備，但煎餅分類也出現(xiàn)在并行處理器網(wǎng)絡(luò)的應(yīng)用中，它可以在處理器之間提供有效的路由算法。

這個問題值得注意的是微軟創(chuàng)始人比爾蓋茨（作為威廉蓋茨）唯一著名的數(shù)學論文題目，題為“按前綴逆轉(zhuǎn)排序的界限”。它出版于1979年，它描述了一種有效的煎餅分選算法。此外，由Futurama聯(lián)合創(chuàng)始人David X. Cohen（作為David S. Cohen）發(fā)表的最著名的論文涉及燒焦的煎餅問題。他們的合作者分別是Christos Papadimitriou（當時在哈佛大學，現(xiàn)在在哥倫比亞大學）和Manuel Blum（當時在伯克利，現(xiàn)在在卡內(nèi)基梅隆大學）。

最近還研究了通過逆轉(zhuǎn)進行符號排序和通過逆轉(zhuǎn)進行排序的相關(guān)問題。雖然已經(jīng)通過反轉(zhuǎn)找到了有效的精確算法用于帶符號的排序，已經(jīng)證明通過反轉(zhuǎn)排序的問題甚至難以逼近某個常數(shù)因子，并且也被證明在多項式時間內(nèi)是近似的。在近似因子1.375內(nèi)。

本詞條內(nèi)容貢獻者為:

李嘉騫 - 博士 - 同濟大學