Ricerca bidirezionale

La ricerca bidirezionale è un metodo di ricerca dati in un albero logico. A partire da due nodi, un nodo iniziale e un nodo finale ( nodo obiettivo ), l'algoritmo effettua due ricerca parallele. La prima ricerca scandaglia i cammini a partire dal nodo iniziale sui nodi successori. La seconda ricerca scandaglia a ritroso i cammini a partire dal nodo finale sui nodi predecessori. L'algoritmo di ricerca bidirezionale, infine, verifica l'esistenza di punti di contatto a metà strada tra le due ricerche.

Per trovare il percorso tra il nodo di partenza S e il nodo di destinazione O l'algoritmo bidirezionale verifica la coincidenza dei nodi sulla frontiera delle due ricerche. Ad esempio, il nodo A e il nodo B compaiono sulla frontiera di entrambe le ricerche. Una volta individuati i nodi comuni sulla frontiera si può facilmente individuare il cammino completo dal nodo iniziale S (start) al nodo finale O (obiettivo). Il vantaggio della ricerca bidirezionale consiste nella minore complessità temporale rispetto ad una ricerca in ampiezza. Nel caso della ricerca bidirezionale ognuna delle due ricerche si interrompe a metà strada. La complessità dell'algoritmo è quindi la seguente

b^d/2 + b^d/2

La ricerca in ampiezza, viceversa, ha una complessità superiore pari a O(b d). Nel caso della ricerca in ampiezza l'algoritmo deve scandagliare tutti i nodi di tutti i rami fino in profondità. Nel caso della ricerca bidirezionale, invece, le due ricerche si interrompono ognuna a metà della profondità senza penalizzare la completezza della ricerca.

b^d > b^d/2 + b^d/2

Differenza tra ricerca bidirezionale e ricerca in ampiezza. Per comprendere meglio la differenzia proviamo ad esplodere completamente l'albero logico a partire dal nodo iniziale fino alla massima profondità d. Nello schema seguente rappresentiamo l'albero logico della ricerca in ampiezza a partire dal nodo di partenza S. Per ovvi motivi di spazio la rappresentazione dell'albero non è completa, è comunque utile per fare un confronto visivo del grado di complessità dei due algoritmi.

L'algoritmo di ricerca in ampiezza deve scandagliare quasi tutte le combinazioni possibili prima di giungere al nodo obiettivo O sulla frontiera dell'albero di ricerca. Il numero dei nodi da scandagliare si riduce notevolmente, invece, nel caso della ricerca bidirezionale dove le due ricerche si interrompono ad una profondità inferiore. L'algoritmo di ricerca bidirezionale è, pertanto, un metodo più efficiente dell'algoritmo di ricerca in ampiezza a parità di completezza della ricerca. Ad esempio, una ricerca con fattore di ramificazione 2 e una profondità 5 implica un livello di complessità pari a 32 (2⁵) con la ricerca in ampiezza e un livello di complessità pari a 16 (2³+2³) con la ricerca bidirezionale.

Completezza. Pur avendo una minore complessità l'algoritmo di ricerca bidirezionale non penalizza la completezza della ricerca. Le due ricerche parallele consentono di raggiungere il medesimo livello di completezza di una ricerca in ampiezza in un tempo di elaborazione notevolmente inferiore.

Conoscenza obiettivo. L'algoritmo di ricerca bidirezionale implica la conoscenza del nodo obiettivo. Soltanto conoscendo l'esatta posizione del nodo obiettivo è possibile avviare una ricerca a ritroso sui nodi predecessori.

Individuazione predecessori. Non sempre è facile risalire ai predecessori di un nodo. La difficoltà di procedere ad una ricerca a ritroso è tanto maggiore quanto più il problema da risolvere ha una natura astratta. Inoltre, non è detto che le azioni siano sempre reversibili.