Lezione 6 Algoritmi di ricerca informati Flashcards
In cosa gli algoritmi di ricerca informati si differenziano da quelli non informati?
Gli algoritmi informati hanno a disposizione una funzione euristica, che viene calcolata a priori per ogni stato dello state space e ha lo scopo di darci maggiori informazioni su di esso, in modo da rendere la ricerca più facile (es:distanza dal livello del mare o distanza ad aria dal traguardo)
Quali sono le definizioni di ammissibilità e consistenza di una funzione euristica?
Una funzione euristica si dice ammissibile se al massimo sottostima la quantità che sta rappresentando. Si dice consistente se il valore euristico di un qualsiasi stato di partenza è minore o uguale alla somma tra il costo dell’azione compiuta per raggiungere un qualsiasi stato foglia e il valore euristico dello stesso.
Quali sono le caratteristiche del greedy best first search?
Il greedy best first search è un best first che usa come funzione di valutazione la funzione euristica (andando a minimizzarla o massimizzarla in base alle necessità). Non è ottimo perchè si rischia di cadere e perdere tempo in minimi locali e non c’è nessun modo per evitarli.
Quali sono le caratteristiche dell’A* search?
L’A* search unisce aspetti dell greedy best first search e dell’uniform cost search. Usiamo come funzione di evaluation la somma tra il path cost e la funzione euristica, andando quindi ad accorgerci di quando un path diventa troppo lungo per essere buono. Se la funzione euristica è ammissibile l’A* è cost-efficient, se è anche consistente l’A* è completo.
Quali sono le caratteristiche del weighted A* search?
Aggiunge una costante di peso > 1 alla funzione euristica, in modo che la ricerca possa cercare di ottimizzare prima quello (e quindi in teoria raggiungere prima il traguardo) tenendo comunque conto anche del path cost.
Quali sono le caratteristiche dell’iterative deepening A* search?
Funziona come un A* in cui aggiungiamo un valore di cutoff alla funzione di evaluation, che andiamo ad aumentare iterativamente.
