Optimální řešení pro Rubiks Cube - Optimal solutions for Rubiks Cube - Wikipedia

Míchaná Rubikova kostka

Optimální řešení pro Rubikova kostka odkazují na řešení, která jsou nejkratší. Existují dva běžné způsoby, jak měřit délku řešení. První je spočítat počet čtvrtotočků. Druhým je spočítat počet zákrutů vnější vrstvy zvaných „otočení obličeje“. Tah k otočení vnější vrstvy o dvě čtvrtiny (90 °) otáčky ve stejném směru by se počítal jako dva tahy v metrice čtvrtotáčkové (QTM), ale jako jedno otočení v metrické ploše (FTM nebo HTM) ", nebo OBTM" Outer Block Turn Metric ").^[1]

Minimální počet otočení obličeje potřebný k vyřešení jakékoli instance Rubikovy kostky je 20,^[2] a minimální počet čtvrtotáčků je 26.^[3] Tato čísla jsou také průměry odpovídajících Cayleyovy grafy z Rubikova kostka. V STM (slice turn metric) to není známo.

Je jich mnoho algoritmy vyřešit zakódovaný Rubikovy kostky. Algoritmus, který řeší kostku v minimálním počtu tahů, je znám jako Boží algoritmus.

Přesuňte notaci

Pro označení sledu tahů na Rubikově kostce 3 × 3 × 3 používá tento článek „Singmaster notation“,^[4] který vyvinul David Singmaster.

Písmena L, R, F, B, U a D označují o čtvrt otáčky ve směru hodinových ručiček levou, pravou, přední, zadní, horní a dolní tvář. Poloviční otáčky jsou označeny připojením a 2. Čtvrtá otáčka proti směru hodinových ručiček je označena připojením a hlavní symbol ( ′ ).

Písmena M, S a E se používají k označení otáčení střední vrstvy. M představuje otočení vrstvy mezi plochami R a L o 1 čtvrtinu otočení shora dolů. S představuje otáčení vrstvy mezi plochami F a B o 1 čtvrt otáčky ve směru hodinových ručiček, při pohledu zepředu. E představuje otočení vrstvy mezi plochami U a D o 1 čtvrtinu otáčení ve směru hodinových ručiček zleva doprava. Stejně jako u běžných zatáček, 2 znamená dvojité otočení a prime (') označuje čtvrt otáčky proti směru hodinových ručiček.^[5]

Písmena X, Y a Z se používají k označení rotace krychle. X znamená rotaci krychle o 90 stupňů dopředu. Y znamená rotaci krychle doleva o 90 stupňů. Z znamená rotaci krychle ve směru hodinových ručiček o 90 stupňů. Tyto rotace krychle se používají v algoritmech, aby byly algoritmy plynulejší a rychlejší. Stejně jako u běžných zatáček, 2 znamená poloviční rotaci a prime (') označuje čtvrtinovou rotaci v opačném směru. Všimněte si, že tato písmena jsou místo toho obvykle malá.

Dolní hranice

To lze dokázat počítáním argumentů, že existují pozice, které k vyřešení vyžadují alespoň 18 tahů. Chcete-li to ukázat, nejprve spočítejte počet pozic krychle, které existují celkem, poté spočítejte počet pozic dosažitelných pomocí maximálně 17 tahů počínaje od vyřešené krychle. Ukazuje se, že druhé číslo je menší.

Tento argument nebyl vylepšen po mnoho let. Také to není konstruktivní důkaz: nevykazuje konkrétní polohu, která potřebuje tolik tahů. to bylo domnělý že tzv superflip by byla pozice, která je velmi obtížná. Rubikova kostka je ve vzoru superflipu, když je každý rohový kus ve správné poloze, ale každý okrajový kus je nesprávně orientován.^[6] V roce 1992 našel řešení superflipu s 20 otočeními obličeje Dik T. Winter, z nichž minimalitu v roce 1995 prokázal Michael Reid, poskytující novou dolní mez pro průměr skupiny krychlí. Také v roce 1995 našel Michael Reid řešení superflipu ve 24 čtvrtotáčkách, jehož minimálnost prokázal Jerry Bryan.^[6] V roce 1998 byla nalezena nová pozice, jejíž řešení vyžaduje více než 24 čtvrtletních obratů. Pozice, která se nazývala „superflip složený se čtyřmi body“, vyžaduje 26 čtvrtotáčků.^[7]

Horní hranice

První horní hranice byla založena na „lidských“ algoritmech. Kombinací nejhorších scénářů pro každou část těchto algoritmů bylo zjištěno, že typická horní hranice je kolem 100.

Snad první konkrétní hodnotou pro horní hranici bylo 277 tahů zmíněných David Singmaster počátkem roku 1979. Jednoduše spočítal maximální počet tahů požadovaný jeho algoritmem řešení krychle.^[8][9] Později to Singmaster oznámil Elwyn Berlekamp, John Conway, a Richard K. Guy přišel s jiným algoritmem, který trval maximálně 160 tahů.^[8][10] Brzy poté Cambridgeovi kubisté z Conwaye uvedli, že kostku lze obnovit maximálně 94 pohyby.^[8][11]

Thistlethwaitův algoritmus

Průlom, známý jako „sestup skrz vnořené podskupiny“, našel Morwen Thistlethwaite; detaily Thistlethwaitův algoritmus byly publikovány v Scientific American v roce 1981 Douglas Hofstadter. Přístupy ke krychli, které vedly k algoritmům s velmi malým počtem tahů, jsou založeny na teorie skupin a při rozsáhlých počítačových vyhledáváních. Thistlethwaiteova myšlenka byla rozdělit problém na dílčí problémy. Tam, kde algoritmy až do tohoto bodu problém rozdělily pohledem na části krychle, které by měly zůstat pevné, rozdělil jej omezením typu pohybů, které lze provést. Zejména rozdělil skupina krychle do následujícího řetězce podskupin:

• ${ displaystyle G_ {0} = jazyk L, R, F, B, U, D rangle}$
• ${ displaystyle G_ {1} = jazyk L, R, F, B, U ^ {2}, D ^ {2} rangle}$
• ${ displaystyle G_ {2} = langle L, R, F ^ {2}, B ^ {2}, U ^ {2}, D ^ {2} rangle}$
• ${ displaystyle G_ {3} = langle L ^ {2}, R ^ {2}, F ^ {2}, B ^ {2}, U ^ {2}, D ^ {2} rangle}$
• ${ displaystyle G_ {4} = {1 }}$

Dále připravil stoly pro každou pravici coset mezery ${ displaystyle G_ {i + 1} setminus G_ {i}}$. U každého prvku našel posloupnost tahů, které jej přenesly do další menší skupiny. Po těchto přípravách pracoval následovně. Náhodná krychle je ve skupině obecných krychlí ${ displaystyle G_ {0}}$. Dále našel tento prvek vpravo coset prostor ${ displaystyle G_ {1} setminus G_ {0}}$. Aplikoval odpovídající postup na krychli. Tím se dostal do krychle dovnitř ${ displaystyle G_ {1}}$. Dále vyhledal postup, který vezme kostku ${ displaystyle G_ {2}}$, vedle ${ displaystyle G_ {3}}$ a nakonec ${ displaystyle G_ {4}}$.

Střední stav Rubikovy kostky v Kociembově algoritmu. Libovolný stát z G₁ bude mít symboly „+“ a „-“, jak je znázorněno.^[12]

Ačkoli celá skupina krychlí ${ displaystyle G_ {0}}$ je velmi velký (~ 4,3 × 10¹⁹), pravé mezery coset ${ displaystyle G_ {1} setminus G_ {0}, G_ {2} setminus G_ {1}, G_ {3} setminus G_ {2}}$ a ${ displaystyle G_ {3}}$ jsou mnohem menší ${ displaystyle G_ {2} setminus G_ {1}}$ je největší a obsahuje pouze 1082565 prvků. Počet tahů vyžadovaných tímto algoritmem je součtem největšího procesu v každém kroku.

Zpočátku Thistlethwaite ukázal, že jakoukoli konfiguraci lze vyřešit maximálně 85 tahy. V lednu 1980 vylepšil svou strategii, aby přinesl maximálně 80 tahů. Později téhož roku snížil počet na 63 a poté znovu na 52.^[8] Vyčerpávajícím prohledáváním prostorů cosetů bylo později zjištěno, že nejhorší možný počet tahů pro každou fázi byl 7, 10, 13 a 15, což dalo nanejvýš 45 tahů.^[13] Toto je implementace Thistlewaitova algoritmu v Javascript.^[14]

Kociembův algoritmus

Thistlethwaiteův algoritmus byl vylepšen o Herbert Kociemba v roce 1992. Snížil počet přechodných skupin pouze na dvě:

• ${ displaystyle G_ {0} = jazyk U, D, L, R, F, B rangle}$
• ${ displaystyle G_ {1} = jazyk U, D, L ^ {2}, R ^ {2}, F ^ {2}, B ^ {2} rangle}$
• ${ displaystyle G_ {2} = {1 }}$

Stejně jako u Thistlethwaitův algoritmus, prohledával by pravý prostor cosetu ${ displaystyle G_ {1} setminus G_ {0}}$ vzít kostku do skupiny ${ displaystyle G_ {1}}$. Dále hledal optimální řešení pro skupinu ${ displaystyle G_ {1}}$. Hledání v ${ displaystyle G_ {1} setminus G_ {0}}$ a ${ displaystyle G_ {1}}$ oba byly provedeny metodou ekvivalentní k IDA *. Hledání v ${ displaystyle G_ {1} setminus G_ {0}}$ potřebuje maximálně 12 tahů a hledání ${ displaystyle G_ {1}}$ maximálně 18 tahů, jak ukázal Michael Reid v roce 1995. Také generováním neoptimálních řešení, která seskupují krychli ${ displaystyle G_ {1}}$ a hledám krátká řešení v ${ displaystyle G_ {1}}$, obvykle se získávají mnohem kratší celková řešení. Při použití tohoto algoritmu se řešení obvykle nacházejí u méně než 21 tahů, ačkoli neexistuje žádný důkaz, že to tak bude vždy.

V roce 1995 Michael Reid prokázal, že pomocí těchto dvou skupin lze každou pozici vyřešit maximálně v 29 otočkách obličeje nebo ve 42 čtvrtinách otočení. Tento výsledek vylepšil Silviu Radu v roce 2005 na 40.

Na první pohled se tento algoritmus zdá být neprakticky neefektivní - Pokud ${ displaystyle G_ {0}}$obsahuje 18 možných tahů (každý tah, jeho vrchol a jeho rotace o 180 stupňů), který opouští ${ displaystyle 18 ^ {12}}$(Více než 1 kvadrillion) stavů krychle, které mají být prohledány. I s heuristický -jako počítačový algoritmus podobný IDA *, což ji může značně zúžit, prohledávání mnoha států pravděpodobně není praktické. Aby tento problém vyřešil, Kociemba vymyslel vyhledávací tabulku, která poskytuje přesnou heuristiku pro ${ displaystyle G_ {0}}$.^[15] Když je třeba dosáhnout přesného počtu tahů ${ displaystyle G_ {1}}$je k dispozici, hledání se stává prakticky okamžitým - stačí vygenerovat pouze 18 stavů krychle pro každý z 12 tahů a zvolit pokaždé ten s nejnižší heuristikou. To umožňuje druhou heuristiku, to pro ${ displaystyle G_ {1}}$, abychom byli méně přesní a stále umožňovali výpočet řešení v rozumném čase na moderním počítači.

Korfův algoritmus

Použití těchto skupinových řešení v kombinaci s počítačovým vyhledáváním obecně rychle poskytne velmi krátká řešení. Ale tato řešení nemusí vždy obsahovat záruku jejich minimality. Abychom konkrétně hledali minimální řešení, byl zapotřebí nový přístup.

V roce 1997 Richard Korf^[16] oznámil algoritmus, kterým optimálně vyřešil náhodné instance krychle. Z deseti náhodných kostek, které udělal, žádná nevyžadovala více než 18 otočení obličeje. Metoda, kterou použil, se nazývá IDA * a je popsán v jeho příspěvku „Hledání optimálních řešení Rubikovy kostky pomocí databází vzorů“. Korf popisuje tuto metodu následovně

IDA * je vyhledávání do hloubky, které hledá stále delší řešení v řadě iterací, pomocí heuristiky s dolní hranicí k ořezávání větví, jakmile dolní hranice na jejich délce překročí aktuální vázanou iteraci.

Funguje to zhruba následovně. Nejprve identifikoval řadu dílčích problémů, které jsou dostatečně malé, aby je bylo možné optimálně vyřešit. Použil:

1. Kostka se omezovala pouze na rohy, nedívala se na hrany
2. Kostka omezena pouze na 6 hran, nehledě na rohy ani na ostatní hrany.
3. Kostka omezena na dalších 6 hran.

Je zřejmé, že počet tahů potřebných k vyřešení kteréhokoli z těchto dílčích problémů je dolní mez pro počet tahů potřebných k vyřešení celé krychle.

Vzhledem k náhodný kostka C, je řešena jako iterativní prohlubování. Nejprve se vygenerují všechny kostky, které jsou výsledkem použití 1 tahu na ně. To je C * F, C * U, ... Dále z tohoto seznamu jsou generovány všechny kostky, které jsou výsledkem použití dvou tahů. Pak tři tahy a tak dále. Pokud se kdykoli zjistí kostka, která potřebuje příliš mnoho tahů založených na horních mezích, aby byla stále optimální, může být ze seznamu vyloučena.

I když tohle algoritmus vždy najde optimální řešení, neexistuje analýza nejhorších případů. Není známo, kolik tahů může tento algoritmus potřebovat. Implementaci tohoto algoritmu najdete zde.^[17]

Další vylepšení a hledání Božího čísla

V roce 2006 Silviu Radu dále zdokonalil své metody, aby dokázal, že každou pozici lze vyřešit v maximálně 27 otočkách obličeje nebo 35 čtvrtotáčkách.^[18] Daniel Kunkle a Gene Cooperman v roce 2007 použili a superpočítač ukázat, že všechny nevyřešené kostky lze vyřešit ne více než 26 tahy (v metrice otočení obličeje). Místo toho, aby se pokusil explicitně vyřešit každou z miliard variací, byl počítač naprogramován tak, aby přenesl krychli do jednoho z 15 752 stavů, z nichž každý mohl být vyřešen během několika dalších tahů. U všech bylo prokázáno, že jsou řešitelné ve 29 tazích, přičemž většina z nich byla řešitelná v 26. Tých, které se původně nepodařilo vyřešit v 26 tazích, bylo poté vyřešeno výslovně a ukázalo se, že i ty lze vyřešit v 26 tazích.^[19][20]

Tomáš Rokicki ve výpočtovém důkazu z roku 2008 uvedl, že všechny nevyřešené kostky lze vyřešit na 25 tahů nebo méně.^[21] To bylo později sníženo na 23 tahů.^[22] V srpnu 2008 Rokicki oznámil, že má důkaz pro 22 tahů.^[23]

Nakonec v roce 2010 předali finále Tomáš Rokicki, Herbert Kociemba, Morley Davidson a John Dethridge počítačem podporovaný důkaz že všechny pozice krychle lze vyřešit maximálně 20 otočením obličeje.^[2]V roce 2009 Tomáš Rokicki dokázal, že k vyřešení jakékoli míchané kostky stačí 29 tahů v metrice čtvrtotočky.^[24] A v roce 2014 Tomas Rokicki a Morley Davidson dokázali, že maximální počet čtvrtotáčků potřebných k vyřešení krychle je 26.^[3]

Metriky turn-turn a quarter-turn se liší v povaze jejich antipodů.^[3]Antipod je míchaná kostka, která je maximálně daleko od vyřešení, která vyžaduje maximální počet tahů k vyřešení. V metrice půl otáčky s maximálním počtem 20 existují stovky milionů takových pozic. V metrice čtvrtotočky je známá pouze jedna poloha (a její dvě rotace), která vyžaduje maximálně 26 tahů. Navzdory značnému úsilí nebyly nalezeny žádné další polohy o čtvrt otáčky na vzdálenost 26.^{[potřebuje aktualizaci ]} I ve vzdálenosti 25 je známo, že existují pouze dvě polohy (a jejich rotace).^{[3][Citace je zapotřebí ]} Ve vzdálenosti 24 existuje asi 150 000 pozic.

Reference

Další čtení

• Singmaster, David (1981). Poznámky k Rubikově magické kostce. Vydavatelé Enslow.CS1 maint: ref = harv (odkaz)

externí odkazy

• Jak vyřešit Rubikovu kostku, článek Wikibooks, který poskytuje přehled několika algoritmů, které jsou natolik jednoduché, že si je lidé mohou zapamatovat. Takové algoritmy však obvykle neposkytují optimální řešení, které využívá pouze minimální možný počet tahů.