Ricerca best first
La ricerca best first è una strategia di ricerca informata in cui ad ogni passo viene espanso sempre il nodo migliore, quello più vicino all'obiettivo da raggiungere. Best first significa "prima il migliore". La ricerca best first è anche conosciuta come ricerca greedy o ricerca golosa ( ricerca avida ). Queste ultime due denominazioni hanno il pregio di mettere meglio in luce, come vedremo, anche alcuni handicap della ricerca best first. Come funziona un algoritmo di ricerca best first? Per valutare la qualità (best) dei nodi l'algoritmo si avvale di una funzione di conoscenza ( funzione euristica ). Ad esempio, può valutare la qualità dei nodi in base alla distanza aerea (in linea retta) dal nodo obiettivo senza tenere conto del cammino complessivo. Prendiamo come esempio il seguente grafo in cui l'obiettivo dell'algoritmo è raggiungere il nodo Z a partire dal nodo A.
Nel nodo iniziale A l'algoritmo di ricerca best-first deve decidere quale nodo espandere tra B e C. Il nodo B dista 12 in linea d'aria ( linea tratteggiata blu ) dal nodo obiettivo Z. Il nodo C dista 5 in linea d'aria dal nodo obiettivo Z. Sulla base della funzione di conoscenza l'algoritmo espande il nodo C, essendo quello più vicino in linea retta all'obiettivo Z. Successivamente espande il nodo D e, infine, giunge in terzo step all'obiettivo finale con un costo di cammino pari a 15. Il cammino ACDZ dell'algoritmo best-first è evidenziato in verde nel grafo ed è più efficiente del cammino alternativo ABDZ ( costo di cammino 20).
Minore complessità dell'algoritmo. Senza dover analizzare tutti i cammini possibili l'algoritmo di ricerca best first ha individuato in soli tre cicli il cammino dal nodo A al nodo Z. Ciò equivale a una minore complessità spaziale e a una minore complessità temporale della ricerca.
Ricerca incompleta e non efficiente. L'algoritmo di ricerca best first è incompleto in quanto non analizza tutte le possibilità. Inoltre, non è detto che la funzione di conoscenza sia sempre efficace. Ad esempio, nel grafo seguente il cammino ACDZ individuato dall'algoritmo di ricerca best-first ( linea rossa ) non è quello più efficiente. Il cammino più efficiente AEFZ ( linea verde ) implica il passaggio dal nodo A al nodo E, il quale essendo più distante dall'obiettivo Z rispetto al nodo C non sarà mai prescelto dall'euristica dell'algoritmo (minore distanza). Nel nodo A l'algoritmo ha scelto frettolosamente il cammino meno efficiente poiché l'euristica è errata. Da questo deriva anche il nome "ricerca golosa" o "ricerca greedy" dell'algoritmo best first.
Rischio di cammino ciclico. L'algoritmo best first non evita, inoltre, il rischio di incappare in percorsi morti, vicini all'obiettivo finale ma non collegati fisicamente ad esso. Nel grafo seguente l'algoritmo best-first individua il cammino ACD, essendo il nodo D un nodo interrotto ( vicolo cieco ), il cammino continua verso B fino a tornare al nodo di partenza A ( cammino ciclico ). Pertanto, anche nella ricerca best first occorre includere una funzione di back-tracking ( passo indietro ) nella funzione di ricerca e dedicare uno spazio di memoria riservato ai tentativi falliti al fine di evitare di incorrere in un loop ( cammino ciclico infinto ).
Scelta della funzione euristica. In questa pagina si utilizza come funzione euristica la distanza fisica in linea retta tra i nodi. È comunque soltanto una tra le tante scelte possibili. Si può, ad esempio, adottare una funzione euristica in base al colore dei nodi, al numero dei collegamenti in uscita, alla media tra la distanza dal nodo di partenza e quello di destinazione, ecc.
