A*

A*

L'algoritmo A* combina gli algoritmi di ricerca su grafo LCF e BFS, dove per ogni percorso p considera la stima f(p) del suo costo totale (dal nodo di partenza fino al goal), con f(p) = cost(p) + h(p). Dove h(p) è una stima del costo minimale dall’ultimo nodo di p fino a un goal.

Si è pensato di utilizzare A* perchè i fattori di ammissibilità sono rispettati ovvero:

• il fattore di ramificazione è finito
• costi archi > 0
• h(n) è ammissibile

Classe di riferimento: AStarGraph

Classe correlata: Graph

Per applicare A* si è pensato di creare un grafo come struttura dati, dove i nodi sono le strade e gli archi gli incroci (strada a strada) ed i vertici hanno come proprietà il peso del nodo, anche gli archi riportano il peso del nodo utile nel calcolo del percorso.

Per la costruzione del grafo, in particolare i vertici, si interroga la KB e si costruiscono le strade con le proprietà (nome,lunghezza,peso,x,y).

Per la costruzione del grafo, in particolare gli archi, si interroga la KB e si costruiscono gli incroci attraverso la procedura collega che determina il collegamento di due incroci attraverso una strada.

Per la creazione del grafo ci si è assicurati di evitare ambiguità con doppioni utilizzando un insieme.

Per la funzione di costo di A* si somma il peso (funzione implementata in prolog) di ogni arco attraversato e la funzione euristica data dalla norma uno delle coordinate dei punti di arrivo e destinazione.

Il MPP (Multipath pruning) permette di evitare i cicli. Si è applicato il MPP, attraverso due insiemi, uno dei nodi attraversati ed uno con il percorso scelto. Questo permette di visitare un nodo, trovare i nodi adiacenti e scegliere tra tutti i nodi disponibili il prossimo da percorrere.