Intelligenza Artificiale
Primo test intermedio a.a. 2013-14 6/11/2013
1. In quale classe di problemi di ricerca sono necessarie azioni sensoriali per acquisire informazioni durante l’esecuzione della soluzione? Rispondere facendo un esempio nel dominio del robot aspirapolvere.
2. Descrivere la complessità computazionale temporale dell’algoritmo di ricerca ad approfondimento iterativo a partire da fattore di diramazione b e profondità d del nodo goal più vicino alla radice dell’albero di ricerca. Indicare come viene determinata.
3. Si consideri un problema di ricerca in cui: (a) ci sono varie soluzioni; (b) è noto che le soluzioni ottime si trovavo a profondità 50 dell’albero di ricerca; (c) il fattore di diramazione è uguale a 4. Se non dispongo di alcuna euristica e sono interessato a trovare la soluzione ottima, in pratica qual è l’algoritmo di ricerca cieca che mi conviene usare? Motivare la risposta.
4. Descrivere una tecnica per evitare di attraversare percorsi ciclici dello spazio di ricerca visitato dall’algoritmo di ricerca in profondità. Specificare una soluzione che minimizzi lo spazio aggiuntivo necessario.
5. Descrivere la formula probabilistica utilizzata dall’algoritmo di ricerca Simulated Anealing per randomizzare la ricerca.
6. Descrivere le differenze tra un’euristica ammissibile e un’euristica consistente per A*. Quali sono le relative proprietà per A*?
7. Descrivere almeno una delle seguenti per l’algoritmo di ricerca hill-climbing specificando quando sono utili: (a) Tecnica della “prima scelta” (b) Tecnica delle mosse laterali.
8. Che differenza c’è nella formulazione di un problema di ricerca tradizionale (off-line) e un problema di ricerca on-line? Perché l’algoritmo Agente-Online-DFS funziona solo negli spazi degli stati dove le azioni sono reversibili?
9. Dato il seguente Diagramma degli
Stati in cui lo stato più a sinistra è l’unico
nodo goal e il nodo più in alto è l’unico
stato iniziale
A. Indicare profondità e fattore di diramazione dell’albero di ricerca costruito dalla procedura di ricerca in ampiezza (RA)
B. Numerare i nodi del diagramma degli stati in ordine crescente dall’alto al basso e da sinistra verso destra. Utilizzando tale numerazione, indicare la sequenza di numeri corrispondente alla sequenza di nodi visitati dall’algoritmo RA per trovare lo stato goal.
10. Descrivere brevemente la tecnica del forward checking nella risoluzione di un CSP.
