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).


(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 o uguale al costo dello stato finale). Poiché tutti
    gli stati compresi nel rettangolo con vertici opposti (0, 0) e
    (x, y) soddisfano tali condizioni, nel caso pessimo,
    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.