A differenza del precedente articolo in cui abbiamo visto diversi tipi di ricerca non informata, in questo articolo vedremo come alcuni algoritmi elaborano i percorsi in base alle informazioni sui nodi e sugli archi in loro possesso. Le informazioni euristiche su quali nodi sono più promettenti possono guidare la ricerca modificando il nodo selezionato alla riga 11 dell'algoritmo di ricerca generico.
Questi tipi di algoritmo si basano su una funzione euristica h ( n ), prende in input un nodo n e restituisce un valore reale positivo che è la stima del costo del percorso meno costoso dal nodo n al nodo obiettivo. La funzione h ( n ) è un'euristica ammissibile se h ( n ) è sempre minore o uguale all'attuale costo del percorso meno costoso dal nodo n al nodo obiettivo.
La funzione euristica utilizza le informazioni che possono essere facilmente ottenibili sui nodi. C'è sempre un compromesso tra il costo per determinare il valore euristico e l'accuratezza del valore stesso. Un metodo standard per derivare questo tipo di funzione è risolvere un problema più semplice e utilizzare il costo per l'obiettivo nel problema semplificato come funzione euristica del problema originale.
Top comments (0)