Ricerca informata

La ricerca informata è una strategia di ricerca per trovare una o più soluzioni a un problema utilizzando una funzione di conoscenza. La strategia di ricerca informata si basa sull'impiego di una conoscenza addizionale specifica al problema che si vuole risolvere e al campo di applicazione dell'algoritmo. L'algoritmo di ricerca informata è quindi dotato sia della funzione di ricerca che di una funzione di conoscenza ( funzione euristica ). La funzione di conoscenza determina l'ordine di ricerca dell'algoritmo al fine di ridurre il tempo necessario e/o il costo della ricerca. La funzione euristica stima la probabilità di trovare la soluzione nei vari nodi da selezionare e, sulla base di queste stime, modifica l'ordine dei nodi nella coda di ricerca anticipando l'analisi su quelli a maggiore probabilità di successo. La ricerca informata si distingue alla ricerca non informata che, viceversa, si limita a esplorare l'universo degli stati possibili soltanto mediante la funzione di ricerca senza avvalersi di alcuna conoscenza aggiuntiva del problema. I principali vantaggi di una ricerca informata rispetto a una ricerca non informata sono i seguenti:

• Evitare l'esplosione combinatoria. L'algoritmo di ricerca informata non necessita l'espansione completa di tutti i nodi dell'albero di ricerca.
• Decidere quale nodo espandere. Nel processo di ricerca l'algoritmo decide quale nodo espandere tra quelli possibili in un medesimo livello senza doverli espandere tutti.
• Riconoscere i cammini promettenti. Sulla base della funzione di conoscenza l'algoritmo stima la probabilità di successo dei vari nodi/cammini prima di espanderli nel processo di ricerca.

In conclusione, la ricerca informata non elimina il processo di ricerca ma ne riduce fortemente i tempi di esecuzione. Pur non essendo una ricerca completa, la ricerca informata consente di raggiungere comunque soluzioni accettabili con maggiore efficienza rispetto a una ricerca non informata. Esistono diverse tipologie di ricerca informata, qui di seguito elenchiamo le principali:

• Ricerca best-first
• Ricerca A-star
• Ricerca IDA* ( Iterative Deepening A* )
• RBFS ( Recursive Best First Search )
• MA* e SMA* ( Simplified Memory-bounded A* )
• Ricerca euristica con memoria limitata

Esempio di ricerca informata. Per cercare il cammino da un nodo di partenza a uno di destinazione la funzione euristica può stimare il costo di cammino in base alla distanza aerea tra i nodi intermedi. In tal modo viene anticipato l'ordine di analisi dei nodi intermedi più vicini in linea d'aria. Ciò, ovviamente, non implica che siano sempre anche quelli più vicini in linea stradale ma aumenta la probabilità media di trovare prima la soluzione al problema rispetto a una strategia di ricerca non informata.