Isten algoritmus
Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2022. március 7-én felülvizsgált verziótól ; az ellenőrzések 2 szerkesztést igényelnek .Isten algoritmusa egy olyan fogalom, amely a Rubik-kocka megoldásának megvitatása során merült fel . A kifejezés más permutációs rejtvényekkel kapcsolatban is használható . A rejtvényisten algoritmus bármely olyan algoritmus , amely egy adott konfigurációból kiindulva a lehető legkisebb számú lépést tartalmazó rejtvénymegoldást készít (optimális megoldás).
A Rubik-kocka matematikai elméletének egyik úttörője , David Singmaster [1] a következőképpen írja le a kifejezés megjelenését:
John Conway , a világ egyik vezető csoportteoretikusa megjegyezte, hogy a kocka betartja az úgynevezett megmaradási (vagy paritási) törvényeket, ami azt jelenti, hogy bizonyos mozgások egyszerűen lehetetlenek. Vagy Conway, vagy valamelyik cambridge -i kollégája „Isten algoritmusaként” határozta meg a legrövidebb utat bármely adott állapotból a kiindulási állapotba.
Eredeti szöveg (angol)[ showelrejt] John Conway, a világ egyik legnagyobb teoretikus csoportja megfigyelte, hogy a kocka betartja az úgynevezett megmaradási (vagy paritási) törvényeket, ami azt jelenti, hogy bizonyos lépések egyszerűen nem lehetségesek. Vagy Conway, vagy valamelyik cambridge-i kollégája „Isten algoritmusaként” határozta meg a legrövidebb utat bármely adott pozícióból a kiindulási helyzetbe. – David Singmaster [2]Definíció
Isten algoritmusa létezhet olyan rejtvényeknél, amelyekben véges számú lehetséges konfiguráció van, és minden konfigurációban megengedett a „mozgatások” véges halmaza, amelyek az aktuális konfigurációt egy másikra fordítják. A „fejtsd meg a rejtvényt” kifejezés azt jelenti, hogy egy olyan mozdulatsort jelölünk, amely bizonyos kezdeti konfigurációt valamilyen végső konfigurációba visz. A rejtvény optimális megoldása az, hogy a legrövidebb mozdulatsort jelezzük a rejtvény megoldásához. Több optimális megoldás is lehet.
A definíció alá tartozó figyelemre méltó rejtvények közé tartozik a Rubik-kocka , a Hanoi-torony , a 15-ös játék , a Chip Solitaire , valamint a különféle transzfúziós és szállítási problémák (" Farkas, Kecske és Káposzta "). Ezekben a rejtvényekben közös, hogy gráfként írhatók le , amelynek csúcsai a rejtvény összes lehetséges konfigurációja, az élek pedig a köztük lévő lehetséges átmenetek („mozgatások”).
Sok ilyen rejtvényben a végső konfigurációt implicit módon feltételezik, például „címkékben” - a csontok rendezett elrendezésében egy Rubik-kocka esetében - az arcok azonos színűek. Ezekben az esetekben a "rejtvény összeállítása" azt jelenti, hogy egy tetszőleges kezdeti konfigurációhoz meg kell határozni egy rögzített végső konfigurációhoz vezető lépéssorozatot .
Az algoritmus megoldja a rejtvényt, ha bemenetként egy tetszőleges pár kezdeti és végső konfigurációt vesz (vagy csak a kezdeti konfigurációt, ha a végső konfiguráció rögzített), és ennek eredményeként egy olyan mozdulatsort ad vissza, amely átviszi a kezdeti konfigurációt a végső konfigurációba ( ha létezik ilyen sorozat, ellenkező esetben az algoritmus a megoldás lehetetlenségét jelzi). Az optimális megoldás a lehető legkisebb lépésszámot tartalmazza.
Ekkor Isten algoritmusa (egy adott rejtvényhez) egy olyan algoritmus, amely megoldja a rejtvényt, és talál legalább egy optimális megoldást tetszőleges konfigurációpárra.
Egyes szerzők úgy vélik, hogy Isten algoritmusának praktikusnak is kell lennie , azaz ésszerű mennyiségű memóriát kell használnia, és ésszerű időn belül kell befejeznie.
Legyen G egy permutációs rejtvénycsoport ( adott generátorkészlettel), v G Cayley-gráfjának csúcsa . Keressen egy hatékony , praktikus algoritmust a v - tól a v 0 csúcshoz vezető út meghatározására , amely olyan semleges elemhez tartozik , amelynek hossza egyenlő a v - v 0 távolsággal . [...] Ezt az algoritmust Isten algoritmusának nevezik .
Eredeti szöveg (angol)[ showelrejt] Legyen G egy permutációs rejtvény csoportja (rögzített generátorkészlettel), és v egy csúcsa G Cayley-gráfjában. Keressen egy hatékony, praktikus algoritmust a v-ből az azonossághoz társított v 0 csúcshoz vezető út meghatározására. amelynek hossza egyenlő a v és v 0 távolsággal . [...] Ezt az algoritmust Isten algoritmusának nevezik . – David Joyner [3]A gyakorlatiasságot többféleképpen is meg lehet érteni. Léteznek tehát olyan számítógépes programok, amelyek lehetővé teszik a Rubik-kocka tetszőleges konfigurációjának optimális megoldását ésszerű időn belül [4] . Ugyanakkor egy hasonló feladat egy 4×4×4-es kocka esetében jelenleg gyakorlatilag megvalósíthatatlan [5] [6] [7] . Néhány rejtvényhez létezik egy stratégia, amely egyszerű szabályok szerint lehetővé teszi az optimális megoldás manuális meghatározását, számítógép segítsége nélkül.
Isten algoritmusának alternatív meghatározása: Az algoritmus nem szükséges a mozdulatok teljes sorozatának megtalálásához; ehelyett elegendő megtalálni az optimális megoldás első lépését, amely közelebb viszi a célhoz és áthelyezi egy új konfigurációba. A két definíció ekvivalens: az algoritmus újbóli alkalmazása egy új konfigurációpárra ismét megtalálja az optimális megoldás mozgását, ami lehetővé teszi az optimális megoldás teljes mozgássorozatának megszerzését.
Isten száma
Egy adott rejtvény istenszáma egy n szám , úgy, hogy a feladványnak van legalább egy olyan konfigurációja, amelynek optimális megoldása n lépésből áll, és nincs olyan konfiguráció, amelynek optimális megoldásának hossza meghaladja az n -t. . Más szavakkal, Isten száma a legkisebb felső korlát a rejtvénykonfigurációk optimális megoldásainak hosszkészletében.
A 3x3x3-as Rubik-kocka istenszáma 20 - ez a Rubik-kockacsoport Cayley-gráfjának átmérője [8] .
Általában (egy tetszőleges permutációs rejtvénynél) Isten száma nem egyenlő a rejtvénycsoport Cayley-gráfjának átmérőjével, hanem a rejtvény „összeállított” állapotának megfelelő csúcs excentricitásával .
Példák
- Egy 3 × 3 × 3 méretű Rubik-kockát mindig legfeljebb 20 mozdulattal lehet megoldani (a 6 lap bármelyikének fordulatát 90 vagy 180 fokkal lépésenként számolva). Ismertek olyan konfigurációk , amelyek összeszereléséhez legalább 20 mozdulat szükséges. Így a Rubik-kocka "istenszáma" 20 [9] .
- Ha csak 90 fokos fordulat megengedett (de nem 180 fok, ami lehetséges, de két lépésnek számít), a Rubik-kocka "istenszáma" 26 [10] .
- Egy 2 × 2 × 2-es kocka Istenszáma 11 lépés, ha egy 180°-os fordulatot 1 lépésnek számítanak, vagy 14 lépést, ha egy 180°-os fordulatot 2 lépésnek számítanak. A 2 × 2 × 2-es kocka kis számú ( 3 674 160 ) konfigurációja lehetővé tette Isten algoritmusának kiszámítását (minden konfigurációhoz optimális megoldás formájában) még a 80-as években [11] .
- Egy háromszínű kocka, amelynek ellentétes oldalai azonos színűek. A háromszínű kocka konfigurációinak száma
- A " tizenöt " a legrosszabb esetben 80 "rövid" [14] vagy 43 "hosszú" [15] lépésben oldható meg (a "rövid" lépések alatt az egyes lapkák mozgatását értjük, a "hosszú" lépéseken pedig - egész sorok mozgatását. 1, 2 vagy 3 csont). Az általánosított címkék esetében (több mint 15 csempével) a legrövidebb megoldás megtalálásának problémája NP-teljes [16] .
- A Hanoi Tower esetében Isten algoritmusa létezik tetszőleges számú lemezre, de a lemezek hozzáadásával a lépések száma exponenciálisan nő [17] .
Lásd még
Jegyzetek
- ↑ A Rubik-kocka története (elérhetetlen link) . Letöltve: 2013. július 20. Az eredetiből archiválva : 2013. szeptember 4..
- ↑ Jerry Slocum, David Singmaster, Wei-Hwa Huang, Dieter Gebhardt, Geert Hellings. A kocka: Végső útmutató a világ legkeresettebb rejtvényéhez – Titkok, történetek, megoldások . - 2009. - S. 26. - 142 p. - ISBN 978-1-57912-805-0 .
- ↑ David Joyner. Kalandok a csoportelméletben: Rubik-kocka, Merlin gépe és egyéb matematikai játékok . - 2008. - S. 149. - 328 p. (nem elérhető link)
- ↑ Herbert Kociemba. Cube Explorer . Letöltve: 2013. július 27. Az eredetiből archiválva : 2013. szeptember 4..
- ↑ Nagyobb rubikkocka kötve Archivált 2014. május 29.
- ↑ 4x4x4 algoritmus generátor? (mint a cube explorer) . Letöltve: 2013. július 26. Az eredetiből archiválva : 2014. május 29.
- ↑ 4x4 algoritmusok (elérhetetlen link) . Letöltve: 2013. július 26. Az eredetiből archiválva : 2014. május 29.
- ↑ Weisstein, Eric W. Isten száma . Letöltve: 2020. május 4. Az eredetiből archiválva : 2020. február 21.
- ↑ Rokicki, T.; Kociemba, H.; Davidson, M.; és Dethridge, J. Isten száma 20 . Hozzáférés dátuma: 2013. július 19. Az eredetiből archiválva : 2013. július 26.
- ↑ Rokicki, T. és Davidson, M. Isten száma 26 a negyedforduló metrikájában . Letöltve: 2015. július 2. Az eredetiből archiválva : 2015. július 7..
- ↑ Jaap Scherphuis. Mini kocka, a 2×2×2 Rubik- kocka . Letöltve: 2013. július 21. Az eredetiből archiválva : 2013. szeptember 4..
- ↑ Jaap Scherphuis. Pyraminx (angol) . Letöltve: 2013. július 21. Az eredetiből archiválva : 2013. augusztus 29..
- ↑ Néhány 3 színű kocka eredmény . A Cube fórum domainje. Letöltve: 2013. július 29. Az eredetiből archiválva : 2013. szeptember 4..
- ↑ A. Brüngger, A. Marzetta, K. Fukuda and J. Nievergelt, The parallel search bench ZRAM and its applications Archived 2017 November 11 at the Wayback Machine , Annals of Operations Research 90 (1999), pp. 45-63.
- ↑ Bruce Norskog. A Tizenöt Rejtvény 43 „mozdulattal” megoldható . A Cube fórum domainje (angol) (2010. augusztus 12.) . Letöltve: 2013. július 20. Az eredetiből archiválva : 2013. szeptember 4..
- ↑ Daniel Ratner, Manfred K. Warmuth (1986). "A legrövidebb megoldást találni a 15 rejtvényből álló N × N bővítményhez nehéz feladat" Archiválva : 2012. március 9., a Wayback Machine webhelyen . a Proceedings AAAI-86 . Országos Mesterséges Intelligencia Konferencia, 1986. pp. 168-172.
- ↑ Carlos Rueda, "Optimális megoldás a Towers of Hanoi Puzzle-hoz" .
Linkek
- Rubik-kocka: Roham az erősség ellen (Konstantin Knop)
| Speedcubing | |
|---|---|
| Szervezet |
|
| Sportfelszerelés | |
| Fogalmak |
|
| Világbajnokságok | |