Ricerca in avanti
La ricerca in avanti è una tecnica e un algoritmo di ricerca. Nella ricerca in avanti il dato viene cercato a partire da una soluzione iniziale, fino a giungere all'obiettivo della ricerca stessa. In un albero logico la situazione iniziale è generalmente la radice dell'albero, il nodo più in alto. La ricerca prosegue dall'alto verso il basso in modo orizzontale ( ricerca in profondità ) oppure in modo orizzontale. Nel seguente diagramma è rappresentato un esempio di processo di ricerca in avanti in profondità ( progressione ).
Il precedente esempio mostra il caso di una ricerca in avanti non informata. L'algoritmo di ricerca scandaglia tutto l'albero logico in progressione fino al raggiungimento dell'obiettivo. Nel caso in esame l'obiettivo è situato nell'ultimo nodo in profondità sulla destra ( goal ) ed è, pertanto, la situazione peggiore poiché l'algoritmo deve scandagliare interamente l'albero logico prima di arrivare alla soluzione ( 12 passi ). In media, un algoritmo di ricerca in avanti non informata impiega n/2 passi prima di giungere alla soluzione ( 6 passi ). La ricerca in avanti è completa ( completezza ) poiché giunge sempre alla soluzione se quest'ultima esiste. La ricerca in avanti può essere utilizzat anche per cercare una soluzione all'interno di uno spazio degli stati.
Inefficienza. La ricerca in avanti è un algoritmo di ricerca fortemente inefficiente, soprattutto nei casi della ricerca non informata, poiché analizza anche le situazioni irrilevanti e quelle ridondanti ( ripetute ). Il processo di ricerca implica un elevato consumo di risorse computazionali. In un grafo le combinazioni dei percorsi possibili per giungere all'obiettivo a partire da una situazione iniziale possono essere molteplici. Ad esempio, nel precedente grafo l'obiettivo ( goal ) è distante soltanto due passi dalla situazione iniziale ( start ) ma l'algoritmo della ricerca in avanti non conosce la mappa degli stati ed è costretto ad analizzare molte combinazioni di percorso prima di trovare quello che conduce all'obiettivo. La ricerca in avanti è, quindi, una tecnica di ricerca completa ma inefficiente.
Ricerca informata.Per aumentare l'efficienza della ricerca in avanti è possibile utilizzare delle euristiche ( ricerca in avanti informata ) facendo selezionare all'algoritmo prima i percorsi con maggiore probabilità di successo. La ricerca informata consente di posticipare l'analisi dei percorsi meno promettenti.
- Complessità spaziale e temporale. La ricerca in avanti non informata può richiedere un elevato consumo di risorse di memoria e un elevato tempo di esecuzione. Ad esempio, per cercare un libro a partire dal codice ISBN la ricerca in avanti non informata enumera i record dell'intero database, fino a giungere al codice ISBN ricercato. È evidente che si tratti di un processo di ricerca non efficiente. In un grafo la complessità della ricerca in avanti cresce in modo esponenziale rispetto al numero dei dati. Ad esempio, per trovare un percorso in un grafo, anche se composto d pochi nodi e archi, l'algoritmo della ricerca in avanti è costretto a elaborare migliaia di combinazioni di percorso prima di giungere a quello giusto.
