Agenti risolutori di problemi: soluzione del problema

La fase successiva alla formulazione del problema è la ricerca della soluzione dello stesso. Per fare ciò si parte dallo spazio degli stati dal quale si costruisce l'albero di ricerca. Il procedimento è iterativo: si considera in prima istanza lo stato iniziale e si crea un nodo corrispondente, detto radice, si applica il test obiettivo al nodo in analisi, si espande il nodo se non soddisfa il test e si sceglie un altro nodo e si continua dall'applicazione del test obiettivo.
Un nodo è una struttura dati formata da cinque elementi:

• stato dello spazio degli stati a cui il nodo è associato, da notare che ad uno stesso stato possono corrispondere più nodi;
• puntatore al padre, ovvero al nodo da cui è stato generato; questo servirà per ricostruire a ritroso il cammino dal goal raggiunto fino allo stato iniziale;
• azione che porta al nodo;
• costo del cammino che porta dalla radice al nodo (questo compo si chiama g(n));
• profondità del nodo.

Per creare l'albero di ricerca è utile definire un insieme, che viene detto frontiera, dei nodi generati nell'albero stesso ma non ancora espansi. Il problema principale risulta allora ordinare l'insieme in modo che l'algoritmo di creazione dell'albero estrarrà ad ogni passo il nodo opportuno.