Spazio degli stati. Grafo orientato e alberi di ricerca

Lo spazio degli stati per poter essere studiato viene per convenzione rappresentato con un grafo orientato. Gli stati che man mano si verificano vengono chiamati in un grafo nodi. Il modo di procedere attraverso i diversi stati viene di solito chiamato genera-e-verifica, ossia nel passaggio da uno stato ad un altro vengono memorizzati quei dati e solo quelli che di volta in volta servono a passare dall’uno all’altro verso la soluzione. La struttura che facilita notevolmente la ricerca di una soluzione è quella ad albero, per questo si parla di alberi di ricerca. Ogni nodo dell’albero conterrà la descrizione di uno stato insieme all’informazione utile al proseguimento della ricerca e alla ricostruzione della soluzione. L’obiettivo degli algoritmi di ricerca  quello di trovare una soluzione, cioè di generare uno stato finale.
Le strategie di ricerca possono allora avere due direzioni:
se si parte da una soluzione iniziale e si cerca di arrivare a quella finale si parla di ricerca in avanti o ricerca guidata dai dati
se invece si parte da uno dei possibili stati soluzione e ci si chiede da quali stati iniziali esso possa essere stato generato, allora si parla di ricerca all’indietro o ricerca guidata dall’obiettivo