Best-first search

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