Best-first search - Wikipedia
Da Wikipedia, l'enciclopedia libera.
| Best-first search | |
|---|---|
| Classe | Algoritmo di ricerca |
| Struttura dati | Albero |
| Caso peggiore temporalmente | 
|
| Caso peggiore spazialmente |
|
| Ottimale | no |
| Completo | sì |
| Manuale |
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.
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 
- Stuart J. Russell, Peter Norvig, Intelligenza artificiale: un approccio moderno, Pearson Education Italia, 2005. ISBN 887192228X.
- best-first search, su sapere.it, De Agostini.
- (EN) Technical definition of best-first search, su encyclopedia.com.