Questa applicazione web ti permette di visualizzare una rappresentazione grafica di una gamma di diversi algoritmi di ricerca a grafo, mentre risolvi la tua scelta di 8 problemi di puzzle.
Inizio
Sulla sinistra di questa applicazione, vedrai il Pannello di Controllo. Usando il pannello di controllo, puoi configurare i seguenti aspetti dell’applicazione:
- Stato iniziale e Stato obiettivo
- Quale algoritmo di ricerca usare
- Quale funzione euristica usare, se usi un algoritmo di ricerca informato
- E se usare la modalità a passo singolo o a raffica
Ognuna di queste opzioni sarà descritta più in dettaglio di seguito.
Stati iniziali e finali
Per impostare gli stati iniziali o finali, puoi cliccare sul pulsante ‘Modifica stato’ o sulla rappresentazione grafica dello stato.
Dovresti vedere un popup come il seguente:
Per cambiare un tile, clicca semplicemente sul tile che vorresti sostituire, poi inserisci il nuovo valore sulla tua tastiera. Questo scambierà la tessera con quella che prima conteneva quel valore.
Algoritmo di ricerca
N-Puzzle supporta cinque diversi algoritmi di ricerca basati su grafici. I primi tre sono Algoritmi di Ricerca Non Informati:
- Ricerca per ampiezza
- Ricerca per profondità
- Ricerca per approfondimento iterativo
Gli altri due sono Algoritmi di Ricerca Informati:
- Ricerca A*
- Ricerca Greedy
Se scegliete un algoritmo di ricerca informato, allora avrete anche bisogno di selezionare una funzione euristica.
Funzione Euristica
N-Puzzle supporta tre diverse Funzioni Euristiche:
- Distanza Euclidea
- Distanza Manhattan (distanza Città-Blocco)
- Tiles Out-of-place
Modalità Passo Singolo o Burst
N-Puzzle può essere usato in due modalità. Il default è la modalità Single-Step, che ti permette di “riavvolgere” una ricerca, un passo alla volta. Questo è utile per capire meglio come funziona un algoritmo di ricerca.
L’altra modalità è il Burst Mode. Una volta iniziato, il Burst Mode continua l’esecuzione di una ricerca fino a quando lo stato dell’obiettivo è stato trovato. Una ricerca in Burst Mode può essere messa in pausa, ma non può essere ‘riavvolta’.
L’albero di ricerca
Rappresentazione dello stato
Mentre una ricerca è attiva, potrai vedere una rappresentazione visiva dell’albero di ricerca. Ogni nodo in questo albero di ricerca rappresenta una disposizione di tessere (o stato), ed è disegnato come una scatola che è divisa in 4 sezioni.
Il seguente diagramma mostra un nodo preso da una ricerca Greedy:
La sezione più grande è lo stato del puzzle. Sotto di essa vedrete due sezioni più piccole.
Sotto lo stato del puzzle ci sono due sezioni. La sezione a sinistra è la profondità del nodo. La sezione a destra è il punteggio euristico. Il punteggio euristico è usato solo con gli algoritmi di ricerca informata, quindi se stai usando la ricerca Breadth-first, Depth-first o Iterative Deepening Search, il punteggio euristico sarà omesso.
L’ultima sezione registra l’ordine in cui i nodi sono stati espansi. Per esempio, il nodo radice sarà sempre ‘#1’, e il nodo successivo espanso sarà segnato come ‘#2’.
Colori dei nodi
Per aiutare a rendere l’albero di ricerca più ‘leggibile’, il bordo di ogni nodo è codificato con colori in base al suo stato attuale.
Il seguente diagramma mostra l’algoritmo A* (con l’euristica della distanza euclidea) applicato ad un problema che può essere risolto in sole due mosse:
I colori possono essere interpretati come segue:
| Colore | Significato |
|---|---|
| Blu | Se un nodo è nella Lista Aperta allora sarà evidenziato in blu. |
| Rosso | Dopo ogni iterazione di un algoritmo di ricerca, il nodo che sarà espanso successivamente sarà evidenziato in rosso. Questo vale anche quando il nodo obiettivo è stato trovato. |
| Grigio | Se uno stato è stato esplorato, sarà grigio. Per esempio, nel passo 2) del diagramma qui sopra, lo stato iniziale è stato colorato di grigio per indicare che è stato esplorato. Nel passo 3), un nodo che rappresenta lo stato iniziale viene riscoperto ma non sarà espanso poiché lo stato iniziale è stato espanso tramite il nodo radice. |
| Verde | Una volta trovato lo stato obiettivo, sarà evidenziato in verde. |
| Oro | Una volta che un nodo che rappresenta lo stato obiettivo è stato trovato, qualsiasi nodo sul percorso di ritorno al nodo radice sarà evidenziato in oro. |
| Viola | Quando si usa la ricerca di approfondimento iterativo, i nodi inesplorati che superano la profondità massima non saranno aggiunti alla lista aperta. Questi nodi saranno colorati di viola. |
Liste aperte e chiuse
Mentre gli algoritmi di ricerca sono in esecuzione, vengono mantenute due liste. La prima è la Lista Aperta – questa è usata per tenere traccia dei nodi che sono stati scoperti, ma non ancora esplorati.
La seconda è la Lista Chiusa – questa è usata per tenere traccia dei nodi che sono stati esplorati, o nodi che non saranno esplorati perché rappresentano stati che sono già stati esplorati attraverso altri nodi.
Quando una ricerca è attiva, il numero di nodi nelle liste aperte e chiuse sarà visibile nell’angolo in alto a sinistra:
