Ricerca A star
La ricerca A star è una strategia di ricerca informata in cui la scelta del cammino si basa sia sul costo effettivo C1 necessario per raggiungere un nodo intermedio n dal nodo di origine e sia sulla stima del costo C2 necessario per raggiungere il nodo finale ( obiettivo ) a partire dal nodo intermedio n. La funzione di ricerca è, quindi, composta da due funzioni di osto:
F(n) = C1(n) + C2(n)
La ricerca A-Star è conosciuta anche come ricerca A-Stella o ricerca A*. La strategia di ricerca A-star è una variante della ricerca a costo uniforme. A differenza di quest'ultima la ricerca A-star analizza il costo del cammino C1 soltanto fino ad un livello di profondità n ( nodo intermedio ) e da qui stima il cammino C2 per raggiungere il nodo obiettivo. In tal modo la ricerca a-star permette di analizzare dapprima i cammini presumibilmente migliori, ossia quelli in grado di minimizzare la somma delle funzioni di costo C1 e C2. Nel seguente grafo è rappresentato un esempio di ricerca a-star.
Come si può facilmente osservare, a partire dal nodo iniziale A è possibile intraprendere tre cammini per raggiungere il nodo finale Z. Se l'algoritmo prendesse in considerazione soltanto il costo effettivo C1 dovrebbe analizzare dapprima il nodo C in quanto ha un costo C1 inferiore (4) rispetto ai nodi B (6) e D (7). Ciò porterebbe ad arrivare al nodo finale Z mediante il cammino ACZ con un costo di cammino pari a 19 (4+15). Pur essendo una soluzione efficace, in quanto l'obiettivo viene raggiunto, non è anche una soluzione efficiente dal punto di vista dei costi. L'algoritmo di ricerca A-star riduce il rischio di selezionare un cammino inefficiente poiché non si limita a prendere in considerazione soltanto il costo C1 ma anche una stima ( ricerca informata ) del costo C2. Seguendo tale logica il nodo intermedio migliore risulta essere il nodo D, il quale pur essendo il più lontano dal nodo iniziale (C1=7) consente di minimizzare la somma dei costi C1+C2 (7+10) rispetto ai cammini alternativi. Il costo del cammino individuato dall'algoritmo A-star ADZ è pari a 17 ed è il cammino più efficiente per raggiungere il nodo Z a partire dal nodo A.
Euristica. L'ottimalità della strategia di ricerca A-star è determinata dall'euristica utilizzata per stimare il costo C2 dal nodo intermedio al nodo finale, la quale deve sempre essere un'euristica ammissibile e consistente.
