Informazioni su questo esperimento
I pianificatori di percorsi in mappe, robot e videogiochi risolvono tutti lo stesso problema: trovare il modo meno costoso per andare da una partenza a una meta. Su questa griglia, ogni passo su una strada costa 1, un passo nel fango costa 5 e non è possibile attraversare i muri. Osserva tre algoritmi classici espandersi da S. La ricerca in ampiezza conta i passi e ignora il fango, Dijkstra esplora sempre per prima la cella meno costosa, mentre A* aggiunge una stima della distanza rimanente per dirigersi direttamente verso la meta. Crea le tue mappe e confronta quanto lavoro svolge ciascun algoritmo.
Obiettivi di apprendimento
- Rappresentare una mappa come un grafo di celle collegate alle celle vicine, con un costo per ogni passo
- Descrivere come la ricerca in ampiezza esplora ad anelli con lo stesso numero di passi
- Spiega perché Dijkstra trova il percorso più economico quando i passi hanno costi diversi
- Spiega come l’euristica A* riduce il numero di celle esplorate senza rinunciare al percorso migliore
- Confronta gli algoritmi in base al costo del percorso trovato e al lavoro svolto
Come si usa
- 1Scegli BFS e premi Cerca. Il percorso trovato passa nel fango? Leggi il costo nella tabella.
- 2Scegli Dijkstra e cerca di nuovo. Confronta il percorso e il relativo costo con quelli di BFS.
- 3Scegli A*. Il costo del suo percorso è uguale a quello di Dijkstra? Quante celle in meno ha esplorato?
- 4Osserva la frontiera blu durante la ricerca. In che modo la sua forma è diversa con Dijkstra e A*?
- 5Dipingi un muro per chiudere la strada intorno al fango. Quale algoritmo cambia percorso e perché?
- 6Premi Cancella mappa e trascina S e G per allontanarle. Senza ostacoli, quante celle esplora ciascun algoritmo?
Il modello
Ipotesi
- Ci si può muovere solo in alto, in basso, a sinistra e a destra. Entrare in una cella costa 1 sulla strada e 5 nel fango; non è possibile entrare nei muri.
- Durante la ricerca, BFS considera ogni passo come se costasse 1, quindi trova il percorso con meno passi. Il costo indicato nella tabella è il costo reale di quel percorso, fango compreso.
- Se due celle hanno la stessa priorità, viene esplorata per prima quella aggiunta per prima; perciò, con la stessa mappa, ogni esecuzione segue esattamente lo stesso ordine.
- La ricerca si ferma non appena l’obiettivo viene rimosso dalla frontiera; a quel punto se ne conosce il costo minimo.
Provalo in classe
- Q1Perché BFS può trovare un percorso più costoso di Dijkstra, anche se ha meno passi?
- Q2Se tutte le celle fossero strade, BFS e Dijkstra troverebbero percorsi con lo stesso costo? Perché?
- Q3Cosa succederebbe ad A* se la stima h fosse dieci volte la distanza di Manhattan?
- Q4Perché A* esplora meno celle quando l’obiettivo si trova in un’area aperta, ma più o meno tante quante Dijkstra in un labirinto?
- Q5Un navigatore trova in meno di un secondo un percorso veloce attraverso un paese con milioni di incroci stradali. Quali idee di questo laboratorio lo rendono possibile?
Domande frequenti
Qual è l’algoritmo migliore?
Dipende dal problema. BFS è semplice e corretto quando ogni passaggio ha lo stesso costo. Dijkstra gestisce costi diversi. A* dà lo stesso risultato di Dijkstra esplorando meno celle, se è disponibile una buona stima della distanza dalla destinazione.
Che cos’è la frontiera?
La frontiera è l’insieme delle celle raggiunte ma non ancora esplorate. Ogni algoritmo rimuove una cella dalla frontiera alla volta; l’unica differenza tra loro è la regola con cui scelgono quale cella rimuovere per prima.
Questi algoritmi possono gestire costi negativi?
Dijkstra e A* presuppongono che nessun passaggio abbia un costo negativo. Con costi negativi, una cella considerata definitiva in precedenza potrebbe poi risultare raggiungibile tramite un percorso meno costoso; serve quindi un altro algoritmo, come Bellman-Ford.