Algoritmo A*

Algoritmo A*
Classe	Algoritmo di ricerca
Struttura dati	Grafo
Caso peggiore temporalmente
Caso peggiore spazialmente
Ottimale	sì
Completo	sì
	Manuale

百度北京小汽车摇号政策始于2011年1月。

In informatica, A* (pronunciato /e? stɑ?r/ in inglese) è un algoritmo di ricerca su grafi che individua un percorso da un dato nodo iniziale verso un dato nodo goal (o che passi un test di goal dato). Utilizza una "stima euristica" che classifica ogni nodo attraverso una stima della strada migliore che passa attraverso tale nodo. Visita il nodo in base a tale stima euristica. L'algoritmo A* è anche un esempio di ricerca best-first.^[1]^[2]

L'algoritmo è stato descritto nel 1968 da Peter Hart, Nils Nilsson, e Bertram Raphael.

Intuizione

Consideriamo un esempio motivante. Ci troviamo ad un incrocio A, e vorremmo andare ad un incrocio B che fortunatamente sappiamo trovarsi a nord rispetto a noi. In questo caso gli incroci sono i vertici di un grafo e le strade sono gli archi.

Se si effettua una 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 chance 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.

Veduta d'insieme

Un algoritmo di ricerca che garantisce sempre di trovare il percorso più corto verso una meta è detto ammissibile. Se A* utilizza una euristica allora non bisogna mai sovrastimare la distanza (o in genere, il costo) verso la meta, si può così verificare che A* sarà ammissibile. Una euristica che fa di una ricerca A* ammissibile è detta euristica ammissibile.

Se la stima semplicemente ritorna sempre zero, che non sarà mai una sovrastima, allora A* compirà effettivamente l'algoritmo di Dijkstra e troverà ancora una soluzione ottimale, benché non rapidamente. L'euristica migliore possibile, benché non sia di solito pratico calcolarla, è l'effettiva distanza minima verso la meta. Un esempio di euristica pratica ammissibile è la distanza in linea d'aria dalla meta su una mappa.

Può essere verificato che A* non considera più nodi di qualunque altro algoritmo di ricerca ammissibile, a meno che l'algoritmo alternativo non abbia una stima euristica più accurata. In questo senso A* è l'algoritmo computazionalmente più efficiente che garantisce la ricerca del percorso più breve.

Descrizione

A* comincia a partire dal nodo selezionato. Per ogni nodo è definito un costo di entrata (di solito zero per il nodo iniziale). A* allora valuta la distanza dal nodo meta a partire da quello corrente. Questa stima ed il costo assieme formano l'euristica che sarà assegnata al percorso passante per questo nodo. Il nodo è aggiunto allora a una lista, spesso chiamata "open".

L'algoritmo allora rimuove il primo nodo dalla lista (perché avrà valore della funzione euristica più basso). Se la lista è vuota, non ci saranno percorsi dal nodo iniziale al nodo meta e l'algoritmo si arresterà. Se il nodo è il nodo meta, A* ricostruisce e pone in output il percorso ottenuto e si arresta. Questa ricostruzione del percorso a partire dai nodi più vicini significa che non è necessario memorizzare il percorso in ogni nodo.

Se il nodo non è il nodo meta, nuovi nodi saranno creati per tutti i nodi vicini ammissibili; il modo di fare questo dipende dal problema. Per ciascun nodo successivo A* calcola il "costo" di entrata nel nodo e lo salva col nodo. Questo costo è calcolato dalla somma cumulativa dei pesi immagazzinati negli antenati, più il costo dell'operazione per raggiungere questo nuovo nodo.

L'algoritmo gestisce anche una lista di "closed", un elenco di nodi che sono già stati controllati. Se un nuovo nodo generato è già nella lista con un costo uguale o più basso, non ci sarà alcuna futura indagine su tale nodo o col percorso ad esso associato. Se un nodo nella lista di closed è uguale ad uno nuovo, ma è stato immagazzinato con un costo più alto, allora sarà rimosso dalla lista di closed, e il processo continuerà a partire dal nuovo nodo.

Successivamente, una stima della distanza dal nodo nuovo alla meta è aggiunta al costo per formare il suo valore euristico. Tale nodo è aggiunto allora alla lista "open", a meno che non esista un nodo identico con valore euristico minore o uguale.

L'algoritmo sarà adottato ad ogni nodo vicino, fatto ciò il nodo originale è preso dalla lista e posto nella lista di "closed". Il prossimo nodo sarà ottenuto dalla lista di open e con esso si ripeterà il processo descritto.

Perché A* è ammissibile e computazionalmente ottimo

C'è una spiegazione intuitiva del perché A* è sia ammissibile che ottimo rispetto ad altri algoritmi di ricerca ammissibili. A* ha una stima ottimistica del costo del percorso attraverso ogni nodo considerato, l'ottimismo consiste anche nel sapere che il vero costo del percorso attraverso ciascun nodo verso il nodo goal varrà almeno quanto vale la nostra stima. Tutto è basato su quanto A* "conosce".

Quando A* ha terminato la sua ricerca, per definizione avrà trovato un percorso il cui costo attuale è più basso del costo stimato per ogni percorso attraverso tutti i nodi rimasti in open. Ma essendo tale stima ottimista, A* potrà senza pericoli ignorare tali nodi. In altre parole, A* non trascurerà mai la possibilità di trovare un percorso dal costo minore, e quindi sarà ammissibile.

Supponiamo ora che un altro algoritmo di ricerca A termini la sua ricerca con un percorso il cui costo non sia minore del costo stimato per qualche nodo appartenente ad open. L'algoritmo A non può eliminare la possibilità, basandosi sulle informazioni euristiche che possiede, che un percorso attraverso tale nodo possa avere un costo inferiore a quanto valutato. Così anche se A potrà considerare meno nodi rispetto ad A*, non potrà essere ammissibile. Quindi, A* considera il numero di nodi più basso di qualunque altro algoritmo di ricerca ammissibile che utilizzi una funzione euristica non più accurata di quella adottata da A*.

Monotonicità

Se si può garantire che il primo percorso trovato da A* verso un nodo qualsiasi è quello ottimo, allora la lista CLOSED non sarà necessaria. Sarà necessaria solo una lista dei nodi già visitati (OPEN), così tali nodi non saranno rivisitati (in quanto non sarà necessario farlo). Questa garanzia può essere ottenuta se la funzione euristica è, oltre che ammissibile, anche monotona (o consistente), cioè se la differenza tra i valori dell'euristica per ogni coppia di nodi connessi non supera il costo effettivo associato all'arco che li collega (h(n1) ≤ c(n1,n2) + h(n2)). Questa è una forma di disuguaglianza triangolare, e garantisce che i nodi lungo un qualunque cammino nello spazio di ricerca abbiano sempre f(n) (funzione di valutazione) non decrescente. Si dimostra che A*, con tale euristica, espande i nodi in ordine non decrescente di f(n), poiché grazie al requisito di monotonicità non verrà mai generato un nodo con f(n) minore di quella del padre. Se A* espande i nodi in ordine non decrescente, allora quando anche si trovasse un nuovo cammino verso un nodo già in CLOSED, lo si potrebbe ignorare perché avrebbe sicuramente f(n) maggiore o uguale a quella del nodo già espanso, ed avendo lo stesso valore di stima euristica (è lo stesso nodo) il cammino percorso fino a quel punto avrà sicuramente un costo maggiore o uguale. Lo si può dunque scartare, ed asserire che il primo percorso trovato da A* verso un nodo è il cammino ottimo fino a quel nodo.

Si dimostra che una euristica monotona è ammissibile, e quindi se si rispetta la restrizione di monotonicità si ottiene anche il percorso ottimo fino al goal. Intuitivamente, se il primo cammino trovato verso un nodo è quello ottimo (verso quel nodo) allora ciò vale anche per il nodo goal, e quindi se l'algoritmo termina, lo fa con la soluzione ottima. è utile ricordare che A*, con euristica ammissibile, termina sempre su grafi finiti e con costi strettamente positivi.

La restrizione di monotonicità è un requisito più stringente dell'ammissibilità, ma per molti problemi classici si vede che un'euristica ammissibile è, solitamente, anche monotona. Un esempio molto valido di euristica ammissibile e consistente è quella della distanza in linea d'aria tra due punti, usata nel calcolo del percorso stradale ottimo tra le città di una mappa. Questa euristica ci permette di "vedere" cosa significhi essere ammissibile e consistente. Essa è sicuramente ammissibile, poiché nessuna strada tra due punti può essere più breve della distanza in linea d'aria tra essi, e quindi l'euristica non sovrastima mai il costo da un nodo al goal. è consistente, come si vede facilmente disegnando un triangolo in cui i vertici siano tre città di una piccola mappa. Scegliamo la città di partenza e quella di arrivo, immaginando che la strada passi dalla terza città. Se disegniamo una strada qualsiasi tra la partenza e l'arrivo, la sua lunghezza è maggiore o uguale a quella del lato che li unisce, e ogni lato di un triangolo è a sua volta maggiore o uguale alla differenza tra gli altri due lati. è quindi rispettata la restrizione di monotonicità.

Pseudocodice

Il seguente pseudocodice descrive l'algoritmo:

 function A*(start,goal)
     closedset := the empty set                 % The set of nodes already evaluated.     
     openset := set containing the initial node % The set of tentative nodes to be evaluated.
     g_score[start] := 0                        % Distance from start along optimal path.
     came_from := the empty map                 % The map of navigated nodes.
     h_score[start] := heuristic_estimate_of_distance(start, goal)
     f_score[start] := h_score[start]           % Estimated total distance from start to goal through y.
     while openset is not empty
         x := the node in openset having the lowest f_score[] value
         if x = goal
             return reconstruct_path(came_from,goal)
         remove x from openset
         add x to closedset
         foreach y in neighbor_nodes(x)
             if y in closedset
                 continue
             tentative_g_score := g_score[x] + dist_between(x,y)
             
             if y not in openset
                 add y to openset
                
                 tentative_is_better := true
             elseif tentative_g_score < g_score[y]
                 tentative_is_better := true
             else
                 tentative_is_better := false
             if tentative_is_better = true
                 came_from[y] := x
                 g_score[y] := tentative_g_score
                 h_score[y] := heuristic_estimate_of_distance(y, goal)
                 f_score[y] := g_score[y] + h_score[y]
     return failure

 function reconstruct_path(came_from,current_node)
     if came_from[current_node] is set
         p = reconstruct_path(came_from,came_from[current_node])
         return (p + current_node)
     else
         return the empty path

Note

^ Stuart Russell e Peter Norvig, Intelligenza Artificiale, 4a ed., Pearson, 2021, ISBN 9788891904454.
^ (EN) David L. Poole e Alan K. Mackworth, Artificial intelligence: foundataions of computational agents, Third edition, Cambridge University Press, 2023, ISBN 978-1-009-25822-7.

Bibliografia

P. E. Hart, N. J. Nilsson, B. Raphael: A Formal Basis for the Heuristic Determination of Minimum Cost Paths, IEEE Transactions on Systems Science and Cybernetics SSC4 (2), pp. 100–107, 1968.
P. E. Hart, N. J. Nilsson, B. Raphael: Correction to "A Formal Basis for the Heuristic Determination of Minimum Cost Paths", SIGART Newsletter, 37, pp. 28–29, 1972.
N. J. Nilsson, Principles of Artificial Intelligence, Tioga Publishing Company, Palo Alto, California, 1980.

Voci correlate

Altri progetti

Wikimedia Commons contiene immagini o altri file sull'algoritmo A*

Collegamenti esterni

(EN) Justin Heyes-Jones' A* algorithm tutorial. URL consultato il 27 ottobre 2019 (archiviato dall'url originale il 3 novembre 2012).
(EN) Another A* Pathfinding for Beginners, su policyalmanac.org. URL consultato il 28 gennaio 2006 (archiviato dall'url originale il 24 dicembre 2005).
(EN) Amit's Thoughts on Path-Finding and A*.
(EN) Sven Koenig's Demonstration of Lifelong Planning A* and A*.
(EN) Remko Tron?on and Joost Vennekens's JSearch demo (archiviato dall'url originale l'11 febbraio 2006).: demonstrates various search algorithms, including A*.
(EN) Sune Trudslev's Path finding in C# article. URL consultato il 5 febbraio 2018 (archiviato dall'url originale il 21 luglio 2006).

Portale Informatica

Portale Matematica

[1] Stuart Russell e Peter Norvig, Intelligenza Artificiale, 4a ed., Pearson, 2021, ISBN 9788891904454.

[2] (EN) David L. Poole e Alan K. Mackworth, Artificial intelligence: foundataions of computational agents, Third edition, Cambridge University Press, 2023, ISBN 978-1-009-25822-7.

[1]

[2]

桂花什么时候开花	慢性胰腺炎吃什么药	眩晕是什么意思	发烧是什么原因引起的	左下腹疼痛是什么原因
有点尿血是什么原因	喝完酒早上吃什么好	society是什么意思	知柏地黄丸治疗什么病	胃肠性感冒吃什么药
金箔是什么	乌合之众什么意思	弦子为什么嫁给李茂	吃什么可以提高记忆力	翊字五行属什么
消化不良吃什么食物	微量元素六项是什么检查	小腿浮肿是什么原因女性	女人吃什么补肾	感叹号像什么

北京的简称是什么luyiluode.com	打脸是什么意思hcv8jop6ns8r.cn	肝脏在什么位置zsyouku.com	肠胃看病挂什么科hcv9jop5ns6r.cn	脑宁又叫什么名字onlinewuye.com
王为念和王芳什么关系hcv8jop8ns7r.cn	手肿是什么病的前兆adwl56.com	阳五行属什么hcv9jop4ns5r.cn	开车撞死猫有什么预兆hcv8jop4ns5r.cn	低烧头疼吃什么药bysq.com
飞蓬草有什么功效aiwuzhiyu.com	孕妇子痫是什么病hcv9jop7ns9r.cn	小孩做ct对身体有什么影响hkuteam.com	额头老出汗是什么原因hcv8jop3ns5r.cn	肤色不均匀是什么原因hcv9jop5ns9r.cn
突然心跳加快是什么原因hcv8jop7ns0r.cn	酒店五行属什么hcv8jop5ns9r.cn	儿童咳嗽吃什么药管用hcv8jop7ns0r.cn	梦见自己生了个儿子是什么意思cl108k.com	护理是做什么的hcv7jop4ns7r.cn