Isten algoritmusa - God's algorithm

Isten algoritmusa egy olyan elképzelés, amely a Rubik -kocka rejtvény megoldási módjainak tárgyalásaiból ered , de más kombinációs rejtvényekre és matematikai játékokra is alkalmazható . Minden olyan algoritmusra vonatkozik, amely a lehető legkevesebb mozdulattal rendelkező megoldást állít elő, azzal az elképzeléssel, hogy csak egy mindentudó lény ismeri az optimális lépést bármely konfigurációtól.

Hatály

Meghatározás

Ez a fogalom olyan rejtvényekre vonatkozik, amelyek véges számú "konfigurációt" feltételezhetnek, viszonylag kicsi, jól meghatározott "mozdulatok" arzenáljával, amelyek alkalmazhatók lehetnek a konfigurációkra, majd új konfigurációhoz vezethetnek. A rejtvény megoldása azt jelenti, hogy elérünk egy kijelölt "végső konfigurációt", egy egyedi konfigurációt vagy a konfigurációk egyikét. A rejtvény megoldásához mozdulatsort alkalmazunk, kezdve valamilyen tetszőleges kezdeti konfigurációtól.

Megoldás

Egy algoritmus úgy tekinthető egy ilyen rejtvény megoldására, ha bemenetként egy tetszőleges kezdeti konfigurációt vesz fel, és kimenetként egy végső konfigurációhoz vezető mozdulatsort állít elő ( ha a feladvány megoldható ebből a kezdeti konfigurációból, ellenkező esetben azt jelzi, hogy egy megoldás). A megoldás akkor optimális, ha a mozdulatsorozat a lehető legrövidebb. Ezt a számot Isten számának vagy formálisabban a minimumx értéknek nevezik . Isten algoritmusa tehát egy adott rejtvény esetében olyan algoritmus, amely megoldja a rejtvényt, és csak optimális megoldásokat hoz létre.

Egyes írók, például David Joyner, úgy vélik, hogy ahhoz, hogy egy algoritmust megfelelően "Isten algoritmusának" nevezzenek , praktikusnak is kell lennie , vagyis az algoritmus nem igényel rendkívüli mennyiségű memóriát vagy időt. Például a kezdeti konfigurációkkal indexelt óriási keresőtáblázat használatával nagyon gyorsan lehet megoldásokat találni, de rendkívüli mennyiségű memóriát igényel.

Ahelyett, hogy teljes megoldást kérne, egyenként kérhet egyetlen lépést a kezdeti, de nem végleges konfigurációból, ahol a lépés az első az optimális megoldás közül. A probléma egymozgásos változatának algoritmusa az eredeti probléma algoritmusává alakítható, ha többször meghívja, miközben minden egyes lépést a jelenlegi konfigurációra alkalmaz, amíg a végsőt el nem éri. Ezzel szemben az eredeti probléma bármely algoritmusa az egymozgásos verzió algoritmusává alakítható úgy, hogy a kimenetet az első lépésre csonkolja.

Példák

A leíráshoz illő jól ismert rejtvények olyan mechanikus rejtvények, mint a Rubik-kocka , a Hanoi-tornyok és a 15 rejtvény . A peg pasziánsz egyszemélyes játéka , valamint számos logikai rejtvény , például a misszionáriusok és kannibálok problémája is szerepel . Ezek közös jellemzője, hogy lehet modellezni matematikailag , mint egy irányított gráf , amelyben a konfiguráció a csúcsai, és a mozog az íveket.

Mechanikus rejtvények

n -rejtvények

A Tizenöt rejtvény 80 egylapkás mozdulattal vagy legrosszabb esetben 43 többcsempés mozdulattal oldható meg. Az n -rejtvény általánosítása szempontjából az optimális megoldás megtalálásának problémája NP -nehéz . Ezért ismeretlen, de valószínűtlennek tűnik, hogy létezik -e gyakorlati Isten algoritmusa erre a problémára.

Hanoi tornyai

A Hanoi -tornyok rejtvényhez Isten algoritmusa ismert bármilyen számú lemezre. A lépések száma exponenciális a lemezek számában ( )${\ displaystyle 2^{n} -1}$ .

Rubik kocka

Richard Korf 1997 -ben publikált egy algoritmust, amely meghatározza a Rubik -kockát megoldó lépések minimális számát. Míg 1995 óta tudták, hogy a legrosszabb esetben 20 a megoldás lépéseinek alsó határa, 2010 -ben kiterjedt számítógépes számításokkal bebizonyosodott, hogy egyetlen konfiguráció sem igényel 20 lépésnél többet. Így a 20 éles felső határ az optimális megoldások hosszában. David Singmaster matematikus ezt a számot "elhamarkodottan sejtette", hogy 1980 -ban 20.

Megoldatlan játékok

Néhány jól ismert, nagyon korlátozott egyszerű szabályokkal és mozdulatokkal rendelkező játékban azonban soha nem határozták meg Isten nyerő stratégiáját. Ilyen például a társasjáték sakk és a Go . Mindkét játék rohamosan növekvő számú pozícióval rendelkezik minden mozdulattal. Az összes lehetséges pozíció ( csoportátmérő ), kb. 10 ¹⁵⁴ sakknál és 10 ¹⁸⁰ (19 × 19 -es táblán) Go esetében, túl nagy ahhoz, hogy nyers erő megoldást lehessen használni a jelenlegi számítástechnikával (hasonlítsa össze a most megoldottat) , nagy nehezen, Rubik -kocka csak kb4,3 × 10 ¹⁹ pozíció). Következésképpen Isten algoritmusának nyers erejű meghatározása ezekre a játékokra nem lehetséges. Noha sakk számítógépeket építettek, amelyek képesek legyőzni a legjobb emberi játékosokat is, nem számítják ki a játékot egészen a végéig. A Deep Blue például csak 11 lépést keresett előre (minden játékos lépését két lépésnek számítva), így a keresési terület csak 10 ¹⁷ -re csökkent . Ezt követően az egyes játékhelyzetek előnyeit értékelte az emberi játékból és tapasztalatokból származó szabályok szerint.

Még ez a stratégia sem lehetséges a Go -val. Amellett, hogy rengeteg pozíciót kell értékelni, eddig senki sem tudott sikeresen összeállítani egy egyszerű szabálykészletet a Go pozíció erősségének értékelésére, mint a sakk esetében. Az értékelési algoritmusok hajlamosak elemi hibákat elkövetni, így még korlátozott előretekintés esetén is, amikor a legerősebb ideiglenes pozíció megtalálására törekszünk, Isten algoritmusa nem volt lehetséges a Go számára.

Viszont a piszkozatokat (dáma), amelyek felületesen hasonlítanak a sakkhoz, régóta gyanítják, hogy szakértő gyakorlói "eljátszották". 2007 -ben Schaeffer és mtsai. ezt úgy bizonyította, hogy kiszámított egy adatbázist az összes pozícióból, tíz vagy kevesebb darabbal. Így Schaeffer Isten algoritmusával rendelkezik a végső játékhoz, és ezzel bizonyította, hogy minden tökéletesen játszott nyereményjáték döntetlennel végződik. Piszkozatok azonban csak5 × 10 ²⁰ pozíció és még kevesebb,A Schaeffer adatbázisában található 3,9 × 10 ¹³ sokkal könnyebben feltörhető probléma, és megegyezik a Rubik -kockával.

A feladványok halmazának nagysága nem határozza meg teljesen, hogy lehetséges -e Isten algoritmusa. A már megoldott Hanoi torony rejtvény tetszőleges darabszámú lehet, és a pozíciók száma exponenciálisan nő . Ennek ellenére a megoldás algoritmusa bármilyen méretű problémára alkalmazható, és mivel az algoritmus futási ideje a probléma, NP-nehéz. ${\ displaystyle 3^{n}}$${\ displaystyle O (2^{n})}$

Lásd még

• Oracle gép
• Isteni lépés
• Bizonyítékok a KÖNYVBŐL

Megjegyzések

Hivatkozások

• Baum, Eric B., Mi a gondolat? , MIT Press, 2004 ISBN  0262025485 .
• Davis, Darryl N.; Chalabi, T .; Berbank-Green, B., "Mesterséges élet, ügynökök és Go", Mohammadian, Masoud, New Frontiers in Computational Intelligence and Applications , 125.-139 . O. , IOS Press, 2000 ISBN  9051994761 .
• Fraser, Rober (szerk.); Hannah, W. (szerk.), The Draft Players 'Weekly Magazine , vol. 2, Glasgow: JH Berry, 1885.
• Joyner, David (2002). Kalandok csoportelméletben . Johns Hopkins Egyetemi Kiadó. ISBN 0-8018-6947-1.
• Moore, Cristopher; Mertens, Stephan, A számítás természete , Oxford University Press, 2011 ISBN  0191620807 .
• Rothenberg, Gadi, Katalízis, Isten algoritmusa és a zöld démon , Amsterdam University Press, 2009 ISBN  9056295896 .
• Schaeffer, Jonathan; Neil Burch, Yngvi Björnsson, Akihiro Kishimoto, Martin Müller, Robert Lake, Paul Lu, Steve Sutphen, "Dáma meg van oldva" , Science , vol. 317, sz. 58444, 1518–1522, 2007. szeptember 14.
• Singmaster, David, Notes on Rubik's Magic Cube , Penguin, 1981 ISBN  0-907395-00-7 .
• Singmaster, David, "A magyar" mágikus kocka "oktatási értéke", Proceedings of the Fourth International Congress on Mathematical Education , tartott Berkeley -ben, Kaliforniában, 1980. augusztus 10-16., 307-312. Oldal, Birkhauser Boston Inc, 1983 ISBN  978-0-8176-3082-9 .