Intelligenza artificiale e ricerca euristica

ricerca euristica: questo tipo di ricerca viene utilizzata per problemi di grani dimensioni. Essa viene utilizzata per determinare in maniera previa i cammini più promettenti. Un’euristica  una tecnica che migliora il processo di ricerca delle soluzioni cercando il cammino migliore da compiere per raggiungerla o addirittura la soluzione migliore tra tante che potrebbero essere scelte. Essa associa ad ogni nodo dello spazio degli stati un valore numerico, un “peso” che rappresenta la desiderabilità dello stato corrispondente. Questa desiderabilità viene solitamente espressa in termini di vicinanza o lontananza dallo stato finale. Nonostante il termine “euristico” venga utilizzato con varie accezioni (deriva dal greco => scoprire) attualmente esso designa un metodo che migliora il comportamento di un algoritmo di ricerca automatica. Ma nel nostro caso specifico euristica “è una funzione che stima il costo di una soluzione”1 (funzione legata all’algoritmo A* inteso come un algoritmo generale). La funzione è f(n) = g(n) + h(n) dove g(n) è il costo pagato per arrivare dal nodo iniziale al nodo n, mentre h(n) è una stima del costo che si dovrà pagare per arrivare al nodo soluzione. Analizzando la funzione si nota che la funzione euristica è solo h(n) che si può stimare solo in relazione alla conoscenza che si ha del problema e degli eventuali passaggi che devono ancora compiersi per giungere alla soluzione. Il modo più naturale per utilizzare informazioni euristiche è nel decidere quale nodo dello spazio degli stati esplorare per primo.