Albero di ricerca

L'albero di ricerca è una rappresentazione grafica del funzionamento di un algoritmo di ricerca. Nell'intelligenza artificiale l'albero di ricerca è la rappresentazione delle sequenze di azioni che un'agente razionale può effettuare a partire da un determinato stato iniziale. Nella rappresentazione di un albero di ricerca il nodo padre consiste nello stato iniziale dell'ambiente Al nodo padre sono collegati gli stati conseguenti per ogni azione possibile. Ogni azione possibile viene rappresentata tramite un collegamento (o ramo) che unisce il nodo padre con il nodo figlio. Ogni nodo figlio identifica lo stato conseguente dell'azione I nodi dell'albero di ricerca sono gli stessi dello spazio degli stati del problema da risolvere. Ogni nodo figlio viene ulteriormente espanso con le azioni possibili a partire da quello stato e così via.

Il processo di apertura dei nuovi nodi a partire da un nodo è detto espansione. Un nodo privo di ulteriori azioni possibili è un nodo terminale, o nodo foglia, e contribuisce a delimitare la frontiera degli stati. Il processo di ricerca si ferma quando lo stato di un nodo eguaglia lo stato obiettivo, ossia quando si trova la soluzione del problema. L'albero di ricerca è uno strumento utilizzato nel campo di studio dell'informatica, del problem solving e dell'intelligenza artificiale. Nell'analisi informatica consente di analizzare e rappresentare sul piano tramite un grafo il funzionamento di un algoritmo di ricerca, al fine di migliorare e ottimizzare la strategia e il processo della ricerca.