Sto creando il risolutore di cubi di Rubik. Sarebbe bello se il risolutore potesse risolvere cubi di qualsiasi dimensione e se potesse generare soluzioni brevi.
Ho trovato molte varie informazioni su l'algoritmo di Dio , che come ho capito è in grado di risolvere vari enigmi, non solo il cubo di Rubic.
Quindi voglio implementare l'algoritmo di Dio, ma non riesco a trovare alcuna spiegazione semplice di questo algoritmo.
In parole semplici, come funziona davvero l'algoritmo di Dio?
Non penso sia possibile fare di meglio che citare Wikipedia: l'algoritmo di Dio :
God's algorithm ... refers to any algorithm which produces a solution having the fewest possible number of moves, the idea being that an omniscient being would know an optimal step from any given configuration.
Quindi non è un "algoritmo" il cui funzionamento può essere descritto. Esistono più algoritmi di questo tipo, tra cui la ricerca in ampiezza e il meet-in-the-middle (che esegue la ricerca in ampiezza dalla posizione corrente e la posizione risolta e cerca una posizione raggiungibile da entrambi).
"L'algoritmo di Dio" non è un vero algoritmo. È l'algoritmo teorico che risolve un determinato problema in modo ottimale. Ma questo algoritmo è sempre specifico per un problema.
L'algoritmo funziona molto come la strategia perfetta negli scacchi: dallo stato risolto, enumerare ricorsivamente tutti gli stati vicini. Una volta raggiunto uno stato uguale al tuo stato corrente, il percorso che hai intrapreso per trovarlo è il percorso più breve verso la soluzione.
Il problema è che lo spazio e il tempo necessari per costruire effettivamente l'albero completo diventano astronomici, troppo grandi per poterli effettivamente spendere. Quindi il suo unico vantaggio è che sappiamo che esiste e come eseguirlo se potessimo permettercelo.
Ovviamente, vorremmo avere qualcosa di meglio; un metodo che troverà in modo affidabile il percorso più breve con molto meno sforzo. Se potessimo impossessarci di un tale algoritmo, renderebbe il problema molto più facile e presumibilmente (specialmente se fosse elegante) erediterebbe quindi l'appellativo "algoritmo di Dio", perché sarebbe superiore alla soluzione ingenua sotto ogni aspetto . Il problema è che non solo non conosciamo un tale metodo, non sappiamo neanche se esiste.
Per iniziare, Algoritmo di Dio non è un algoritmo. Non esiste un modo particolare in cui puoi risolvere diverse permutazioni del cubo con quell'algo.
Quali sono i creatori dell'algo di Dio:
Partizionate le posizioni in 2.217.093.120 serie da 19.508.428.800 posizioni.
Ridotto il conteggio dei set che dovevamo risolvere a 55,882,296 usando la simmetria e impostando la copertura.
E hanno scritto un programma che utilizzava circa 35 anni CPU per trovare soluzioni a tutte le posizioni in ciascuno dei set di 55,882,296.
Spero che questo ti dia un indizio su come funziona il dio algo.
Che cosa puoi fare -
Memorizza le permutazioni 43,252,003,274,489,856,000 del cubo lungo with the solutions in un database e poi ogni volta che ottieni un cubo codificato, controlla il database per quella specifica permutazione del cubo e poi ottieni la soluzione. Facile. (Pun intended)
Comunque, ecco un link che ho scoperto che potrebbe aiutarti - codice sorgente del risolutore Coset
Utilizza una struttura di ricerca per esaminare la struttura dei dati mostrata di seguito.
Dall'esperienza personale, l'utilizzo di un set per tenere traccia di ogni parte rotazionale del cubo funziona bene. Ogni sub cubo è in tre set non mater le dimensioni del cubo di rubik. Quindi, per trovare un sub cubo in un punto in cui sul cubo del rubik si prende l'intersezione dei tre set (il risultato è un sub cubo). Per eseguire una mossa, rimuovi i cubetti sub effettivi dai set coinvolti nella mossa e poi rimettili nei set che li prendono come risultato del movimento.
Il cubo 4 x 4 avrà 12 serie. 6 set per le 6 facce e 6 set per le sei bande che girano attorno al cubo. Le facce hanno ciascuna 16 sub cubi e le fasce hanno 12 sub-cuccioli. Ci sono un totale di 56 sub cubi. Ogni sub cubo contiene informazioni sul colore e la direzione dei colori. Lo stesso cubo di rubik è un array 4: 4 di 4 con ogni elemento che ha informazioni costituite dai 3 set che definiscono il sub cubo in quella posizione.
Leggi altre domande sui tag algorithms