Esercizio 1 Si consideri la seguente griglia 2D (illimitata) come spazio di ricerca. | | | | | | | | -.--.--.--.--.--.--.--.- | | | | | | | | -.--.--.--.--.--.--.--.- | | | | | | | | -.--.--.--X--.--.--.--.- | | | | | | | | -.--.--.--.--.--.--.--.- | | | | | | | | -.--.--.--.--.--.--.--.- | | | | | | | | Lo stato iniziale è costituito dall'origine (contrassegnata con la X) e lo stato goal è individuato dalle coordinate (x, y). (a) Quale è il fattore di branching per questo spazio degli stati ? RISPOSTA: 4 (numero di vicini per ogni locazione.) (b) Quanti stati distinti ci sono a profondità k ? RISPOSTA: Gli stati a distanza d dalla origine formano un quadrato ruotato di 45 gradi (rombo) sulla griglia: | | | | | | | | -.--.--.--0--.--.--.--.- | | |/ | \| | | | esempio per d=2 -.--.--0--.--0--.--.--.- | |/ | | | \| | | -.--0--.--X--.--0--.--.- | |\ | | | /| | | -.--.--0--.--0--.--.--.- | | |\ | /| | | | -.--.--.--0--.--.--.--.- | | | | | | | | Si considerino ora i due casi seguenti: - k è pari: allora a profondità k si trovano tutti gli stati a distanza k, k/2, k/4,..., 0, dall'origine. Infatti, partendo dall'origine si devono percorrere esattamente k tratti (archi) della griglia in una qualunque direzione (eventualmente tornando indietro verso l'origine), quindi lo stato di arrivo non potrà trovarsi a distanza dispari dall'origine. - k è dispari: con una argomentazione simile alla precedente si conclude che a profondità k si trovano tutti gli stati a distanza 1, 3, ..., k, dall'origine. In tutti e due i casi gli stati da considerare saranno disposti su rombi alternati e concentrici sull'origine. E' quindi facile vedere che il numero di tali stati è (k+1)^2. (c) Assumendo una ricerca breadth-first senza il controllo di stati ripetuti, quanti sono i nodi espansi nel caso pessimo ? RISPOSTA: si noti che lo stato di arrivo (x, y) si trova a distanza |x|+|y| dall'origine. Quindi, poiché non si controllano gli stati ripetuti, si espanderanno (nodo radice) 4^0 + (nodi a livello 1) 4^1 + (nodi a livello 2) 4^2 + .... ... (nodi a livello |x|+|y|-1) 4^(|x|+|y|-1) + (nodi a livello |x|+|y|, tranne il nodo di arrivo) 4^(|x|+|y|) -1 = 1 + 4 + 4^2 + 4^3 + ... + 4^(|x|+|y|) -1 = = (4^(|x|+|y|+1) - 1)/(4 - 1) -1 = = (4^(|x|+|y|+1) - 1)/3 -1 Si noti che per il livello |x|+|y| si è assunto che lo stato di arrivo sia l'ultimo ad essere esaminato per quel livello (caso pessimo) e che quest'ultimo non ha bisogno di essere espanso poiché il test di goal avrà successo. In effetti, se lo stato di arrivo non si trova su uno degli assi cartesiani, il caso pessimo è livemente più favorevole perchè esistono almeno due modi di raggiungere lo stato con la percorrenza di |x|+|y| tratti, e quindi esistono 2 nodi a livello |x|+|y| che rappresentano lo stesso stato di arrivo (e quindi si devono espandere (4^(|x|+|y|+1) - 1)/3 -2 nodi, assumendo |x|+|y| > 1). (d) Assumendo una ricerca breadth-first con il controllo di stati ripetuti, quanti sono i nodi espansi nel caso pessimo ? RISPOSTA: in questo caso la ricerca procede "verso l'esterno", cioè visitando stati disposti su rombi sempre più esterni. Ad ogni rombo appartengono esattamente 4k stati, tranne l'origine che costituisce un rombo degenere con uno stato (quello iniziale). Quindi, nel caso pessimo si espandono: (nodo radice) 1 + (nodi a livello 1) 4*1 + (nodi a livello 2) 4*2 + .... ... (nodi a livello |x|+|y|-1) 4*(|x|+|y|-1) + (nodi a livello |x|+|y|, tranne il nodo di arrivo) 4*(|x|+|y|) -1 = 1 + 4*(1+2+ ... + (|x|+|y|) ) - 1 = = 4*(|x|+|y|)*(|x|+|y|+1)/2 = = 2*(|x|+|y|)*(|x|+|y|+1) (e) Dire se la funzione euristica h(u,v) = |u-x| + |v-y| è ammissibile per lo stato (u, v). RISPOSTA: Si, poiché coincide esattamente con il costo da sostenere per raggiungere lo stato finale. In particolare, corrisponde alla distanza Manhattan. (f) Si consideri l'utilizzo della funzione euristica di sopra all'interno di A* con il controllo degli stati ripetuti. Si dica se è vero che A* espande O(|x| + |y|) nodi prima di terminare e motivare la risposta. RISPOSTA: Falso. Purtroppo A*, essendo un algoritmo ottimo, espande tutti i nodi che sono su cammini che conducono allo stato finale (e che hanno costo inferiore al costo dello stato finale). Poiché tutti gli stati compresi nel rettangolo con vertici opposti (0, 0) e (x, y) soddisfano tali condizioni, tutti sono espansi e quindi A* espande O((|x| + |y|)^2) nodi prima di terminare. (g) Si dica se h, come definita al punto (e), rimane ammissibile nel caso in cui alcune connessioni (tratti) siano rimossi. RISPOSTA: Vero. La rimozione di connessioni implica la necessità di allungare il percorso e quindi h restituisce una sottostima del costo effettivo. (h) Si dica se h, come definita al punto (e), rimane ammissibile nel caso in cui si aggiungano collegamenti diretti fra stati non adiacenti. RISPOSTA: Falso. In questo caso si creano delle scorciatoie e quindi h può restituire una sovrastima del costo effettivo. Esercizio 2 Si consideri la scacchiera del gioco degli scacchi e il pezzo cavallo. La mossa del cavallo consiste in una L, cioè se la casella in cui esso si trova ha coordinate (0,0), le caselle da esso raggiungibili sono esprimibili dalle coordinate (u,v) che appartengono all'insieme {(2,1), (1,2), (-1,2), (-2,1), (-2,-1), (-1,-2), (1,-2), (2,-1)}. Si assuma una scacchiera illimitata. (a) dato un cavallo in posizione (0,0) che ha come goal quello di raggiungere la casella (x,y) nel minor numero di mosse possibili, si dica come, senza costruire una soluzione, si possa decidere se il numero di mosse necessarie sia pari o dispari. RISPOSTA: ad ogni mossa il cavallo passa da una casella di un colore ad una casella di colore diverso. Quindi se la casella da raggiungere è dello stesso colore della casella (0,0) allora è necessario un numero pari di mosse, altrimenti un numero dispari. Matematicamente tale condizione si può esprimere andando a verificare se |x|+|y| è pari o dispari. (b) dire se l'euristica h(x,y) = |¯ (|x|+|y|)/3 ¯| è ammissibile. RISPOSTA: si, corrisponde alla distanza Manhattan. Corrisponde a considerare ogni mossa come uno spostamento di 3 caselle in una qualunque direzione (non necessariamente ad L). (c) si considerino k cavalli presenti simultaneamente sulla scacchiera in posizione s1, ..., sk e con caselle goal e1,...,ek. In questo contesto, una mossa consiste nel muovere simultaneamente fino a k cavalli, ma una casella non può accogliere simultaneamente più di un cavallo. Dire quale è il massimo fattore di branching per questo spazio degli stati. RISPOSTA: 9^k, infatti ogni cavallo ha a disposizione le 8 mosse canoniche, più la possibilità di non muovere. (d) nel contesto del punto (c) si supponga che h_i sia una euristica ammissibile per il problema dove il cavallo i è considerato indipendentemente dagli altri. Si dica quale delle seguenti euristiche è ammissibile per il problema con tutti i k cavalli: 1) min{h_1,...,h_k} 2) max{h_1,...,h_k} 3) h_1+...+h_k RISPOSTA: solo 1) e 2). In particolare, se le h_i fossero esatte, 2) sarebbe esatta per il problema rilassato dove i cavalli possono occupare in più di uno una generica casella. Ovviamente 1) è ammissibile perchè è sempre una sottostima del costo reale. 3) non è ovviamente ammissibile perchè, sommando tutte le h_i restituisce una sovrastima: ad esempio, se ogni cavallo fosse esattamente ad una mossa dal proprio goal, la euristica restituirebbe k invece di 1. (e) quale fra le euristiche 1) e 2) del punto (d) è la migliore ? Giustificare la risposta. RISPOSTA: ovviamente 2) perchè 1) < (o uguale) 2) per ogni stato, cioè 2) domina 1).