Întrebări despre algoritmul lui Dumnezeu și cubul Rubik (Inginerie software, Algoritmi)

Firzen a intrebat.

Sunt în curs de creare a unui rezolvator de cuburi Rubik. Ar fi bine dacă solverul ar putea rezolva cuburi de orice dimensiune și dacă ar putea genera soluții scurte.

Am găsit mai multe informații diverse despre Algoritmul lui Dumnezeu, , care, din câte am înțeles, este capabil să rezolve diverse puzzle-uri, nu doar cubul lui Rubic.

Așadar, vreau să implementez algoritmul lui Dumnezeu, dar nu găsesc nicio explicație simplă a acestui algoritm.

În cuvinte simple, cum funcționează de fapt algoritmul lui Dumnezeu?

Comentarii

  • @AndresF. Nu cred că cere ajutor pentru a implementa Algoritmul lui Dumnezeu, ci mai degrabă cere o explicație simplă și clară a ceea ce este și cum funcționează în termeni simpli. –  > Por maple_shaft.
  • @maple_shaft întrebarea inițială cerea implementarea, dar a fost editată. –  > Por ratchet freak.
  • În cuvinte simple, algoritmul lui Dumnezeu este: „Fă întotdeauna cea mai bună mișcare”. –  > Por Hellion.
5 răspunsuri
Peter Taylor

Nu cred că se poate face mai bine decât să citez Wikipedia:Algoritmul lui Dumnezeu:

Algoritmul lui Dumnezeu … se referă la orice algoritm care produce o soluție având cel mai mic număr posibil de mutări, ideea fiind că o ființă omniscientă ar cunoaște un pas optim din orice configurație dată.

Deci nu este „un” algoritm a cărui funcționare poate fi descrisă. Există mai mulți astfel de algoritmi, printre care breadth-first-search și meet-in-the-middle (care efectuează breadth-first-search pornind de la poziția curentă și de la poziția rezolvată și caută o poziție accesibilă prin ambele).

Comentarii

  • Deci… Numai Dumnezeu poate implementa corect algoritmul lui Dumnezeu. 😉 –  > Por FrustratedWithFormsDesigner.
Philipp

„Algoritmul lui Dumnezeu” nu este un algoritm real. Este algoritmul teoretic care rezolvă o anumită problemă în mod optim. Dar acest algoritm este întotdeauna specific unei probleme.

  • Există probleme care pot fi rezolvate cu un algoritm care s-a dovedit matematic a fi ideal, astfel încât acest algoritm poate fi numit „algoritmul lui Dumnezeu” pentru acea problemă dată.
  • Pentru alte probleme, există algoritmi care sunt suspectați a fi „algoritmul lui Dumnezeu”, dar nu există încă o dovadă în acest sens.
  • Există probleme pentru care există algoritmi, dar există motive să se creadă că trebuie să existe un algoritm mai bun, astfel încât algoritmul lui Dumnezeu pentru acea problemă trebuie încă găsit.

Kilian Foth

Algoritmul funcționează foarte asemănător cu strategia perfectă în șah: pornind de la starea rezolvată, enumerați recursiv toate stările vecine. Odată ce ajungeți la o stare care este egală cu starea actuală, calea pe care ați parcurs-o pentru a o găsi este cea mai scurtă cale spre soluție.

Problema este că spațiul și timpul necesare pentru a construi efectiv arborele complet devin astronomice, mult prea mari pentru a le cheltui efectiv. Așadar, singurul său avantaj este că știm că există și că știm cum să îl realizăm dacă ne-am permite.

Evident, am dori să avem ceva mai bun; o metodă care să găsească în mod fiabil calea cea mai scurtă cu mult mai puțin efort. Dacă am putea face rost de un astfel de algoritm, acesta ar face problema mult mai ușoară și, probabil (mai ales dacă ar fi elegant), ar moșteni atunci denumirea de „algoritmul lui Dumnezeu”, deoarece ar fi superior soluției naive din toate punctele de vedere. Problema este că nu numai că nu cunoaștem o astfel de metodă, dar nici măcar nu știm dacă ea există.

Comentarii

  • Prostii. Există deja o metodă standard care îmbunătățește căutarea de tip „breadth-first” într-un spațiu de permutări: se numește în mod diferit „meet-in-the-middle”, căutare bidirecțională și, probabil, încă una sau două denumiri. –  > Por Peter Taylor.
  • și există mai multe metode pentru a găsi „căi probabil bune”, dintre care una este A* cu o euristică bună –  > Por ciudatul cu clichet.
Confuzie

Pentru a începe cu, Algoritmul lui Dumnezeu nu este un algoritm. Nu există un mod anume în care poți rezolva diferite permutări ale cubului cu acel algo.


Ce au făcut creatorii lui God’s Algo:

  • Au împărțit pozițiile în 2.217.093.120 de seturi de 19.508.428.800 de poziții fiecare.

  • Au redus numărul de seturi pe care trebuia să le rezolve la 55.882.296 folosind simetria și acoperirea seturilor.

  • Și au scris un program care a folosit aproximativ 35 de ani CPU pentru a găsi soluții pentru toate pozițiile din fiecare dintre cele 55.882.296 de seturi.


Sper că acest lucru vă oferă un indiciu despre cum funcționează algo-ul lui Dumnezeu.

Ce puteți face –

Doar stocați 43,252,003,274,489,856,000 permutări ale cubului de-a lungul with the solutions într-o bază de date și apoi, de fiecare dată când primești un cub încurcat, verifică în baza de date pentru acea permutare a cubului și apoi obține soluția. Este ușor. (Joc de cuvinte intenționat)


În orice caz, iată un link pe care l-am găsit și care te-ar putea ajuta – Codul sursă al rezolvatorului Coset

martyn strong

Folosiți un arbore de căutare pentru a parcurge structura de date prezentată mai jos.

Din experiența personală, utilizarea unui set pentru a ține evidența fiecărei părți rotative a cubului funcționează bine. Fiecare subcuvânt se află în trei seturi, indiferent de dimensiunea cubului Rubik. Deci, pentru a găsi un subcuvânt undeva pe cubul Rubik, trebuie doar să luați intersecția celor trei seturi (rezultatul este un subcuvânt). Pentru a face o mutare, scoateți subcuvelele afectate din seturile implicate în mutare și apoi puneți-le înapoi în seturile care le primesc ca rezultat al mutării.

Cubul de 4 pe 4 va avea 12 seturi. 6 seturi pentru cele 6 fețe și 6 seturi pentru cele 6 benzi care înconjoară cubul. Fețele au fiecare câte 16 subcube, iar benzile au fiecare câte 12 subcube. În total, există 56 de subcube. Fiecare subcuvânt conține informații despre culoare și direcția culorilor. Cubul rubik în sine este o matrice de 4 pe 4 pe 4 pe 4, fiecare element având informații constând în cele 3 seturi care definesc subcubul din locația respectivă.