Algoritmo di Dijkstra e Best-First-Search#
L’algoritmo di Dijkstra funziona visitando i vertici del grafico a partire dal punto di partenza dell’oggetto. Poi esamina ripetutamente il vertice più vicino non ancora esaminato, aggiungendo i suoi vertici all’insieme dei vertici da esaminare. Si espande verso l’esterno dal punto di partenza fino a raggiungere l’obiettivo. L’algoritmo di Dijkstra è garantito per trovare un percorso più breve dal punto di partenza all’obiettivo, a condizione che nessuno dei bordi abbia un costo negativo. (Scrivo “un percorso più breve” perché spesso ci sono più percorsi equivalenti). Nel seguente diagramma, il quadrato rosa è il punto di partenza, il quadrato blu è l’obiettivo, e le aree in verde acqua mostrano quali aree l’Algoritmo di Dijkstra ha analizzato. Le aree verde acqua più chiare sono quelle più lontane dal punto di partenza, e quindi formano la “frontiera” dell’esplorazione:
L’algoritmo Greedy Best-First-Search funziona in modo simile, tranne che ha una stima (chiamata euristica) di quanto sia lontano dalla meta ogni vertice. Invece di selezionare il vertice più vicino al punto di partenza, seleziona il vertice più vicino all’obiettivo. La Greedy Best-First-Search non è garantita per trovare un percorso più breve. Tuttavia, funziona molto più velocemente dell’algoritmo di Dijkstra perché usa la funzione euristica per guidare il suo percorso verso l’obiettivo molto velocemente. Per esempio, se l’obiettivo è a sud della posizione di partenza, Greedy Best-First-Search tenderà a concentrarsi sui percorsi che portano verso sud. Nel diagramma seguente, il giallo rappresenta i nodi con un alto valore euristico (alto costo per raggiungere l’obiettivo) e il nero rappresenta i nodi con un basso valore euristico (basso costo per raggiungere l’obiettivo). Mostra che la Greedy Best-First-Search può trovare percorsi molto velocemente rispetto all’algoritmo di Dijkstra:
Tuttavia, entrambi questi esempi illustrano il caso più semplice – quando la mappa non ha ostacoli, e il percorso più breve è davvero una linea retta. Consideriamo l’ostacolo concavo come descritto nella sezione precedente. L’algoritmo di Dijkstra lavora di più ma ha la garanzia di trovare un percorso più breve:
Greedy Best-First-Search d’altra parte fa meno lavoro ma il suo percorso non è chiaramente altrettanto buono:
Il problema è che Greedy Best-First-Search è “avido” e cerca di muoversi verso la meta anche se non è il percorso giusto. Poiché considera solo il costo per arrivare all’obiettivo e ignora il costo del percorso fino a quel momento, continua ad andare avanti anche se il percorso che sta facendo è diventato molto lungo.
Non sarebbe bello combinare il meglio di entrambi? A* è stato sviluppato nel 1968 per combinare approcci euristici come Greedy Best-First-Search e approcci formali come Dijsktra’s Algorithm. È un po’ insolito in quanto gli approcci euristici di solito danno un modo approssimativo per risolvere i problemi senza garantire che si ottenga la risposta migliore. Tuttavia, A* è costruito sopra l’euristica, e sebbene l’euristica stessa non dia una garanzia, A* può garantire un percorso più breve.