text: 煎餅排序是指給定煎餅的張數時，最壞情況下需要的最少翻面次數。這個問題最早由美國幾何學家提出。它屬於排序問題的變種。煎餅排序的目標和傳統排序演算法最小化比較次數不同，因為它每次操作只允許反轉序列的，所以需要最小化反轉字首次數。焦煎餅排序是煎餅排序的變種問題，每張煎餅都有一面是烤焦的，最終除了按照大小排序以外還要讓所有焦面向下。煎餅問題.最初的煎餅問題.對於任意一疊"n"之間，但精確值仍未知。最簡單的演算法在最壞情況下需要2"n" − 3次翻轉。這種演算法是選擇排序的變體，每輪用一次翻轉把未排序的煎餅中最大者翻到頂上，再用一次翻轉把它翻到最終所在處，然後對剩餘未排序煎餅重複此過程。剩下兩個煎餅時只需一次翻轉即完成排序。1979年比爾·蓋茨和赫里斯託斯·帕帕季米特里烏給出了一個上界"n"。2011年，勞倫特·比爾託證明了給定一疊煎餅的長度分佈，找到最短解法是NP困難的，最終解決了這個已提出三十餘年的問題。焦煎餅問題.焦煎餅問題。雖然細菌對DNA翻轉的處理能力較弱，但單次培養中為數眾多的細菌提供了龐大的平行計算平臺。當細菌帶有抗生素抗藥性時，DNA序列的排序問題即告解決。字串中的煎餅問題.如果將煎餅摞視為一個字串，每次翻轉相當於取一段字首並將其反轉，這是一個置換操作。不過，前述討論假定每個煎餅都是不同的，但是字串可以包含相同字元，因此字首反轉所需次數可能會減少。赫肯斯也是NP完全的。歷史.煎餅排序問題最初由提出，他當時用了假名“哈利·德威特”。煎餅問題更多地在教育中見到，但也會在並行處理網路中用到，它的解答對應著處理器之間高效的最短路演算法。這個問題也在計算生物學中有所應用。微軟公司創立者比爾·蓋茨就這個問題在1979年發表過一篇題為《字首逆轉排序的邊界問題》。之後，相關的字串子串反轉排序問題也得到了研究。不過，帶符號的子串反轉排序問題有平方時間的精確演算法，但子串反轉問題不存在多項式時間的精確演算法，其多項式時間近似演算法的近似因子下界為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：formula_1Pn的虧格γ(Pn)為：formula_2煎餅圖有許多有趣的性質，例如對稱性和上文所述的遞迴結構。另外，它是凱萊圖，因此也是。隨著維度的增加，煎餅圖的度數和直徑都以低於對數的速度增長，因此它比等圖更為。人們對其在平行計算的互連網路模型的應用非常關注。如果把煎餅圖視為互連網路的模型，它的直徑大小可以衡量通訊延遲高低。相關整數序列.在整數數列線上大全中，有一些序列與煎餅排序有關：拓展閱讀.
metadata: erhwenkuo/wikipedia-zhtw
metadata: 煎餅排序
metadata: https://zh.wikipedia.org/wiki?curid=6105909