Utilizzo di un algoritmo di ricerca A * per risolvere il puzzle tridimensionale 3x3?

Question

Sto lavorando a un problema di puzzle a scatola tridimensionale 3x3 nei miei compiti. Io codice con C.

Ci sono 26 scatole e in un primo, primo luogo è vuoto. Facendo scorrere le scatole, devo sistemarle nell'ordine corretto. I numeri rossi mostrano l'ordine corretto e il 27 ° posto deve essere vuoto alla fine. Non voglio che tu mi dia il codice; Ho cercato nei forum e sembra che devo usare il A* search algorithm, ma come?

Potete darmi suggerimenti su come utilizzare l'algoritmo A * su questo problema? Che tipo di struttura dati dovrei usare?

Answer 1

Sai come funzionano i grafici e come A * trova percorsi più brevi su di essi, giusto?

L'idea di base è che ogni configurazione del puzzle può essere considerata un vertice in un grafico ei bordi rappresentano le mosse (collegando le configurazioni prima e dopo lo spostamento).

Trovare un insieme di mosse che porta da una configurazione originale a quella desiderata può essere visto come un problema di ricerca del percorso.

Answer 2

Definire il problema come stati-grafico:
G=(V,E) dove V=S={(x_1,x_2,...,x_54) | all possible states the 3d board can be in} [ogni numero rapprensenta un singolo 'piazzare' sul bordo 3d].
e definire E={(v1,v2)| it is possible to move from state v1 to state v2 with a single step} una definizione alternativa [identica] per E è quello di utilizzare la funzione successors(v):
Per ogni v in V: successors(v)={all possible boards you can get, with 1 step from v}

È inoltre necessario un admissible heuristic function, una abbastanza buona per questo problema può essere: h(state)=Sigma(manhattan_distance(x_i)) where i in range [1,54]) in sostanza, è la somma di manhattan distances per ogni numero dalla sua destinazione.

Ora, una volta ottenuti questi dati, possiamo iniziare a eseguire A * sul grafico definito G, con l'euristica definita. E poiché la nostra funzione euristica è ammissibile [convincere te stesso perché!], È garantito che la soluzione A * trovata sarà ottimale, a causa di admissibility and optimality of A*.
Individuazione del percorso attuale: A * termina quando si sviluppa lo stato di destinazione. [x_i=i nei termini utilizzati in precedenza]. Troverai il tuo percorso passando dal target alla sorgente, usando il campo parent in ciascun nodo.