Lezione 5 Ricerca non informata Flashcards
Quali sono le caratteristiche degli algoritmi di ricerca non informati?
Un algoritmo si dice non informato se non conosce alla perfezione il mondo che lo circonda ma ha a sua disposizione solo informazioni circostanziali su cui lavorare.
Quali sono le caratteristiche del breadth-first search?
Il breadth first search utilizza una coda fifo per la frontiera, espandendo quindi i nodi sempre nell’ordine in cui sono stati generati. In questo modo avremo un albero che si espande in maniera uniforme ad ogni livello. Questo algoritmo è limitato dal punto di vista della complessità spaziale e per certi state space anche di quella temporale.
Quali sono le caratteristiche dell’uniform cost search?
L’uniform cost search usa una coda di priorità per gli stati che hanno costo di path (quindi a partire dalla radice) inferiore. In questo modo andiamo ad espandere l’albero sempre a partire dal path meno costoso, assicurandoci così di trovare la soluzione ottimale. Rischia di avere complessità spaziale e temporale elevate.
Quali sono le caratteristiche del depth-first search?
Il depth first search si implementa con una coda LIFO per la frontiera e consiste nel percorrere fino in fondo un ramo alla volta, permettendo così di trovare soluzioni in profondità in tempo ridotto. Questo algoritmo non garantisce di trovare la soluzione migliore, e ha problemi con spazio e tempo.
Quali sono le caratteristiche del depth-limited search e dell’iterative deepening search?
Il depth limited search consiste nel limitare la profondità a cui vogliamo arrivare con il depth-first search, in modo da tutelarci contro loop e soluzioni eccessivamente lunghe, potrebbe non essere in grado di trovare una soluzione. L’iterative deepening fa la stessa cosa ma iterativamente, aumentando di volta in volta il limite di profondità fino a raggiungere una soluzione.
Quali sono le caratteristiche del bidirectional search?
Il bidirectional search consiste nell’utilizzare il nostro punto di arrivo (quando è noto) come secondo punto di partenza dell’albero di ricerca, questo riduce di molto le complessità, ma è applicabile solo quando le azioni sono bidirezionali e il punto di arrivo è noto. Questo può essere fatto con vari algoritmi di ricerca.
