Algoritmo A*: differenze tra le versioni

Versione delle 12:53, 1 ott 2016

Versione delle 12:23, 2 ott 2016

Riga 8:

Se si effettua una [[Visita in ampiezza|ricerca breadth-first]] come illustrato dall'[[algoritmo di Dijkstra]], cercheremo ogni punto con un raggio circolare fisso, gradualmente espanderemo questo cerchio per cercare gli incroci più lontani dal nostro punto iniziale. Questa può essere una strategia efficace se non si conosce dove si trovi la destinazione, come fa la polizia nella ricerca di un criminale nascosto.

Comunque, essa porta ad uno spreco di tempo se si hanno più informazioni. Una strategia migliore consiste nell'esplorazione degli incroci posizionati a nord del primo, perché essi saranno probabilmente i vertici più prossimi a B. Bisogna tuttavia notare che le strade potrebbero essere chiuse obbligandoci ad andare a sud per poter raggiungere la destinazione con un percorso a forma di C. Allora, se le strade ce lo permettono, andremo ad esplorare gli incroci sempre più vicini all'incrocio goal B. Ci sarà bisogno di qualche backtrack occasionale, ma intuitivamente questa è una strategia che ha buone chanceschance di trovare l'obiettivo velocemente. Inoltre, può essere provato che questa strategia troverà in ogni caso la strada migliore possibile, cioè la soluzione ottimale, come farebbe la ricerca breadth-first. Questa è l'essenza della ricerca A*.

Comunque, non è garantito che l'esecuzione dell'A* sia migliore rispetto ai semplici algoritmi di ricerca. In un ambiente molto contorto, il solo modo per raggiungere la nostra destinazione potrebbe essere quello di dirigerci a sud e in seguito girarci attorno. In questi casi la prova dei nodi più prossimi alla nostra destinazione potrebbe essere uno spreco di tempo.