Jumalan algoritmi

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 7. maaliskuuta 2022 tarkistetusta versiosta . tarkastukset vaativat 2 muokkausta .

Jumalan algoritmi  on käsite, joka syntyi keskustelun aikana Rubikin kuution ratkaisutavoista . Termiä voidaan käyttää myös muiden permutaatiopulmien yhteydessä . Palapelijumala-algoritmi on mikä tahansa algoritmi , joka tuottaa pulmaratkaisun, joka sisältää mahdollisimman vähän liikkeitä (optimaalinen ratkaisu) mistä tahansa tietystä konfiguraatiosta alkaen.

Yksi Rubikin kuution matemaattisen teorian pioneereista , David Singmaster [1] , kuvaa termin ulkoasua seuraavasti:

John Conway , yksi maailman johtavista ryhmäteoreetikoista, huomautti, että Kuutio noudattaa niin kutsuttuja säilymislakeja (tai pariteettilakeja), mikä tarkoittaa, että jotkut liikkeet ovat yksinkertaisesti mahdottomia. Joko Conway tai yksi hänen kollegoistaan ​​Cambridgessa määritteli lyhimmän polun mistä tahansa tietystä tilasta takaisin alkutilaan "Jumalan algoritmiksi".

Alkuperäinen teksti  (englanniksi)[ näytäpiilottaa] John Conway, yksi maailman suurimmista teoreetikoista, havaitsi, että kuutio noudattaa niin kutsuttuja säilymislakeja (tai pariteettilakeja), mikä tarkoittaa, että jotkut liikkeet eivät yksinkertaisesti ole mahdollisia. Joko Conway tai yksi hänen kollegoistaan ​​Cambridgessa määritteli lyhimmän reitin mistä tahansa tietystä paikasta takaisin lähtöasentoon "Jumalan algoritmiksi". - David Singmaster [2]

Määritelmä

Jumalan algoritmi voi olla olemassa arvoituksille, joissa on rajallinen määrä mahdollisia kokoonpanoja ja rajallinen joukko "siirtoja", jotka ovat sallittuja jokaisessa kokoonpanossa, jotka muuttavat nykyisen kokoonpanon toiseksi. Termi "ratkaise palapeli" tarkoittaa liikesarjan osoittamista, joka vie alkukokoonpanon johonkin lopulliseen kokoonpanoon. Optimaalinen ratkaisu pulmaan on ilmoittaa lyhin siirtosarja pulman ratkaisemiseksi. Optimaalisia ratkaisuja voi olla useita.

Merkittäviä tämän määritelmän piiriin kuuluvia pulmia ovat Rubikin kuutio , Hanoin torni , 15-peli , Chip Solitaire , erilaiset verensiirto- ja kuljetusongelmat (" Susi, vuohi ja kaali "). Kaikille näille arvoituksille yhteistä on, että niitä voidaan kuvata graafina , jonka kärjet ovat kaikki mahdolliset pulman konfiguraatiot ja reunat ovat mahdollisia siirtymiä niiden välillä ("liikkuja").

Monissa tällaisissa pulmapeleissä lopullinen konfiguraatio oletetaan epäsuorasti esimerkiksi "tunnisteissa" - järjestetyssä luiden järjestelyssä Rubikin kuutiolle - kasvojen sama väri. Näissä tapauksissa "palapelin kokoaminen" tarkoittaa, että mielivaltaista alkukokoonpanoa varten on määriteltävä siirtosarja, joka johtaa kiinteään lopulliseen kokoonpanoon.

Algoritmi ratkaisee pulman, jos se ottaa syötteeksi mielivaltaisen parin alku- ja lopullisia kokoonpanoja (tai vain alkuperäisen konfiguraation, jos lopullinen konfiguraatio on kiinteä) ja palauttaa tuloksena siirtosarjan, joka siirtää alkuperäisen konfiguraation lopulliseen ( jos tällainen sekvenssi on olemassa, muuten algoritmi ilmoittaa ratkaisun mahdottomuudesta). Optimaalinen ratkaisu sisältää mahdollisimman vähän liikkeitä.

Sitten Jumalan algoritmi (tietylle pulmalle) on algoritmi, joka ratkaisee pulman ja löytää ainakin yhden optimaalisen ratkaisun mielivaltaiselle kokoonpanoparille.

Jotkut kirjoittajat uskovat, että Jumalan algoritmin tulisi myös olla käytännöllinen , eli käyttää kohtuullista muistia ja suorittaa kohtuullisessa ajassa.

Olkoon G permutaatiopulmaryhmä (tietyllä generointijoukolla), v G : n Cayley-graafin huippu . Etsi tehokas , käytännöllinen algoritmi polun määrittämiseksi v :stä kärkeen v 0 , joka liittyy neutraaliin elementtiin, jonka pituus on yhtä suuri kuin etäisyys v :stä v 0 :aan . [...] Tätä algoritmia kutsutaan Jumalan algoritmiksi .

Alkuperäinen teksti  (englanniksi)[ näytäpiilottaa] Olkoon G permutaatiopulman ryhmä (kiinteällä generointijoukolla) ja olkoon v G:n Cayley-graafin huippu. Etsi tehokas, käytännöllinen algoritmi polun määrittämiseksi v:stä identiteettiin liittyvään kärkipisteeseen v 0 jonka pituus on yhtä suuri kuin etäisyys v:stä v 0 :aan . [...] Tätä algoritmia kutsutaan Jumalan algoritmiksi . – David Joyner [3]

Käytännön voi ymmärtää eri tavoin. Joten on olemassa tietokoneohjelmia, joiden avulla voidaan löytää optimaalinen ratkaisu mielivaltaiseen Rubikin kuution konfiguraatioon kohtuullisessa ajassa [4] . Samaan aikaan samanlainen tehtävä 4×4×4 kuutiolla on tällä hetkellä käytännössä mahdotonta [5] [6] [7] . Joillekin arvoituksille on olemassa strategia, jonka avulla yksinkertaisten sääntöjen mukaan optimaalinen ratkaisu voidaan määrittää manuaalisesti ilman tietokoneen apua.

Vaihtoehtoinen määritelmä Jumalan algoritmille: Algoritmia ei vaadita koko liikesarjan löytämiseen; Sen sijaan riittää, että löydetään optimaalisen ratkaisun ensimmäinen liike, joka tuo sen lähemmäksi tavoitetta ja siirtää sen uuteen kokoonpanoon. Kaksi määritelmää ovat samanarvoisia: soveltamalla algoritmia uudelleen uuteen konfiguraatiopariin löytää jälleen optimaalisen ratkaisun liikkeen, mikä mahdollistaa optimaalisen ratkaisun koko siirtosarjan saamisen.

Jumalan numero

Tietyn pulman jumalaluku on luku n , jolloin pulmalle on ainakin yksi konfiguraatio, jonka optimaalinen ratkaisu koostuu n liikkeestä, eikä ole konfiguraatiota, jonka optimaalisen ratkaisun pituus ylittää n . Toisin sanoen, Jumalan luku on pienin yläraja pulmakokoonpanojen optimaalisten ratkaisujen pituuksien joukossa.

3x3x3 Rubikin kuution jumalaluku on 20 - tämä on Rubikin kuutioryhmän Cayley-graafin halkaisija [ 8 ] .

Yleensä (mielivaltaiselle permutaatiopulmalle) Jumalan luku ei ole yhtä suuri kuin pulmaryhmän Cayley-graafin halkaisija, vaan pulmapelin "kootun" tilaa vastaavan kärjen epäkeskisyys .

Esimerkkejä

• 3  ×  3  × 3 Rubikin kuutio  voidaan aina ratkaista korkeintaan 20 liikkeellä (laskemalla minkä tahansa kuuden pinnan käännöksen 90 tai 180 astetta liikettä kohti). Tunnetaan konfiguraatioita , joiden kokoaminen vaatii vähintään 20 liikettä. Siten Rubikin kuution "jumalaluku" on 20 [9] .

• Jos sallitaan vain 90 asteen käännökset (mutta ei 180 astetta, jotka ovat mahdollisia, mutta lasketaan kahdeksi liikkeeksi), Rubikin kuution "jumalaluku" on 26 [10] .

• 2  ×  2  ×  2 nopan jumalanumero on 11 liikettä, jos 180°:n käännös lasketaan yhdeksi liikkeeksi, tai 14 liikettä, jos 180°:n käännös lasketaan kahdeksi liikkeeksi. Pieni ( 3 674 160 ) määrä 2  ×  2  ×  2 kuution konfiguraatioita mahdollisti Jumalan algoritmin laskemisen (optimaalisen ratkaisun muodossa kullekin konfiguraatiolle) jo 80-luvulla [11] .

• Meffertin jumalan pyramidin numero on 11 [12] .

• Kolmivärinen kuutio, jonka vastakkaiset sivut ovat samanvärisiä. Kolmivärisen kuution kokoonpanojen määrä on

Maalis-huhtikuussa 2012 havaittiin, että kolmivärisen kuution jumalan numero on 15 FTM , 17 QTM tai 14 STM ( STM- metriikan mukaan minkä tahansa keskikerroksen pyörimisen katsotaan olevan myös 1 kierros ) [13] .

• " Viisitoista " voidaan ratkaista 80 "lyhyellä" [14] tai 43 "pitkällä" [15] siirrolla pahimmassa tapauksessa ("lyhyillä" siirroilla tarkoitamme yksittäisten ruutujen siirtämistä ja "pitkillä" siirroilla - kokonaisten rivien siirtämistä 1, 2 tai 3 luuta). Yleistetyille tunnisteille (yli 15 ruutua) lyhimmän ratkaisun löytämisen ongelma on NP-täydellinen [16] .

• Hanoin tornille Jumalan algoritmi on olemassa mille tahansa määrälle levyjä, mutta levyjen lisäämisen myötä liikkeiden määrä kasvaa eksponentiaalisesti [17] .

Katso myös

• Tuomiopäivän algoritmi
• Graafin halkaisija
• Rubikin kuution matematiikka

Muistiinpanot

1. ↑ Rubikin kuution historia (pääsemätön linkki) . Haettu 20. heinäkuuta 2013. Arkistoitu alkuperäisestä 4. syyskuuta 2013. (määrätön) 
2. ↑ Jerry Slocum, David Singmaster, Wei-Hwa Huang, Dieter Gebhardt, Geert Hellings. Kuutio: Lopullinen opas maailman myydyimpään palapeliin – salaisuuksia, tarinoita, ratkaisuja . - 2009. - S. 26. - 142 s. - ISBN 978-1-57912-805-0 .
3. ↑ David Joyner. Seikkailut ryhmäteoriassa: Rubikin kuutio, Merlinin kone ja muut matemaattiset lelut . - 2008. - S. 149. - 328 s.  (linkki ei saatavilla)
4. ↑ Herbert Kociemba. Kuutio Explorer . Haettu 27. heinäkuuta 2013. Arkistoitu alkuperäisestä 4. syyskuuta 2013. (määrätön)
5. ↑ Isompi rubikin kuutio sidottu Arkistoitu 29. toukokuuta 2014.
6. ↑ 4x4x4 algoritmigeneraattori? (kuten cube explorer) . Haettu 26. heinäkuuta 2013. Arkistoitu alkuperäisestä 29. toukokuuta 2014. (määrätön)
7. ↑ 4x4-algoritmit (pääsemätön linkki) . Haettu 26. heinäkuuta 2013. Arkistoitu alkuperäisestä 29. toukokuuta 2014. (määrätön) 
8. ↑ Weisstein, Eric W. Jumalan numero . Haettu 4. toukokuuta 2020. Arkistoitu alkuperäisestä 21. helmikuuta 2020. (määrätön)
9. ↑ Rokicki, T.; Kociemba, H.; Davidson, M.; ja Dethridge, J. Jumalan numero on 20 . Käyttöpäivä: 19. heinäkuuta 2013. Arkistoitu alkuperäisestä 26. heinäkuuta 2013.  
10. ↑ Rokicki, T. ja Davidson, M. Jumalan numero on 26 neljänneskierrosmetriikassa  . Haettu 2. heinäkuuta 2015. Arkistoitu alkuperäisestä 7. heinäkuuta 2015.
11. ↑ Jaap Scherphuis. Minikuutio, 2×2×2 Rubikin kuutio . Haettu 21. heinäkuuta 2013. Arkistoitu alkuperäisestä 4. syyskuuta 2013.  
12. ↑ Jaap Scherphuis. Pyraminx (englanniksi) . Haettu 21. heinäkuuta 2013. Arkistoitu alkuperäisestä 29. elokuuta 2013.  
13. ↑ Joitakin 3-värisen kuution tuloksia . Cube-foorumin verkkotunnus. Haettu 29. heinäkuuta 2013. Arkistoitu alkuperäisestä 4. syyskuuta 2013. (määrätön)
14. ↑ A. Brüngger, A. Marzetta, K. Fukuda ja J. Nievergelt, The parallel search bench ZRAM and its applications Arkistoitu 11. marraskuuta 2017 at the Wayback Machine , Annals of Operations Research 90 (1999), pp. 45-63.
15. ↑ Bruce Norskog. Viisitoista palapeli voidaan ratkaista 43 "liikkeellä" . Cube Forumin verkkotunnus (englanniksi) (12. elokuuta 2010) . Haettu 20. heinäkuuta 2013. Arkistoitu alkuperäisestä 4. syyskuuta 2013.  
16. ↑ Daniel Ratner, Manfred K. Warmuth (1986). "Lyhimmän ratkaisun löytäminen 15 palapelin N × N -laajennukselle on vaikeaa" Arkistoitu 9. maaliskuuta 2012 Wayback Machinessa . julkaisussa Proceedings AAAI-86 . National Conference on Artificial Intelligence, 1986. s. 168-172.
17. ↑ Carlos Rueda, "Optimaalinen ratkaisu Towers of Hanoi Puzzle" .

Linkit

• Rubikin kuutio: Assault on the Stronghold (Konstantin Knop)

Speedcubing
Organisaatio	World Speedcubing Association
Urheiluväline	Kuutio 2x2x2 Kuutio 3x3x3 Kuutio 4x4x4 Kuutio 5x5x5 Kuutio 6x6x6 Kuutio 7x7x7 Pyraminx Megaminx scube Neliö-1 Rubikin kello
Käsitteet	pinomatto Ryntäily jumalan algoritmi Epäonnistunut yritys Rubikin kuution ratkaiseminen yhdellä kädellä Rubikin kuution rakentaminen jaloillasi Sokea Rubikin kuutio Rubikin kuution kokoaminen liikkeiden lukumäärää varten Epäviralliset speedcubing-lajit
Maailmanmestaruus	1982 2003 2005 2007 2009 2011 2013 2015 2017 2019 2021