Intelligenza Artificiale
Primo test intermedio a.a. 2014-15 23/10/2014
1. Utilizzando come esempio il dominio del robot aspirapolvere, descrivere la differenza tra un problema di ricerca a stato unico e un problema di ricerca a stati multipli (ambiente parzialmente osservabile).
2. Confrontare sinteticamente i seguenti algoritmi di ricerca in termini di (a) completezza, (b) complessità temporale e spaziale, (c) ottimalità della soluzione trovata: ricerca in profondità, ricerca in ampiezza, ricerca ad approfondimento iterativo.
3. Specificare sotto quali condizioni la “ricerca a costo unifome” termina trovando una soluzione ottima (se esiste).
4. Specificare i passi dell’algoritmo di ricerca A*.
5. Cosa significa che una euristica per A* è consistente? La consistenza è necessaria per garantire che la soluzione trovata (se esiste) sia ottima?
6. Descrivere brevemente come si calcola il fattore di diramazione effettivo nella valutazione delle prestazioni di una euristica per A*.
7. Descrivere brevemente la tecnica di ricerca locale “tabu search”.
8. Cosa si intende per “mosse laterali” (o passi di ricerca laterali) nella ricerca locale e a cosa servono?
9. Descrivere un metodo efficace per ordinare le variabili di un CSP durante la ricerca di una soluzione.
10. Si consideri il seguente CSP con variabili discrete: A ≠ B, A < C, B ≠ C, Dom(A)=[2,6], Dom(B)=[8], Dom(C)=[5,6,8].
a. Specificare se il CSP è arc-consistente e nel caso non lo fosse spiegare perché.
b. Indicare quali coppie di variabili (se ne esiste alcuna) che ri-entrano nella coda Q gestita dall’algoritmo AC-3 per rendere il CSP arc-consistente; assumere che inizialmente Q = [(A,C), (C,A), (C,B), (B,C),(A,B),(B,A)].
c. Specificare come può essere usato AC-3 nell’algoritmo generale (basato su backtracking) per risolvere un CSP.
