Agenti risolutori di problemi: ricerca non informata

Si è visto che l'aspetto fondamentale per risolvere i problemi tramite l'albero di ricerca, consiste nella ricerca del nodo da espandere nella frontiera dell'albero stesso. Questa può essere effettuata utilizzando solo le informazioni contenute nella formulazione del problema (ricerca non informata) oppure tramite l'utilizzo di altre informazioni (ricerca informata).
Si illustrano ora alcune metodologie di ricerca non informata, mettendo in luce le caratteristiche di prestazione.

Ricerca in ampiezza.
In base a questo metodo si sceglie sempre il nodo meno profondo; ciò corrisponde a trattare la frontiera come una "coda" ovvero una insieme ordinato dal quale si preleva il primo elemento aggiunto (si parla di logica FIFO: First In First Out). Considerando l'albero, verranno espansi i nodi per livelli di profondità.
La ricerca in ampiezza è completa se il branching factor b non è infinito; non è ottimale dato che la ricerca non tiene conto dei costi dei cammini; ha complessità temporale e spaziale uguale poichè tutti i nodi analizzati devono rimanere comunque in memoria, e pari a O(b^(D+1)).

Ricerca a costo uniforme
La ricerca a costo uniforme sceglie dalla frontiera il nodo a minor costo di cammino. Questo garantisce ottimalità e completezza escludendo i casi in cui esistono costi di passo nulli;  la complessità temporale e spaziale dell'operazione sono uguali per un motivo analogo a prima, e sono pari a O(b^[C*/epsilon]) dove [C*/epsilon] corrisponde al valore intero maggiore e più vicino a C*/epsilon, che significa il numero di livelli che scendo nel caso peggiore (quando la soluzione è a livello epsilon).

Ricerca in profondità
A differenza dei due metodi visti, la ricerca in profondità tende a ricercare la soluzione esplorando l'albero appunto in profondità: viene scelto dalla frontiera il nodo a profondità maggiore. Si nota subito come questo tipo di ricerca potrebbe non terminare e quindi non è completa, dato che non garantisce che venga trovata una soluzione se esiste, e a maggior ragione non è ottima; la complessità temporale è O(b^m), mentre la complessità spaziale, in questo caso, è differente dato che i nodi appartenenti a cammini sondati fino in fondo possono essere eliminati dalla memoria ed è pari a O(bm).

Ricerca a profondità limitata
Un modo per far terminare il metodo di ricerca in profondità consiste nel fissare un valore naturale l e confrontare questo valore con la profondità dei nodi; i nodi che hanno profondità maggire di l non vengono espansi. Anche in questo caso la ricerca non è completa e la complessità temporale è O(b^l) mentre quella spazioale è O(bl).

Ricerca ad approfondimento iterativo
Affrontando il problema di ricerca con l'ultimo metodo visto, non è possibile raggiungere la soluzione se questa è situata a profondità maggiore del valore fissato l. Per ovviare a questo problema si può pensare dunque di provare ad aumentare il valore di l di una unità ogni volta che completiamo la ricerca con un fallimento. Quindi partendo con l=0 si procede cone nella ricerca a profondità limitata; se non viene raggiunto il nodo corrispondente allo stato di goal, si incrementa l di 1 e si continua questa procedura in modo iterativo fino a trovare il nodo corrispondente allo stato di goal. In questo modo, se la soluzione eseiste la troviamo, quindi è un algoritmo completo, ma non ottimo se i costi di passo non sono unitari, dato che non vengono considerati nella scelta del nodo da espandere. La complessità temporale risulta O(b^D) e quella spaziale O(bD).