Ricerca all'indietro

La ricerca all'indietro è una tecnica logico-informatica di ricerca dei dati e delle soluzioni di un problema. A partire dall'obiettivo da raggiungere, l'algoritmo della ricerca all'indietro ricostruisce il cammino per regressione fino a una determinata situazione di partenza. La ricerca prosegue dal basso verso l'alto, dal nodo figlio al nodo padre ( nodo precedente ), escludendo i nodi non rilevanti, quelli che non hanno alcun legame con l'obiettivo da raggiungere. Nel seguente diagramma è rappresentato un esempio di ricerca all'indietro ( regressione ).

Il precedente esempio mostra il caso di una ricerca all'indietro. È evidente il vantaggio computazionale rispetto a un algoritmo di ricerca in avanti. Una ricerca in avanti non informata avrebbe scandagliare l'intero albero logico, dall'alto al basso, prima di raggiungere il nodo obiettivo ( 12 passi ). Non sapendo quali nodi sono rilevanti e quali non lo sono, l'algoritmo della ricerca in avanti enumera tutte le combinazioni. La ricerca all'indietro, invece, impiega soltanto due passi per collegare il nodo obiettivo con il nodo di partenza. Il vantaggio è ancora più grande se la tecnica di ricerca all'indietro è applicata a uno spazio di stati, come nel grafo seguente:

Nodi rilevanti. L'algoritmo della ricerca all'indietro concentra l'elaborazione soltanto sui nodi rilevanti, ossia quelli che hanno una relazione con l'obiettivo da raggiungere. Ciò consente di non prendere in considerazione i cammini e i nodi non rilevanti, attuando una potatura logica al contrario.

Informazione sugli stati precedenti. La ricerca all'indietro è possibile soltanto se l'algoritmo di ricerca è in grado di ricostruire le condizioni di origine di ogni grafo, ossia il legame con i suoi nodi precedenti e con gli stati precedenti. In caso contrario, in mancanza di tali informazioni, l'algoritmo della ricerca all'indietro non può attuare il processo di regressione logica.