Dumnezeu algoritm

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită la 7 martie 2022; verificările necesită 2 modificări .

Algoritmul lui Dumnezeu  este un concept care a apărut în timpul discuției despre modalitățile de a rezolva cubul lui Rubik . Termenul poate fi folosit și în legătură cu alte puzzle-uri de permutare . Algoritmul zeului puzzle-ului este orice algoritm care produce o soluție puzzle care conține numărul minim posibil de mișcări (soluție optimă) pornind de la orice configurație dată.

Unul dintre pionierii teoriei matematice a Cubului Rubik , David Singmaster [1] , descrie apariția termenului astfel:

John Conway , unul dintre cei mai mari teoreticieni ai grupului din lume, a remarcat că Cubul respectă așa-numitele legi de conservare (sau paritate), ceea ce înseamnă că unele mișcări sunt pur și simplu imposibile. Fie Conway, fie unul dintre colegii săi de la Cambridge au definit calea cea mai scurtă de la orice stare dată înapoi la starea inițială ca „Algoritmul lui Dumnezeu”.

Text original  (engleză)[ arataascunde] John Conway, unul dintre cele mai mari grupuri de teoreticieni din lume, a observat că Cubul respectă ceea ce sunt cunoscute sub numele de legi de conservare (sau paritate), ceea ce înseamnă că unele mișcări pur și simplu nu sunt posibile. Fie Conway, fie unul dintre colegii săi de la Cambridge au definit cea mai scurtă rută de la orice poziție dată înapoi la poziția de plecare ca „Algoritmul lui Dumnezeu”. — David Singmaster [2]

Definiție

Algoritmul lui Dumnezeu poate exista pentru puzzle-uri cu un număr finit de configurații posibile și cu un set finit de „mișcări” permise în fiecare configurație care traduc configurația curentă în alta. Termenul „rezolvare puzzle-ul” înseamnă a indica o secvență de mișcări care duce o configurație inițială la o configurație finală. Soluția optimă pentru puzzle este să indicați cea mai scurtă secvență de mișcări pentru a rezolva puzzle-ul. Pot exista mai multe soluții optime.

Puzzle-urile notabile care se încadrează în această definiție includ Cubul Rubik , Turnul din Hanoi , Jocul celor 15 , Solitaire cu cipuri , diverse probleme de transfuzie și transport (" Lupul, Capra și Varza "). Comun tuturor acestor puzzle-uri este că ele pot fi descrise ca un grafic , ale cărui vârfuri sunt toate configurațiile posibile ale puzzle-ului, iar marginile sunt posibilele tranziții între ele („mușcări”).

În multe astfel de puzzle-uri, configurația finală este implicit asumată, de exemplu, în „etichete” - un aranjament ordonat de oase, pentru un cub Rubik - aceeași culoare a fețelor. În aceste cazuri, „asamblarea puzzle-ului” înseamnă că, pentru o configurație inițială arbitrară, este necesar să se specifice o secvență de mișcări care să conducă la o configurație finală fixă .

Algoritmul rezolvă puzzle-ul dacă ia ca intrare o pereche arbitrară de configurații inițiale și finale (sau doar configurația inițială dacă configurația finală este fixă) și returnează ca rezultat o secvență de mișcări care transferă configurația inițială în cea finală ( dacă o astfel de secvență există, în caz contrar, algoritmul raportează imposibilitatea unei soluții). Soluția optimă conține numărul minim posibil de mișcări.

Atunci algoritmul lui Dumnezeu (pentru un puzzle dat) este un algoritm care rezolvă puzzle-ul și găsește cel puțin o soluție optimă pentru o pereche arbitrară de configurații.

Unii autori cred că algoritmul lui Dumnezeu ar trebui să fie , de asemenea, practic , adică să folosească o cantitate rezonabilă de memorie și să se completeze într-un timp rezonabil.

Fie G un grup puzzle de permutare (cu un set generator dat), v un vârf al graficului Cayley al lui G . Găsiți un algoritm eficient și practic pentru determinarea unei căi de la v la un vârf v 0 asociat cu un element neutru a cărui lungime este egală cu distanța de la v la v 0 . [...] Acest algoritm este numit algoritmul lui Dumnezeu .

Text original  (engleză)[ arataascunde] Fie G grupul unui puzzle de permutare (cu un set generator fix) și fie v un vârf în graficul Cayley al lui G. Găsiți un algoritm efectiv, practic pentru determinarea unei căi de la v la vârful v 0 asociat identității având lungimea egală cu distanţa de la v la v 0 . [...] Acest algoritm se numește algoritmul lui Dumnezeu . – David Joyner [3]

Practicitatea poate fi înțeleasă în moduri diferite. Deci, există programe de calculator care permit găsirea soluției optime pentru o configurație arbitrară a cubului Rubik într-un timp rezonabil [4] . În același timp, o sarcină similară pentru un cub 4×4×4 rămâne practic irealizabilă în acest moment [5] [6] [7] . Pentru unele puzzle-uri , există o strategie care permite, după reguli simple, să se determine manual soluția optimă, fără ajutorul unui computer.

Definiție alternativă a algoritmului lui Dumnezeu: algoritmul nu este necesar pentru a găsi întreaga secvență de mișcări; în schimb, este suficient să găsim prima mișcare a soluției optime care o apropie de obiectiv și o transferă într-o nouă configurație. Cele două definiții sunt echivalente: reaplicarea algoritmului unei noi perechi de configurații găsește din nou mutarea soluției optime, ceea ce face posibilă obținerea întregii secvențe de mișcări ale soluției optime.

Numărul lui Dumnezeu

Numărul zeu al unui puzzle dat este un număr n , astfel încât să existe cel puțin o configurație a puzzle-ului, a cărei soluție optimă constă din n mișcări și nu există nicio configurație, a cărei lungime a soluției optime depășește n . Cu alte cuvinte, numărul lui Dumnezeu este cea mai mică limită superioară a setului de lungimi de soluții optime pentru configurațiile puzzle.

Numărul lui Dumnezeu pentru un cub Rubik de 3x3x3 este 20 - acesta este diametrul graficului Cayley al grupului de cuburi Rubik [8] .

În general (pentru un puzzle cu permutare arbitrară), numărul lui Dumnezeu nu este egal cu diametrul graficului Cayley al grupului de puzzle, ci cu excentricitatea vârfului corespunzătoare stării „asamblate” a puzzle-ului.

Exemple

• Un cub Rubik 3  ×  3  × 3  poate fi întotdeauna rezolvat în cel mult 20 de mișcări (numărând o întoarcere a oricăreia dintre cele 6 fețe cu 90 sau 180 de grade pe tură). Sunt cunoscute configurații care necesită cel puțin 20 de mișcări pentru asamblare. Astfel, „numărul lui Dumnezeu” al cubului Rubik este 20 [9] .

• Dacă sunt permise doar virajele de 90 de grade (dar nu și 180 de grade, care sunt posibile, dar se numără ca două mișcări), „numărul lui Dumnezeu” al Cubului Rubik este 26 [10] .

• Numărul divin al unui  zar de 2  ×  2  × 2 este de 11 mișcări dacă o viraj de 180° este socotită ca 1 mutare, sau 14 mișcări dacă o viraj de 180° este socotită ca 2 mișcări. Un număr mic ( 3 674 160 ) de configurații ale cubului 2  ×  2  ×  2 a făcut posibilă calcularea algoritmului lui Dumnezeu (sub forma unei soluții optime pentru fiecare configurație) încă din anii 80 [11] .

• Numărul piramidei zeului lui Meffert este 11 [12] .

• Un cub de trei culori, ale cărui părți opuse sunt colorate la fel. Numărul de configurații ale unui cub tricolor este

În martie-aprilie 2012, s-a constatat că numărul zeului cubului tricolor este de 15 FTM , 17 QTM sau 14 STM (conform metricii STM , rotația oricărui strat mijlociu este, de asemenea, considerată a fi de 1 tură. ) [13] .

• „ Cincisprezece ” poate fi rezolvat în 80 de mișcări „scurte” [14] sau 43 de mișcări „lungi” [15] în cel mai rău caz (prin mișcări „scurte” înțelegem mutarea plăcilor individuale, iar prin mișcări „lungi” - mutarea unor rânduri întregi de 1, 2 sau 3 oase). Pentru etichetele generalizate (cu mai mult de 15 piese), problema găsirii celei mai scurte soluții este NP-complet [16] .

• Pentru Turnul din Hanoi , algoritmul lui Dumnezeu există pentru orice număr de discuri, dar odată cu adăugarea de discuri, numărul de mișcări crește exponențial [17] .

Vezi și

• Algoritmul Doomsday
• Diametrul graficului
• Matematică cubul lui Rubik

Note

1. ↑ Istoria Cubului Rubik (link inaccesibil) . Preluat la 20 iulie 2013. Arhivat din original la 4 septembrie 2013. (nedefinit) 
2. ↑ Jerry Slocum, David Singmaster, Wei-Hwa Huang, Dieter Gebhardt, Geert Hellings. Cubul: Ghidul suprem pentru cel mai bine vândut puzzle din lume - Secrete, povești, soluții . - 2009. - S. 26. - 142 p. - ISBN 978-1-57912-805-0 .
3. ↑ David Joyner. Aventurile în teoria grupurilor: cubul lui Rubik, mașina lui Merlin și alte jucării matematice . - 2008. - S. 149. - 328 p.  (link indisponibil)
4. ↑ Herbert Kociemba. Cube Explorer . Consultat la 27 iulie 2013. Arhivat din original la 4 septembrie 2013. (nedefinit)
5. ↑ Bigger rubik cube bound Arhivat 29 mai 2014.
6. ↑ generator de algoritm 4x4x4? (ca cube explorer) . Preluat la 26 iulie 2013. Arhivat din original la 29 mai 2014. (nedefinit)
7. ↑ Algoritmi 4x4 (link inaccesibil) . Preluat la 26 iulie 2013. Arhivat din original la 29 mai 2014. (nedefinit) 
8. ^ Weisstein , Eric W. Numărul lui Dumnezeu . Preluat la 4 mai 2020. Arhivat din original la 21 februarie 2020. (nedefinit)
9. ↑ Rokicki, T.; Kociemba, H.; Davidson, M.; și Dethridge, J. Numărul lui Dumnezeu este 20 . Data accesului: 19 iulie 2013. Arhivat din original pe 26 iulie 2013.  
10. ↑ Rokicki, T. și Davidson, M. Numărul lui Dumnezeu este 26 în metrica cu sfert de tură  . Preluat la 2 iulie 2015. Arhivat din original la 7 iulie 2015.
11. ↑ Jaap Scherphuis. Mini Cube, cubul Rubik 2×2×2 . Consultat la 21 iulie 2013. Arhivat din original la 4 septembrie 2013.  
12. ↑ Jaap Scherphuis. Pyraminx (engleză) . Preluat la 21 iulie 2013. Arhivat din original la 29 august 2013.  
13. ↑ Unele rezultate cub de 3 culori . Domeniul Cube Forum. Preluat la 29 iulie 2013. Arhivat din original la 4 septembrie 2013. (nedefinit)
14. ↑ A. Brüngger, A. Marzetta, K. Fukuda și J. Nievergelt, The parallel search bench ZRAM and its applications Arhivat la 11 noiembrie 2017 la Wayback Machine , Annals of Operations Research 90 (1999), pp. 45-63.
15. ↑ Bruce Norskog. Puzzle-ul Cincisprezece poate fi rezolvat în 43 de „mișcări” . Forumul Domain of the Cube (engleză) (12 august 2010) . Preluat la 20 iulie 2013. Arhivat din original la 4 septembrie 2013.  
16. ↑ Daniel Ratner, Manfred K. Warmuth (1986). „Găsirea celei mai scurte soluții pentru extensia N × N a puzzle-ului cu 15 este insolubilă” Arhivată 9 martie 2012 la Wayback Machine . în Proceedings AAAI-86 . Conferința Națională de Inteligență Artificială, 1986. pp. 168-172.
17. ↑ Carlos Rueda, „O soluție optimă pentru puzzle-ul Turnurilor din Hanoi” .

Link -uri

• Cubul Rubik: Asalt on the Stronghold (Konstantin Knop)

Speedcubing
Organizare	Asociația Mondială de Speedcubing
Echipament sportiv	Cub 2x2x2 Cub 3x3x3 Cub 4x4x4 Cub 5x5x5 Cub 6x6x6 Cub 7x7x7 Pyraminx Megaminx scube Pătrat-1 Ceasul lui Rubik
Concepte	stackmat Încăierare Dumnezeu algoritm Incercare eșuată Rezolvarea unui cub Rubik cu o singură mână Construiește un cub Rubik cu picioarele tale Cubul Rubik orb Asamblarea unui cub Rubik pentru numărul de mișcări Discipline neoficiale de speedcubing
Campionate mondiale	1982 2003 2005 2007 2009 2011 2013 2015 2017 2019 2021