Best-first search

Best-first search (letteralmente "ricerca prima il migliore") è una strategia di ricerca informata utilizzata per la risoluzione di problemi basati sulla ricerca ed è alla base dei moderni algoritmi di intelligenza artificiale. Rispetto alle strategie di ricerca non informata, di cui si fa uso nel caso in cui non si hanno informazioni specifiche sugli stati del problema oltre la definizione del problema, la ricerca best-first, come tutte le altre strategie di ricerca informata, sfrutta la conoscenza di ulteriori dettagli sugli stati del problema da risolvere.

Best-first search
Classe	Algoritmo di ricerca
Struttura dati	Albero
Caso peggiore temporalmente	$b^{m}$
Caso peggiore spazialmente	$b^{m}$
Ottimale	no
Completo	sì

Si presuppone che il problema sia rappresentato come un albero di ricerca, in cui ogni nodo rappresenta uno stato ben preciso del problema e i nodi foglia costituiscono gli stati obiettivi. La radice è lo stato iniziale del problema. Ogni singolo cammino dalla radice ad una qualsiasi foglia dell'albero rappresenta una soluzione al problema. L'obiettivo è quello di trovare la soluzione più efficiente in termini di velocità di esecuzione e di occupazione di memoria.

La strategia di best-first search implementa un'apposita funzione di valutazione $f(n)$ che ha il compito di selezionare, ad ogni passo della ricerca, il prossimo nodo da espandere. Ad ogni passo, dunque, tra tutti i nodi possibili da espandere l'algoritmo sceglie il nodo con la funzione di valutazione più bassa (da cui best-first). Una funzione di questo tipo viene generalmente detta euristica e ha il compito di selezionare, di volta in volta, il nodo che sembra condurre alla soluzione ottimale del problema.

Bibliografia

• Stuart J. Russell, Peter Norvig, Intelligenza artificiale: un approccio moderno, Pearson Education Italia, 2005. ISBN 887192228X.

Voci correlate

• Ricerca greedy
• Algoritmo A*
• Recursive best-first search
• Beam search

Collegamenti esterni

• best-first search, su sapere.it, De Agostini.
• (EN) Technical definition of best-first search, su encyclopedia.com.