Esercizio 2 (continua)

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

(e) 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)


(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|) nodi prima di terminare.

(g) Si dica se h, come definita al punto (c), 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 (c), 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.