SMA*

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

SMA*, acronimo di Simplified Memory-Bounded A*, è un algoritmo euristico per la ricerca del cammino minimo basato sull'algoritmo A*, proposto dall'informatico anglo-statunitense Stuart Russell nel 1992.^[5]

Il vantaggio principale di SMA* è l'uso limitato della memoria, al contrario di A* che ha bisogno, nel caso peggiore, di uno spazio esponenziale. Tutte le altre caratteristiche di SMA* derivano direttamente da A*, incluse le prestazioni in termini di tempo, che nel caso peggiore rimangono esponenziali.^[6] Come si evince anche dal nome, questo tipo di ricerca fa parte della famiglia memory-bounded A* (o MA*).^[5]

^ Dove $b$ è il fattore di diramazione (branching factor) e $d$ è la profondità della soluzione.
^ Dove $n$ è il numero di nodi che entrano in memoria.
^ Se la soluzione più superficiale entra in memoria, altrimenti restituisce la soluzione migliore che è riuscito a trovare.
^ Se la soluzione più superficiale entra in memoria.
^ ^a ^b Rong Zhou e Eric A. Hansen, Memory-Bounded A* Graph Search (PDF), Proceedings of the Fifteenth International Florida Artificial Intelligence Research Society Conference, Pensacola Beach, Florida, 2002, pp. 203-209. URL consultato il 29 marzo 2020 (archiviato dall'url originale l'8 settembre 2017).
^ (EN) Max Welling, Informed search algorithms (PDF), su ics.uci.edu, Università della California, Irvine, pp. 31-33. URL consultato il 27 marzo 2020 (archiviato il 3 ottobre 2015).

[1] Dove $b$ è il fattore di diramazione (branching factor) e $d$ è la profondità della soluzione.

[2] Dove $n$ è il numero di nodi che entrano in memoria.

[3] Se la soluzione più superficiale entra in memoria, altrimenti restituisce la soluzione migliore che è riuscito a trovare.

[4] Se la soluzione più superficiale entra in memoria.

[Zhou-Hansen-2002-5] Rong Zhou e Eric A. Hansen, Memory-Bounded A* Graph Search (PDF), Proceedings of the Fifteenth International Florida Artificial Intelligence Research Society Conference, Pensacola Beach, Florida, 2002, pp. 203-209. URL consultato il 29 marzo 2020 (archiviato dall'url originale l'8 settembre 2017).

[6] (EN) Max Welling, Informed search algorithms (PDF), su ics.uci.edu, Università della California, Irvine, pp. 31-33. URL consultato il 27 marzo 2020 (archiviato il 3 ottobre 2015).

[1]

[2]

[3]

[4]

[5]

[6]