Agenti risolutori di problemi: ricerca informata

Un agente che ricerca una soluzione nell'albero di ricerca, non è detto che debba limitarsi a considerare i dati del problema; in astratto, può infatti valutare quanto è promettente un nodo e basarsi anche su questa informazione per scegliere i nodi da estrarre ed espandere nella frontiera. Le strategia di ricerca che utilizzano questa logica si chiamano informate o euristiche: in generale, viene valutata la "bontà" di un nodo tramite una funzione f(n) detta funzione di valutazione.

Ricerca greedy best-first
Questa ricerca espande sempre il nodo che è più vicino all'obiettivo, ipotizzando che in questo modo è probabile arrivare rapidamente ad una soluzione. Analiticamente si dice che f(n) = h(n), dove h(n) è una funzione, solitamente definita sullo stato corrispondente al nodo, detta euristica; la funzione euristica stima il costo per arrivare da n al nodo di goal. L'algoritmo sceglie dalla frontiera il nodo con la f(n) inferiore. La ricerca non è completa nei casi in cui espando stati già visitati, dato che possono continuare ad essere espansi nodi corrispondenti allo stesso gruppo di  stati; non considerando i  nodi i cui stati sono già stati espansi (vedere eliminazione stati ripetuti), la ricerca risulta completa ma non ottima. Le complessità temporale e spaziale sono  O(b^m).

Ricerca A*
La ricerca A*, a differenza di quella greedy, tiene conto del costo complessivo del cammino per arrivare dal nodo di partenza a quello di goal. Quanto detto si traduce in una funzione di valutazione f(n) = g(n)+h(n), dove g(n) è il costo di cammino del nodo n e h(n) è la funzione euristica vista per la ricerca greedy. Questa ricerca è molto importante e come tale merita di essere analizzata più in profondità di quanto fatto con gli altri metodi di ricerca visti finora.