Intelligenza Artificiale
Test intermedio a.a. 2016-17 15/11/2016
1. Sia G il diagramma (o grafo) degli stati per un problema di ricerca e T l’albero di ricerca generato da un algoritmo di ricerca per risolvere il problema. Spiegare perché:
I nodi di G possono essere in numero inferiore di quelli di T.
I nodi di G possono esser in numero superiore a quelli di T.
2. Perché nell’algoritmo di ricerca “a costo uniforme” i costi degli operatori non possono essere negativi?
3. Descrivere ad alto livello l’algoritmo di ricerca euristica Weighted-A*. Specificare sotto quali condizioni si può garantire che verrà trovata una soluzione ottima (assumendo che la memoria e il tempo di
computazione a disposizione non hanno limiti).
4. Specificare i passi dell’algoritmo di ricerca A* che usa la lista CLOSED dei nodi già visitati. Per semplicità assumere che la funzione euristica h abbia la proprietà di consistenza.
5. Descrivere la tecnica dei “pattern database” per costruire un’euristica ammissibile. Fare esempio per il rompicapi dell’8.
6. Descrivere come interagiscono le k ricerche locali avviate dall’algoritmo Local Beam Search.
7. Perché l’algoritmo di ricerca locale “Simulated Annealing” è un algoritmo randomizzato (o probabilistico)?
8. Si consideri un problema di ricerca on-line per cercare un percorso all’interno di un labirinto che porta all’uscita. Se tale percorso esiste e si utilizza l’algoritmo di ricerca in profondità on-line, il percorso verrà trovato? Quante volte può essere visitato (dalla ricerca e dall’esecuzione) uno stesso stato al massimo?
9. Descrivere la tecnica del forward checking da utilizzarsi all’interno di un algoritmo di backtracking per risolvere un CSP con variabili discrete. Selo si ritiene utile, nella descrizione fare esempi con il problema della colorazione di una mappa geografica.
10. Siano X e Y due variabili di un CSP con domini Dom(X) = [2,4,6,8,100] e Dom(Y)=[1,3,4] e vincolo Y2 > X. Determinare se X e Y sono arc consistenti. Se non lo fossero trasformare i domini di X e Y per soddisfare la proprietà, senza togliere soluzioni al CSP.
