Ricerca in profondità

La ricerca in profondità è un tipo di ricerca non informata che espande i nodi a partire di più profondi dell'albero di ricerca Tutti i nodi figli di un singolo ramo sono posti in una coda FIFO ( First Input First Output ) ed analizzati uno alla volta. Il funzionamento dell'algoritmo di ricerca può essere rappresentato graficamente, il numero vicino ad ogni nodo identifica l'ordine in base al quale il nodo viene analizzato dall'algoritmo di ricerca.

RICERCA IN PROFONDITA

Nella ricerca in profondità ogni singolo ramo viene espanso completamente prima di analizzare il successivo. Questa differenza consente alla ricerca in profondità di risparmiare una notevole quantità di memoria per l'esecuzione dell'algoritmo, in quanto è sufficiente memorizzare il numero dei rami da analizzare a partire dal nodo radice e i singoli nodi del cammino all'interno del ramo. Una volta analizzata la ramificazione di un ramo, la memoria può essere liberata per fare spazio all'analisi del ramo successivo. La ricerca in profondità riduce la complessità spaziale in termini di memoria rispetto alla ricerca in ampiezza. Dato un fattore di ramificazione b e una fattore di profondità massima dmax, la quantità di memoria necessaria per l'algoritmo è pari a

b dmax

Ad esempio, in un albero di ricerca con un fattore di ramificazione pari a due (b=2) e un fattore di profondità massima pari a tre (dmax=3) la complessità spaziale è stimata ad un valore pari a sei ( 2 X 3 = 6). Nel caso della ricerca in ampiezza la complessità spaziale è, invece, pari a otto ( 23 = 8 ). Tuttavia, dal punto di vista della complessità temporale (durata di esecuzione) l'algoritmo della ricerca in profondità non migliora la performance potenziale che resterebbe comunque pari a O (bdmax) come per la ricerca in ampiezza.

Va comunque osservato che, nei casi in cui la soluzione si trovasse sulla frontiera estrema dell'albero di ricerca, la ricerca in profondità ha maggiori probabilità della ricerca in ampiezza di giungere ad una soluzione profonda in un minore tempo di esecuzione (ciclo macchina) poiché l'algoritmo analizza ogni singolo ramo fino ai nodi estremi mentre la ricerca in ampiezza giunge all'analisi dei nodi più estremi soltanto negli ultimi cicli di esecuzione.

La ricerca in profondità fallisce quando lo spazio degli stati è infinito o l'algoritmo incappi nel problema del cammino ciclico. La ricerca in profondità analizza ogni singolo ramo cieco, dal nodo radice fino all'ultimo nodo-foglia agli estremi, ma se il ramo è infinito o circolare l'algoritmo entra in loop senza analizzare anche i restanti rami dell'albero di ricerca. In tale caso il tempo di elaborazione è infinito e la complessita temporale dell'algoritmo è massima. Per evitare questo problema è necessario apportare delle modifiche all'algoritmo introducendo un limite di profondita ossia un limite al numero massimo di passi per ciascun cammino di ricerca ( ricerca in profondità limitata ).

https://www.okpedia.it/ricerca_in_profondita



note


Commenti

  1. C'è un errore all'inizio. La coda di implementazione non è FIFO in una ricerca in profondità ma LIFO (Last In First Out) - 08 marzo 2015

Ricerca soluzioni

Problemi