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
ClasseAlgoritmo di ricerca
Struttura datiAlbero
Caso peggiore temporalmente
Caso peggiore spazialmente
Ottimaleno
Completo

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 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

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

Voci correlate

modifica

Collegamenti esterni

modifica
  Portale Informatica: accedi alle voci di Wikipedia che trattano di informatica