Třídění palačinek - Pancake sorting

Demonstrace primární operace. Špachtle se otáčí přes tři nejlepší palačinky, výsledek je vidět níže. U problému se spálenou palačinkou by nyní byly spáleny jejich horní strany místo jejich spodních stran.

Třídění palačinek je hovorový výraz pro matematický problém třídění neuspořádaného stohu palačinek v pořadí podle velikosti, když špachtle lze vložit do libovolného bodu v zásobníku a použít k překlopení všech palačinek nad ním. A číslo palačinky je minimální počet otočení požadovaný pro daný počet palačinek. V této podobě byl problém poprvé projednán Američanem geometr Jacob E. Goodman.[1] Jedná se o variantu problému Spálený palačinky, kde každá palačinka má spálenou stranu a všechny palačinky musí navíc skončit spálenou stranou dole.

Všechny metody řazení vyžadují porovnání párů prvků. Pro tradiční problém s tříděním, obvyklým studovaným problémem je minimalizace počet srovnání potřebných k seřazení seznamu. Počet skutečných operací, například výměna dvou prvků, je potom irelevantní. U problémů s tříděním palačinek je naopak cílem minimalizovat počet operací, kde jedinou povolenou operací jsou obrácení prvků některých předpona sekvence. Počet srovnání je nyní irelevantní.

Problémy s palačinkami

Původní problém s palačinkami

Minimální počet otočení potřebný k roztřídění libovolného stohu n Bylo prokázáno, že mezi nimi leží palačinky 15/14n a 18/11n (přibližně 1,07n a 1,64n,), ale přesná hodnota není známa.[2]

Nejjednodušší algoritmus třídění palačinek funguje nanejvýš 2n − 3 převrátí. V tomto algoritmu jakési výběr řazení, přivedeme na jeden vrchol největší palačinku, která dosud nebyla roztříděna; vezměte jej dolů do své konečné polohy ještě jedním otočením; a tento postup opakujte pro zbývající palačinky.

V roce 1979 Bill Gates a Christos Papadimitriou[3] dal horní hranici (5n+5)/3. Toto bylo o třicet let později vylepšeno na 18/11n týmem výzkumníků na University of Texas v Dallasu, vedená profesorem zakladatelů Hal Sudborough.[4][5]

V roce 2011 Laurent Bulteau, Guillaume Fertin a Irena Rusu[6] prokázal, že problém najít nejkratší sekvenci převrácení pro daný stoh palačinek je NP-tvrdé, čímž zodpověděl otázku, která byla otevřena více než tři desetiletí.

Problém se spálenou palačinkou

Ve variantě zvané problém spálené palačinky, spodní část každé palačinky na hromádce je spálená a druh musí být dokončen spálenou stranou každé palačinky dolů. Je to podepsaná permutace, a pokud palačinka i je „spálená strana nahoru“ negativní prvek já` je nahrazen i v permutaci. V roce 2008 skupina vysokoškoláků postavila bakteriální počítač který může vyřešit jednoduchý příklad problému se spálenou palačinkou programováním E-coli překlopit segmenty DNA, které jsou analogické spáleným palačinkům. DNA má orientaci (5 'a 3') a pořadí (promotor před kódováním). I když je výpočetní výkon vyjádřený převrácením DNA nízký, vysoký počet bakterií v kultuře poskytuje velkou paralelní výpočetní platformu. Bakterie se hlásí, když problém vyřeší tím, že se stanou rezistentními na antibiotika.[7]

Problém se shodnými palačinkami

To je inspirováno způsobem indického chleba (roti nebo chapati ) je uvařený. Zpočátku jsou všechny rotis naskládány do jednoho sloupce a kuchař pomocí špachtle otočí rotis tak, aby se každá strana každé roti v určitém okamžiku dotkla základního ohně k přípitku. Možných je několik variant: rotis lze považovat za jednostranný nebo oboustranný a může být zakázáno nebo nepřipít dvakrát na stejnou stranu. Tuto verzi problému poprvé prozkoumala Arka Roychowdhury.[8]

Problém s palačinkami na strunách

Výše uvedená diskuse předpokládá, že každá palačinka je jedinečná, to znamená, že sekvence, na které se provádí obrácení předpony, je permutace. „Řetězce“ jsou však sekvence, ve kterých se symbol může opakovat, a toto opakování může snížit počet obrácení předpony požadovaných k řazení. Chitturi a Sudborough (2010) a Hurkens et al. (2007) nezávisle ukázali, že složitost transformace kompatibilního řetězce na jiný s minimálním počtem obrácení předpony je NP-kompletní. Také dali hranice. Hurkens a kol. dal přesný algoritmus pro třídění binárních a ternárních řetězců. Chitturi[9] (2011) prokázali, že složitost transformace kompatibilního podepsaného řetězce na jiný s minimálním počtem obrácených prefixů předpony - problém spálené palačinky na řetězcích - je NP-úplná.

Dějiny

Nejprve nastal problém s tříděním palačinek Jacob E. Goodman, psal pod pseudonymem „Harry Dweighter“ („pronásledovaný číšník“).[10]

Přestože se pancake sorting vnímá častěji jako vzdělávací zařízení, objevuje se také v aplikacích v sítích paralelních procesorů, ve kterých může poskytnout efektivní směrovací algoritmus mezi procesory.[11][12]

Problém je pozoruhodný jako téma jediné známé matematické práce od Microsoft zakladatel Bill Gates (jako William Gates) s názvem „Meze pro třídění podle obrácení předpony“. Publikovaný v roce 1979 popisuje efektivní algoritmus pro třídění palačinek.[3] Kromě toho nejpozoruhodnější příspěvek publikovaný nakladatelstvím Futurama spolutvůrce David X. Cohen (jako David S. Cohen) se týkal problému spálené palačinky.[13] Jejich spolupracovníci byli Christos Papadimitriou (poté v Harvard, nyní v Columbia ) a Manuel Blum (poté v Berkeley, nyní v Univerzita Carnegie Mellon ).

Nedávno byly také studovány související problémy třídění se znaménkem podle obrácení a řazení podle obrácení. Vzhledem k tomu, že byly nalezeny účinné přesné algoritmy pro podepsané řazení podle obrácení,[14] Ukázalo se, že problém třídění obráceně je obtížné přiblížit se v rámci určitého konstantního faktoru,[15] a také se ukázalo být přibližné v polynomiálním čase v rámci aproximačního faktoru 1.375.[16]

Pancake grafy

Graf lívance P3
Graf lívance P4 lze konstruovat rekurzivně ze 4 kopií P3 přiřazením jiného prvku ze sady {1, 2, 3, 4} jako přípony ke každé kopii.
Hlavní článek: Palačinkový graf

An n-pancake graf je graf, jehož vrcholy jsou permutacemi n symboly od 1 do n a jeho okraje jsou uvedeny mezi permutacemi přechodnými zvrácením předpony. Je to běžný graf s n! vrcholy, jeho stupeň je n − 1. Problém třídění palačinek a problém získat průměr grafu palačinky je ekvivalentní.[17]

Palačinkový graf dimenze n, Pn lze konstruovat rekurzivně z n kopií Pn − 1tím, že ke každé kopii přiřadíte odlišný prvek ze sady {1, 2,…, n} jako příponu.

Jejich obvod:

.

Γ (strn) rod z P.n je:[18]

Vzhledem k tomu, že palačinkové grafy mají mnoho zajímavých vlastností, jako jsou symetrické a rekurzivní struktury, malé stupně a průměry ve srovnání s velikostí grafu, je jim věnována velká pozornost jako modelu propojovacích sítí pro paralelní počítače.[19][20][21] Když považujeme palačinkové grafy za model propojovacích sítí, je průměr grafu mírou, která představuje zpoždění komunikace.[22][23]

Pancake grafy jsou Cayleyovy grafy (tak jsou vrchol-tranzitivní ) a jsou zvláště atraktivní pro paralelní zpracování. Mají sublogaritmický stupeň a průměr a jsou relativně řídký (ve srovnání např. hyperkrychle ).[18]

Související celočíselné sekvence

Počet stohů dané výšky n které vyžadují jedinečné převrácení k třídit
Výška
n		k
0123456789101112131415
11
211
31221
4136113
51412354820
61520791992811332
7163014954313571903101635
817422511191428110561150118520455
918563912278106663801593585132697793795804
101972575396322825106461377863919365130975681467873232
11110908096429438912527371174766412651599810731425047191236489563546
1211111010999883779375333973064788141419294933725211842004316933221311105006613032704167
1311213214511455613009610305057046318403095551849922756397834751525125357218305656614586536481868748522001

Sekvence od Online encyklopedie celočíselných sekvencí:

  • OEIS: A058986 - maximální počet otočení
  • OEIS: A067607 - počet stohů vyžadujících maximální počet vyletí (výše)
  • OEIS: A078941 - maximální počet vyletí pro "spálenou" hromádku
  • OEIS: A078942 - počet výkyvů pro seřazený stoh "spálená strana nahoře"
  • OEIS: A092113 - výše uvedený trojúhelník, čtený po řádcích

[9]

Reference

  1. ^ Simon Singh (14. listopadu 2013). „Překlápění palačinek s matematikou“. Opatrovník. Citováno 25. března 2014.
  2. ^ Fertin, G .; Labarre, A .; Rusu, I .; Tannier, E .; Vialette, S. (2009). Kombinatorika přeskupení genomu. MIT Press. ISBN  9780262062824.
  3. ^ A b Gates, W.; Papadimitriou, C. (1979). "Meze pro třídění podle obrácení předpony" (PDF). Diskrétní matematika. 27: 47–57. doi:10.1016 / 0012-365X (79) 90068-2. Archivovány od originál (PDF) 10. června 2007. Citováno 31. března 2007.
  4. ^ „Tým je nejlepším mladým Billem Gatesem se zlepšenou odpovědí na takzvaný problém s palačinkami v matematice“. University of Texas at Dallas News Center. 17. září 2008. Archivováno od originál 5. dubna 2012. Citováno 10. listopadu 2008. Tým studentů výpočetní techniky UT Dallas a jejich poradce na fakultě zdokonalili dlouhodobé řešení matematické hádanky známé jako problém s palačinkami. Předchozí nejlepší řešení, které trvalo téměř 30 let, navrhl Bill Gates a jeden z jeho instruktorů z Harvardu Christos Papadimitriou několik let před založením společnosti Microsoft.
  5. ^ Chitturi, B .; Fahle, W .; Meng, Z .; Morales, L .; Shields, CO; Sudborough, I. H .; Voit, W. (31. srpna 2009). Msgstr "Horní hranice (18/11) n pro třídění podle obrácení předpony". Teoretická informatika. Grafy, hry a výpočet: Věnováno profesorovi Burkhardovi Monienovi u příležitosti jeho 65. narozenin. 410 (36): 3372–3390. doi:10.1016 / j.tcs.2008.04.045.
  6. ^ Bulteau, Laurent; Fertin, Guillaume; Rusu, Irena (2015). "Pancake Flipping Is Hard". Journal of Computer and System Sciences. 81 (8): 1556–1574. arXiv:1111.0434. doi:10.1016 / j.jcss.2015.02.003.
  7. ^ Haynes, Karmella A; Broderick, Marian L; Brown, Adam D; Butner, Trevor L; Dickson, James O; Harden, W Lance; Slyšel, Lane H; Jessen, Eric L; Malloy, Kelly J; Ogden, Brad J; Rosemond, Sabriya; Simpson, Samantha; Zwack, Erin; Campbell, A Malcolm; Eckdahl, Todd T; Heyer, Laurie J.; Básník, Jeffrey L (2008). „Inženýrské bakterie k vyřešení problému se spálenou palačinkou“. Journal of Biological Engineering. 2: 8. doi:10.1186/1754-1611-2-8. PMC  2427008. PMID  18492232.
  8. ^ Roychowdhury, Arka (18. března 2015). „Itunes: Flipping Pancakes“. Crazy1S.
  9. ^ A b Chitturi, Bhadrachalam (2011). "POZNÁMKA O KOMPLEXNOSTI GENETICKÝCH MUTACÍ". Diskrétní matematika, algoritmy a aplikace. 03 (3): 269–286. doi:10.1142 / S1793830911001206.
  10. ^ Dweighter, Harry (1975), „Elementární problém E2569“, Amer. Matematika. Měsíční, 82 (10): 1009–1010, doi:10.2307/2318260, JSTOR  2318260
  11. ^ Gargano, L .; Vaccaro, U .; Vozella, A. (1993). "Směrování odolné vůči chybám v propojovacích sítích hvězd a palačinek". Dopisy o zpracování informací. 45 (6): 315–320. CiteSeerX  10.1.1.35.9056. doi:10.1016/0020-0190(93)90043-9. PAN  1216942..
  12. ^ Kaneko, K .; Peng, S. (2006). Msgstr "Nesouvislé cesty směrování v grafech palačinek". Proceedings of Seventh International Conference on Parallel and Distributed Computing, Applications and Technologies, 2006 (PDCAT '06). str. 254–259. doi:10.1109 / PDCAT.2006.56. ISBN  978-0-7695-2736-9..
  13. ^ Cohen, D.S.; Blum, M. (1995). „K problému třídění spálených palačinek“. Diskrétní aplikovaná matematika. 61 (2): 105. doi:10.1016 / 0166-218X (94) 00009-3.
  14. ^ Kaplan, H .; Shamir, R .; Tarjan, R.E. (1997). "Rychlejší a jednodušší algoritmus pro třídění podepsaných permutací podle reverzí". Proc. 8. ACM-SIAM SODA: 178–87.
  15. ^ Berman, P .; Karpinski, M. (1999). „O některých užších výsledcích nepřítomnosti“. Proc. 26. ICALP (1999) LNCS 1644: 200–09.
  16. ^ Berman, P .; Karpinski, M.; Hannenhalli, S. (2002). „Algoritmy aproximace 1,375 pro třídění podle obrácení“. Proc. 10. ESA (2002), LNCS 2461: 200–10.
  17. ^ Asai, Shogo; Kounoike, Yuusuke; Shinano, Yuji; Kaneko, Keiichi (1. září 2006). Výpočet průměru grafu 17 palačinek pomocí PC clusteru. Paralelní zpracování Euro-Par 2006: 12. mezinárodní konference Euro-Par. Přednášky z informatiky. 4128. str. 1114–1124. doi:10.1007/11823285_117. ISBN  978-3-540-37783-2.
  18. ^ A b Nguyen, Quan; Bettayeb, Said (5. listopadu 2009). „On the Genus of Pancake Network“ (PDF). International Arab Journal of Information Technology. 8 (3): 289–292.
  19. ^ Akl, S.G .; Qiu, K .; Stojmenović, I. (1993). Msgstr "Základní algoritmy pro propojení sítí hvězd a palačinek s aplikacemi pro výpočetní geometrii". Sítě. 23 (4): 215–225. CiteSeerX  10.1.1.363.4949. doi:10,1002 / net. 3230230403.
  20. ^ Bass, D.W .; Sudborough, I.H. (Březen 2003). "Problémy s palačinkami s omezenými reverzemi předpon a některými odpovídajícími sítěmi Cayley". Journal of Parallel and Distributed Computing. 63 (3): 327–336. CiteSeerX  10.1.1.27.7009. doi:10.1016 / S0743-7315 (03) 00033-9.
  21. ^ Berthomé, P .; Ferreira, A .; Perennes, S. (prosinec 1996). "Optimální šíření informací v sítích hvězd a palačinek". Transakce IEEE na paralelních a distribuovaných systémech. 7 (12): 1292–1300. CiteSeerX  10.1.1.44.6681. doi:10.1109/71.553290.
  22. ^ Kumar, V .; Grama, A .; Gupta, A .; Karypis, G. (1994). Úvod do paralelních výpočtů: Návrh a analýza algoritmů. Benjamin / Cummings.
  23. ^ Quinn, M. J. (1994). Parallel Computing: Theory and Practice (druhé vydání). McGraw-Hill.

Další čtení

externí odkazy