Boží algoritmus

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 7. března 2022; kontroly vyžadují 2 úpravy .

Boží algoritmus  je koncept, který vznikl během diskuse o způsobech řešení Rubikovy kostky . Termín může být také použit ve vztahu k jiným permutačním hádankám . Algoritmus boha puzzle je jakýkoli algoritmus , který vytváří řešení hádanky obsahující minimální možný počet tahů (optimální řešení) počínaje libovolnou konfigurací.

Jeden z průkopníků matematické teorie Rubikovy kostky David Singmaster [1] popisuje vzhled termínu takto:

John Conway , jeden z předních světových skupinových teoretiků, poznamenal, že krychle se řídí takzvanými zákony zachování (neboli parity), což znamená, že některé pohyby jsou prostě nemožné. Conway nebo jeden z jeho kolegů z Cambridge definovali nejkratší cestu z jakéhokoli daného stavu zpět do počátečního stavu jako „Boží algoritmus“.

Původní text  (anglicky)[ zobrazitskrýt] John Conway, jeden z největších světových teoretiků, poznamenal, že kostka se řídí zákony zachování (neboli parity), což znamená, že některé pohyby prostě nejsou možné. Conway nebo jeden z jeho kolegů z Cambridge definovali nejkratší cestu z libovolné dané pozice zpět do výchozí pozice jako „Boží algoritmus“. — David Singmaster [2]

Definice

Boží algoritmus může existovat pro hádanky s konečným počtem možných konfigurací as konečnou sadou "pohybů" povolených v každé konfiguraci, které převádějí současnou konfiguraci do jiné. Termín "vyřešit hádanku" znamená označit sekvenci pohybů, které převedou počáteční konfiguraci do nějaké konečné konfigurace. Optimálním řešením hádanky je označit nejkratší sekvenci tahů k vyřešení hádanky. Optimálních řešení může být několik.

Mezi významné hádanky, které spadají pod tuto definici, patří Rubikova kostka , Hanojská věž , Hra 15 , Chip Solitaire , různé problémy s transfuzí a přepravou („ Vlk, koza a zelí “). Společné pro všechny tyto hádanky je, že je lze popsat jako graf , jehož vrcholy jsou všechny možné konfigurace hádanky a hrany jsou možné přechody mezi nimi („tahy“).

V mnoha takových hádankách se konečná konfigurace implicitně předpokládá, například v „tagech“ - uspořádaném uspořádání kostí, pro Rubikovu kostku - stejné barvy tváří. V těchto případech "sestavení puzzle" znamená, že pro libovolnou počáteční konfiguraci je nutné specifikovat sekvenci pohybů vedoucí k pevné konečné konfiguraci.

Algoritmus vyřeší hádanku, pokud vezme jako vstup libovolnou dvojici počátečních a konečných konfigurací (nebo pouze počáteční konfiguraci, pokud je konečná konfigurace pevná) a jako výsledek vrátí sekvenci tahů, které převedou počáteční konfiguraci do konečné ( pokud taková sekvence existuje, jinak algoritmus hlásí nemožnost řešení). Optimální řešení obsahuje minimální možný počet tahů.

Boží algoritmus (pro danou hádanku) je pak algoritmus, který řeší hádanku a najde alespoň jedno optimální řešení pro libovolnou dvojici konfigurací.

Někteří autoři se domnívají, že Boží algoritmus by měl být také praktický , tj. používat přiměřené množství paměti a dokončit jej v rozumném čase.

Nechť G je permutační hlavolamová skupina (s danou generující množinou), v vrchol Cayleyova grafu G . Najděte účinný a praktický algoritmus pro určení cesty z v do vrcholu v 0 spojeného s neutrálním prvkem, jehož délka je rovna vzdálenosti od v do v 0 . [...] Tento algoritmus se nazývá Boží algoritmus .

Původní text  (anglicky)[ zobrazitskrýt] Nechť G je skupina permutační hádanky (s pevnou generující množinou) a nechť v je vrchol v Cayleyově grafu G. Najděte efektivní, praktický algoritmus pro určení cesty z v do vrcholu v 0 spojeného s identitou mající délku rovnou vzdálenosti od v do v 0 . [...] Tento algoritmus se nazývá Boží algoritmus . – David Joyner [3]

Praktičnost lze chápat různými způsoby. Existují tedy počítačové programy, které umožňují najít optimální řešení pro libovolnou konfiguraci Rubikovy kostky v rozumném čase [4] . Podobný úkol pro kostku 4×4×4 přitom zůstává v tuto chvíli prakticky nerealizovatelný [5] [6] [7] . Pro některé hádanky existuje strategie, která umožňuje podle jednoduchých pravidel určit optimální řešení ručně, bez pomoci počítače.

Alternativní definice Božího algoritmu: Algoritmus není vyžadován k nalezení celé sekvence pohybů; místo toho stačí najít první tah optimálního řešení, který jej přiblíží k cíli a přenese jej do nové konfigurace. Obě definice jsou ekvivalentní: opětovné použití algoritmu na novou dvojici konfigurací opět najde tah optimálního řešení, což umožňuje získat celou sekvenci tahů optimálního řešení.

Boží číslo

Boží číslo dané hádanky je číslo n , takové, že existuje alespoň jedna konfigurace hádanky, jejíž optimální řešení se skládá z n tahů, a neexistuje žádná konfigurace, jejíž délka optimálního řešení přesahuje n . Jinými slovy, Boží číslo je nejmenší horní hranicí množiny délek optimálních řešení hádanek.

Boží číslo pro Rubikovu kostku 3x3x3 je 20 - to je průměr Cayleyho grafu skupiny Rubikovy kostky [8] .

Obecně (pro libovolnou permutační hádanku) se Boží číslo nerovná průměru Cayleyho grafu skupiny hlavolamů, ale excentricitě vrcholu odpovídající „složenému“ stavu hlavolamu.

Příklady

V březnu až dubnu 2012 bylo zjištěno, že číslo boha tříbarevné krychle je 15 FTM , 17 QTM nebo 14 STM (podle metriky STM se za otočení jakékoli střední vrstvy považuje také 1 otáčka ) [13] .

Viz také

Poznámky

  1. ↑ Historie Rubikovy kostky (nepřístupný odkaz) . Získáno 20. července 2013. Archivováno z originálu dne 4. září 2013. 
  2. ↑ Jerry Slocum, David Singmaster, Wei-Hwa Huang, Dieter Gebhardt, Geert Hellings. The Cube: The Ultimate Guide to the World's Bestseller Puzzle - Tajemství, příběhy, řešení . - 2009. - S. 26. - 142 s. - ISBN 978-1-57912-805-0 .
  3. ↑ David Joyner. Dobrodružství v teorii skupin: Rubikova kostka, Merlinův stroj a další matematické hračky . - 2008. - S. 149. - 328 s.  (nedostupný odkaz)
  4. ↑ Herbert Kociemba. Průzkumník kostek . Získáno 27. července 2013. Archivováno z originálu dne 4. září 2013.
  5. ↑ Větší rubiková kostka vázaná Archivováno 29. května 2014.
  6. ↑ Generátor algoritmu 4x4x4? (jako průzkumník kostek) . Získáno 26. července 2013. Archivováno z originálu dne 29. května 2014.
  7. ↑ Algoritmy 4x4 (nepřístupný odkaz) . Získáno 26. července 2013. Archivováno z originálu dne 29. května 2014. 
  8. ↑ Weisstein, Eric W. Boží číslo . Získáno 4. května 2020. Archivováno z originálu dne 21. února 2020.
  9. ↑ Rokicki, T.; Kociemba, H.; Davidson, M.; a Dethridge, J. Boží číslo je 20 . Datum přístupu: 19. července 2013. Archivováno z originálu 26. července 2013.  
  10. ↑ Rokicki, T. a Davidson, M. Boží číslo je 26 ve  čtvrtotáčkové metrice . Získáno 2. července 2015. Archivováno z originálu dne 7. července 2015.
  11. ↑ Jaap Scherphuis. Mini kostka, 2×2×2 Rubikova kostka . Získáno 21. července 2013. Archivováno z originálu dne 4. září 2013.  
  12. ↑ Jaap Scherphuis. Pyraminx (anglicky) . Získáno 21. července 2013. Archivováno z originálu 29. srpna 2013.  
  13. ↑ Některé výsledky 3barevné kostky . Doména fóra Cube. Získáno 29. července 2013. Archivováno z originálu dne 4. září 2013.
  14. ↑ A. Brüngger, A. Marzetta, K. Fukuda a J. Nievergelt, The parallel search bench ZRAM and its applications Archived 11 November 2017 at the Wayback Machine , Annals of Operations Research 90 (1999), pp. 45-63.
  15. ↑ Bruce Norskog. Puzzle Patnáct lze vyřešit ve 43 "tahech" . Doména fóra Cube (anglicky) (12. srpna 2010) . Získáno 20. července 2013. Archivováno z originálu dne 4. září 2013.  
  16. ↑ Daniel Ratner, Manfred K. Warmuth (1986). „Najít nejkratší řešení pro rozšíření N × N 15-puzzle je neřešitelné“ Archivováno 9. března 2012 na Wayback Machine . ve sborníku AAAI-86 . Národní konference o umělé inteligenci, 1986. s. 168-172.
  17. ↑ Carlos Rueda, „Optimální řešení hádanek Hanojských věží“ .

Odkazy