Ricerca informata - greedy best-first, A∗ ed euristiche

Le strategie di Ricerca nello spazio degli stati - formulazione dei problemi e ricerca non informataUn agente risolutore di problemi è un agente basato su obiettivi con rappresentazione atomica: formula un problema (stato iniziale, azioni, modello di transizione, test dell'obiettivo, costo dei passi) e cerca una sequenza di azioni che porta a uno stato obiettivo costruendo un albero di ricerca. Le strategie non informate usano solo la definizione del problema e si distinguono per l'ordine di espansione della frontiera: ampiezza (coda FIFO), costo uniforme (coda con priorità sul costo g), profondità (pila LIFO), profondità limitata, approfondimento iterativo e ricerca bidirezionale. Si confrontano per completezza, ottimalità, tempo e spazio in funzione di b, d, m; tutte sono casi di best-first search con una diversa funzione di valutazione f.Ricerca nello spazio degli stati - formulazione dei problemi e ricerca non informata → non sanno quanto sia lontano l'obiettivo. Qui si aggiunge quell'informazione sotto forma di una funzione euristica, e si ottiene una ricerca che si "orienta" verso l'obiettivo. Poi si passa ai problemi in cui il cammino non conta, risolti con la ricerca locale. Fonte: slide del corso di Intelligenza Artificiale, Ing. dell'Informazione UniPD, con il laboratorio 3.

Ricerca informata e funzione euristica

L'idea: associare a ogni nodo $n$ una funzione euristica $h(n)$, la stima del costo del cammino più economico da $n$ a un obiettivo, ed espandere il nodo più "desiderabile". L'implementazione è la stessa dell'ampiezza e del costo uniforme: la frontiera è una coda con priorità ordinata per desiderabilità decrescente. Due casi speciali: greedy best-first e A∗.

Esempio che ritorna in tutta la nota: la mappa della Romania con obiettivo Bucarest e come euristica la distanza in linea retta (straight-line distance) da Bucarest:

Greedy best-first search

Definizione. La ricerca greedy best-first espande il nodo che sembra più vicino all'obiettivo: $f(n) = h(n)$, con $h(n)$ stima del costo da $n$ all'obiettivo più vicino.

Esempio: da Arad a Bucarest con $h_{SLD}$ (grafo con tabella dei raggiunti):

Cammino Arad $\to$ Sibiu $\to$ Fagaras $\to$ Bucarest, costo $140 + 99 + 211 = 450$, con 4 espansioni. Il cammino ottimo costa $418$ (via Rimnicu Vilcea e Pitesti): greedy è veloce ma sceglie la strada che "sembra" più corta, senza guardare il costo già speso.

Proprietà:

• Completa: solo in spazi finiti e senza cicli (con la tabella dei raggiunti in spazi finiti sì; su alberi può girare in tondo).
• Tempo: $O(b^m)$ nel caso peggiore, ma una buona euristica lo migliora molto.
• Spazio: $O(b^m)$, tiene in memoria tutti i nodi.
• Non ottima.

A∗ search

Definizione. A∗ usa la funzione di valutazione $$f(n) = g(n) + h(n),$$ dove $g(n)$ è il costo finora speso per arrivare a $n$, $h(n)$ la stima del costo restante e $f(n)$ la stima del costo totale di un cammino che passa per $n$. Idea: evitare di espandere cammini già costosi.

Con $h = 0$ si ottiene il costo uniforme; con $f = h$ il greedy.

Esempio: da Arad a Bucarest con $h_{SLD}$. Ogni nodo è scritto come $g + h = f$; la frontiera è ordinata per $f$.

I costi $g$ vengono dai passi: Rimnicu Vilcea $140 + 80 = 220$, Fagaras $140 + 99 = 239$, Pitesti $220 + 97 = 317$, Bucarest via Fagaras $239 + 211 = 450$, via Pitesti $317 + 101 = 418$. Soluzione Arad $\to$ Sibiu $\to$ Rimnicu Vilcea $\to$ Pitesti $\to$ Bucarest, costo 418, ottima, con 6 espansioni (il costo uniforme ne fa 13, il greedy 4 ma sbaglia). Al passo 4 A∗ espande Fagaras perché $415 < 417$ e genera Bucarest con $f = 450$; non lo sceglie subito perché Pitesti ($417$) e poi Bucarest via Pitesti ($418$) hanno $f$ minore.

Il codice del laboratorio è la best_first_search della nota precedente con f = g + h:

def astar_search(problem, h=None):
    """Search nodes with minimum f(n) = g(n) + h(n)."""
    h = h or problem.h
    return best_first_search(problem, f=lambda n: g(n) + h(n))

Euristica ammissibile e consistente

Definizione. Un'euristica $h$ è ammissibile se $h(n) \ge 0$, $h(G) = 0$ per ogni obiettivo $G$ e non sovrastima mai il costo vero: $h(n) \le h^\ast(n)$, con $h^\ast(n)$ costo del cammino ottimo da $n$ all'obiettivo. È consistente (o monotona) se per ogni nodo $n$, ogni azione $a$ e successore $n'$ $$h(n) \le c(n, a, n') + h(n').$$

(È una disuguaglianza triangolare: stimare da $n$ non può costare più che fare un passo e poi stimare da $n'$.) Consistente $\Rightarrow$ ammissibile: lungo un cammino ottimo $n = n_0, n_1, \dots, n_k = G$, con i passi di costo $c_1, \dots, c_k$, si applica la consistenza a ogni passo e si somma: $$h(n_0) \le c_1 + h(n_1) \le c_1 + c_2 + h(n_2) \le \dots \le c_1 + \dots + c_k + h(G) = h^\ast(n),$$ perché $h(G) = 0$. Non vale il viceversa in generale.

La distanza in linea retta è ammissibile: nessuna strada è più corta della retta. È anche consistente: per esempio Arad $\to$ Sibiu: $h(\text{Arad}) = 366 \le 140 + 253 = 393 = c + h(\text{Sibiu})$; Sibiu $\to$ Rimnicu Vilcea: $253 \le 80 + 193 = 273$. Su tutte le 23 strade della mappa, nei due versi, la disuguaglianza è verificata con un programma.

Ottimalità di A∗

Teorema. Se $h$ è ammissibile, A∗ (versione ad albero) è ottima. Se $h$ è consistente, anche la versione su grafo con tabella dei raggiunti è ottima.

Dimostrazione (versione ad albero). Sia $G_s$ un obiettivo non ottimo già generato, e $n$ un nodo non espanso su un cammino ottimo verso l'obiettivo ottimo $G_o$. Allora $$\begin{aligned} f(G_s) &= g(G_s) && \text{perché } h(G_s) = 0\\ &> g(G_o) && \text{perché } G_s \text{ non è ottimo}\\ &= g(n) + h^\ast(n) && \text{(} h^\ast \text{ è il costo vero da } n \text{)}\\ &\ge g(n) + h(n) && \text{perché } h \text{ è ammissibile}\\ &= f(n). \end{aligned}$$ Quindi $f(G_s) > f(n)$: A∗ non seleziona mai $G_s$ finché esiste un nodo come $n$ sul cammino ottimo, dunque il primo obiettivo estratto è ottimo. $\square$

Con la consistenza, inoltre, $f$ non decresce mai lungo un cammino: $f(n') = g(n) + c + h(n') \ge g(n) + h(n) = f(n)$. A∗ espande quindi i nodi in ordine non decrescente di $f$ e, quando un nodo è espanso per la prima volta, ha già il costo $g$ minimo: la tabella dei raggiunti non perde soluzioni ottime. Le espansioni formano i contorni $f$: il contorno $i$ contiene i nodi con $f = f_i$, $f_i < f_{i+1}$. A differenza dei contorni dell'ampiezza (cerchi attorno alla partenza), quelli di A∗ si allungano verso l'obiettivo; più $h$ è accurata, più sono stretti.

Proprietà:

• Completa: sì, a meno di infiniti nodi con $f \le f(G)$.
• Tempo: $O(b^d)$ nel caso peggiore, ma dipende da quanto è buona $h$.
• Spazio: $O(b^d)$, tiene in memoria tutti i nodi.
• Ottima: sì, non si passa al contorno $f_{i+1}$ prima di aver finito $f_i$.

A∗ pesato

Un'euristica che sovrastima (non ammissibile) può far perdere la soluzione ottima, ma può espandere molti meno nodi. A∗ pesato (weighted A∗): $$f(n) = g(n) + W \cdot h(n), \qquad 1 < W < \infty.$$

È una generalizzazione di tutte le strategie viste:

Nelle slide, in un esempio di pianificazione di percorso, con $W = 2$ lo spazio di ricerca si riduce di un fattore 7 con un costo finale maggiore del 5%. Sul puzzle dell'8 dell'esempio sotto (soluzione ottima di 26 mosse), con $h_2$: $W = 1$ genera 6130 nodi; $W = 1{,}4$ (valore predefinito del laboratorio) trova ancora 26 mosse con 1202 nodi; $W = 2$ trova 30 mosse con 638 nodi, cioè circa 10 volte meno nodi con il 15% di cammino in più. Sulla Romania da Arad a Bucarest, già con $W = 1{,}4$ il cammino diventa quello del greedy (costo 450 invece di 418).

Qualità delle euristiche

Fattore di diramazione effettivo

Un modo di caratterizzare la qualità di un'euristica è il fattore di diramazione effettivo $b^\ast$ (effective branching factor). Se A∗ genera in totale $N$ nodi per un problema con soluzione a profondità $d$, $b^\ast$ è il fattore di diramazione di un albero uniforme di profondità $d$ con $N + 1$ nodi: $$N + 1 = 1 + b^\ast + (b^\ast)^2 + \dots + (b^\ast)^d .$$ Si misura sperimentalmente su un campione di problemi, e un'euristica ben progettata ha $b^\ast$ vicino a 1. L'equazione si risolve numericamente (non ha formula chiusa per $d$ grande).

Esempio. $N = 12$, $d = 2$: $13 = 1 + b^\ast + (b^\ast)^2$, cioè $(b^\ast)^2 + b^\ast - 12 = 0$, da cui $b^\ast = 3$. Con $N = 24$ e $d = 6$ la risoluzione numerica dà $b^\ast \approx 1{,}42$ (riga $d = 6$ della tabella delle slide, più sotto).

Il puzzle dell'8

Due euristiche per il puzzle dell'8:

• $h_1(n)$ = numero di tessere fuori posto;
• $h_2(n)$ = distanza di Manhattan totale: per ogni tessera, il numero di caselle (righe più colonne) che la separano dalla posizione finale.

Lo stato $S$ delle slide ha righe $7\,2\,4 \,/\, 5\,\_\,6 \,/\, 8\,3\,1$ e l'obiettivo è $\_\,1\,2 \,/\, 3\,4\,5 \,/\, 6\,7\,8$. Con (riga, colonna) da $(0,0)$ in alto a sinistra:

Tutte le 8 tessere sono fuori posto: $h_1(S) = 8$. E $$h_2(S) = 3 + 1 + 2 + 2 + 2 + 3 + 3 + 2 = 18.$$ Entrambe sono ammissibili: ogni mossa sposta una tessera di una sola casella, quindi servono almeno $h_2$ mosse (e almeno $h_1$).

Dati medi delle slide (100 puzzle per ogni lunghezza $d$ della soluzione):

Sullo stato $S$ (soluzione ottima di 26 mosse), con un programma che genera i nodi con la tabella dei raggiunti: ampiezza 177 809 nodi ($b^\ast \approx 1{,}53$), A∗($h_1$) 62 570 ($b^\ast \approx 1{,}46$), A∗($h_2$) 6 130 ($b^\ast \approx 1{,}33$).

Dominanza. Se $h_2(n) \ge h_1(n)$ per ogni $n$ (entrambe ammissibili), $h_2$ domina $h_1$ ed è migliore: A∗ con $h_2$ espande al più i nodi che espande con $h_1$. Perché A∗ espande ogni nodo con $f(n) < C^\ast$, cioè con $h(n) < C^\ast - g(n)$: con $h$ più grande la condizione è soddisfatta da meno nodi.

Qui $h_2 \ge h_1$ perché una tessera fuori posto dista almeno una casella. Un'euristica ammissibile si può ottenere dal costo esatto di un problema rilassato (con meno vincoli): $h_1$ è il costo esatto se ogni tessera può saltare dovunque in una mossa, $h_2$ se può muoversi di una casella anche su una casella occupata. Tra più euristiche ammissibili conviene il massimo (ammissibile e dominante su tutte).

Il pancake sorting del laboratorio e l'euristica del gap

Nel laboratorio 3 (extra), Esercizio - Route finding sulla Romania e pancake sorting con euristica del gap (laboratorio 3), si ordina una pila di frittelle con una spatola che inverte le prime $i$ frittelle (stato = tupla delle taglie dall'alto in basso). L'euristica del gap conta le coppie di frittelle vicine con taglie che differiscono per più di 1: sono coppie che andranno separate. $$h(s) = \bigl|\{\,i : |s_i - s_{i-1}| > 1\,\}\bigr| .$$ Per $(2, 1, 4, 6, 3, 5)$: coppie $(2,1)$ no, $(1,4)$ sì, $(4,6)$ sì, $(6,3)$ sì, $(3,5)$ sì: $h = 4$. A∗ trova una soluzione ottima di 5 inversioni. Ogni inversione cambia al più un'adiacenza, quindi $h$ non sovrastima; con una ricerca esaustiva (ampiezza all'indietro dall'obiettivo) risulta ammissibile e consistente per tutte le permutazioni con $n \le 7$.

Ricerca locale e problemi di ottimizzazione

In molti problemi il cammino è irrilevante: la soluzione è lo stato obiettivo stesso. Lo spazio degli stati è l'insieme delle configurazioni "complete" e si cerca la configurazione ottima (come nel TSP) o che soddisfa dei vincoli (un orario). Si usano algoritmi di miglioramento iterativo: si tiene un solo stato "corrente" e si prova a migliorarlo.

Gli algoritmi di ricerca locale partono da uno stato e passano a stati vicini, senza tenere traccia dei cammini né degli stati già raggiunti. Usano poca memoria, ma possono non esplorare mai la parte dello spazio in cui sta la soluzione. Esempi:

• TSP: si parte da un giro completo qualsiasi e si fanno scambi a coppie di lati; i metodi locali arrivano entro l'1% dall'ottimo molto in fretta anche con migliaia di città;
• $n$ regine: $n$ regine su una scacchiera $n \times n$ senza due sulla stessa riga, colonna o diagonale; si sposta una regina alla volta per ridurre i conflitti; si risolve quasi istantaneamente anche per $n$ molto grandi.

Paesaggio degli stati e hill climbing

Conviene pensare al paesaggio dello spazio degli stati (state space landscape): ogni stato ha un valore (da massimizzare), e ricerca locale significa salire sul paesaggio.

Definizione (hill climbing). L'ascesa del colle (hill climbing, anche greedy local search) parte da uno stato e passa sempre al vicino di valore più alto; si ferma quando nessun vicino è migliore e restituisce lo stato corrente, un massimo locale.

function Hill-Climbing(problem) returns a state that is a local maximum
    current <- Make-Node(Initial-State[problem])
    loop do
        neighbor <- a highest-valued successor of current
        if Value[neighbor] <= Value[current] then return State[current]
        current <- neighbor

Problemi: si ferma sui massimi locali (stati migliori di tutti i vicini ma non il migliore in assoluto) e sui plateau (zone piatte: se sono un massimo locale piatto la ricerca non sa dove andare, se sono una spalla si può uscire). Rimedi:

• mosse laterali casuali (sideways moves): permettono di uscire dalle spalle, ma possono girare all'infinito sui massimi piatti, quindi servono con un limite;
• hill climbing con riavvii casuali (random restart): si rilancia da stati iniziali casuali; è banalmente completo, perché prima o poi parte vicino alla soluzione.

Esempio: 8 regine. Stato = una regina per colonna (la riga di ciascuna), valore $-h$ con $h$ = numero di coppie di regine che si attaccano; vicini = muovere una regina dentro la sua colonna ($8 \times 7 = 56$ vicini). Lo stato della slide ha le regine nelle righe $(4, 5, 6, 3, 4, 5, 6, 5)$ (colonne da sinistra, righe dall'alto a partire da 0) e $h = 17$. La slide mostra $h$ per ognuno dei vicini: il minimo è $h = 12$, raggiunto da 8 mosse; l'ascesa ne sceglie una. Una configurazione come quella con le regine nelle righe $(7, 2, 6, 3, 1, 4, 0, 5)$ ha $h = 1$ (l'unica coppia che si attacca è quella cerchiata nella slide) ma tutti i suoi vicini hanno $h \ge 2$: è un minimo locale in cui la ricerca si blocca.

I numeri dell'esempio si verificano con questo codice:

import random, math

def h(q):                      # q[c] = riga della regina nella colonna c; coppie di regine che si attaccano
    return sum(q[i] == q[j] or abs(q[i] - q[j]) == j - i
               for i in range(8) for j in range(i + 1, 8))

def successori(q):             # muovere una regina dentro la sua colonna: 8 * 7 = 56 vicini
    return [q[:c] + [r] + q[c + 1:] for c in range(8) for r in range(8) if r != q[c]]

def hill_climbing(q):
    passi = 0
    while True:
        migliore = min(h(n) for n in successori(q))
        if migliore >= h(q):                      # nessun vicino migliore: minimo locale
            return q, passi
        q = random.choice([n for n in successori(q) if h(n) == migliore])
        passi += 1

q = [4, 5, 6, 3, 4, 5, 6, 5]                      # stato della slide
print(h(q), min(h(n) for n in successori(q)), sum(h(n) == 12 for n in successori(q)))   # 17 12 8

Da 2000 stati iniziali casuali (random.seed(0)) l'ascesa più ripida arriva a $h = 0$ nel 13,8% dei casi, in circa 4,1 passi; nel resto dei casi si blocca. Con i riavvii servono in media $1 / 0{,}138 \approx 7$ lanci, e lo spazio di $8^8 \approx 1{,}7 \cdot 10^7$ stati si risolve in un attimo.

Simulated annealing

Idea. Uscire dai massimi locali ammettendo qualche mossa "cattiva", con una dimensione e una frequenza che calano gradualmente. Come l'hill climbing, ma si sceglie un successore casuale e lo si accetta se migliora; se peggiora lo si accetta con una probabilità che decresce con il peggioramento $\lvert\Delta E\rvert$ e con una temperatura $T$ decrescente.

Con $\Delta E = \text{Value}[next] - \text{Value}[current]$, quindi $\Delta E < 0$ per una mossa peggiorativa, la probabilità di accettarla è $$p = e^{\Delta E / T} = e^{-\lvert\Delta E\rvert/T} \in (0, 1) .$$

(Nel pseudocodice delle slide compare $e^{-\Delta E/T}$ con $\Delta E$ = nuovo meno vecchio: per una mossa peggiorativa darebbe un valore maggiore di 1. Nella formula $p \propto e^{-\Delta E(x)/T}$ la $\Delta E(x)$ è invece il peggioramento preso positivo. Il segno corretto è quello scritto qui sopra.)

function Simulated-Annealing(problem, schedule) returns a solution state
    current <- Make-Node(Initial-State[problem])
    for t <- 1 to infinity do
        T <- schedule[t]
        if T = 0 then return current
        next <- a randomly selected successor of current
        DE <- Value[next] - Value[current]
        if DE > 0 then current <- next
        else current <- next only with probability e^(DE/T)

Come si comporta la probabilità $p = e^{-\lvert\Delta E\rvert/T}$:

(Per esempio $e^{-1/2} = 0{,}607$ e $e^{-3/0{,}5} = e^{-6} = 0{,}0025$.) A temperatura alta quasi ogni mossa è accettata (esplorazione, come una passeggiata casuale); a temperatura bassa solo i miglioramenti (come hill climbing). Se $T$ cala abbastanza lentamente, l'algoritmo raggiunge lo stato migliore con probabilità $\to 1$. È usato nel disegno di circuiti VLSI, nella pianificazione di voli, ecc.

def simulated_annealing(q, T=2.0, alpha=0.995, Tmin=1e-3):
    while T > Tmin:
        if h(q) == 0: return q
        c, r = random.randrange(8), random.randrange(8)
        n = q[:c] + [r] + q[c + 1:]
        dE = h(q) - h(n)                          # valore = -h: dE > 0 se n è migliore
        if dE > 0 or random.random() < math.exp(dE / T):
            q = n
        T *= alpha
    return q

Qui il piano di raffreddamento è $T_t = 2 \cdot 0{,}995^t$ (circa 1500 passi fino a $T < 10^{-3}$). Su 500 partenze casuali (random.seed(0)) trova una soluzione delle 8 regine nell'81,6% dei casi, contro il 13,8% dell'hill climbing senza riavvii.

Local beam search

Si parte da $k$ stati invece di uno e a ogni passo si tengono i $k$ migliori successori di tutti. Non equivale a $k$ riavvii indipendenti: ogni selezione influenza la successiva, e le ricerche che trovano stati buoni "reclutano" le altre. Problema: spesso tutti i $k$ stati finiscono sulla stessa collina. Rimedio: stochastic beam search, che sceglie i $k$ successori a caso con probabilità maggiore per i migliori (analogia con la selezione naturale).

Algoritmi genetici

Simili alla stochastic beam search, ma i successori si generano da coppie di stati. Ispirati alla selezione naturale: una popolazione di individui (stati) in cui i più adatti (fitness più alta) producono prole (stati successori) che popola la generazione successiva, con un processo detto ricombinazione. Gli stati devono essere codificati come stringhe. Tre passi:

• selezione: si scelgono i genitori con probabilità proporzionale alla fitness;
• ricombinazione (crossover): si sceglie a caso un punto di taglio, si spezzano le due stringhe genitori e si ricombinano le parti per formare due figli;
• mutazione: si cambia a caso qualche elemento dei figli, con una certa probabilità (tasso di mutazione).

Esempio: 8 regine. Individuo = stringa di 8 cifre (la riga di ogni colonna). Fitness $= 28 - h$ = coppie che non si attaccano ($28 = \binom{8}{2}$ è il massimo). Popolazione di 4: $(4,5,6,3,4,5,6,5)$ con fitness $11$; $(7,2,6,3,1,4,0,5)$ con $27$; $(0,2,4,6,1,3,5,7)$ con $27$; $(3,3,3,3,3,3,3,3)$ con $0$. Somma $65$: probabilità di selezione $0{,}169$, $0{,}415$, $0{,}415$, $0$. Crossover tra il secondo e il primo genitore al punto 3: $(7,2,6 \mid 3,1,4,0,5)$ e $(4,5,6 \mid 3,4,5,6,5)$ danno i figli $(7,2,6,3,4,5,6,5)$ con fitness $18$ e $(4,5,6,3,1,4,0,5)$ con fitness $20$.

Qui i figli non sono migliori del miglior genitore: l'algoritmo funziona perché, su molte generazioni, selezione e ricombinazione combinano blocchi buoni e la mutazione mantiene la diversità. Varianti: strategie evolutive, programmazione genetica.

Ricerca avversaria (oltre le slide)

Le slide del corso non trattano i giochi a due giocatori; si dà qui il minimo di base. In un gioco a somma zero con due giocatori che si alternano, MAX (che vuole il valore più alto) e MIN (il più basso), il valore minimax di un nodo è l'utilità del nodo se è terminale, il massimo dei valori dei figli se tocca a MAX, il minimo se tocca a MIN. La mossa di MAX è quella verso il figlio di valore massimo.

Esempio. Radice MAX con tre figli MIN di foglie $(4, 9, 6)$, $(7, 5, 8)$, $(3, 1, 10)$. I valori dei figli sono $\min = 4$, $5$, $1$; la radice vale $\max(4, 5, 1) = 5$: MAX gioca verso il secondo figlio.

Potatura alfa-beta: si tengono $\alpha$ (miglior valore garantito a MAX finora) e $\beta$ (il migliore per MIN) e si smette di esplorare un nodo quando non può cambiare la decisione. Nell'esempio: il primo figlio dà $4$, $\alpha = 4$; il secondo, con le foglie $7$, $5$, $8$, vale $5$, $\alpha = 5$; nel terzo la prima foglia è $3 \le \alpha = 5$, quindi il figlio vale al più $3$ e non può battere $5$: le foglie $1$ e $10$ non si valutano. Il risultato (radice $= 5$) è lo stesso con $7$ foglie valutate su $9$ (verificato con un programma).

Domande d'esame

1. Da Arad a Bucarest con $h_{SLD}$: quali città espande A∗ e in quale ordine? Che costo ha la soluzione? Arad (366), Sibiu (393), Rimnicu Vilcea (413), Fagaras (415), Pitesti (417), Bucarest (418). Soluzione Arad, Sibiu, Rimnicu Vilcea, Pitesti, Bucarest, costo 418.
2. Per lo stato $S$ del puzzle dell'8 delle slide calcolare $h_1$ e $h_2$. $h_1 = 8$, $h_2 = 3 + 1 + 2 + 2 + 2 + 3 + 3 + 2 = 18$.
3. A∗ genera $N = 12$ nodi per una soluzione a profondità $d = 2$: quanto vale $b^\ast$? $13 = 1 + b^\ast + (b^\ast)^2$, $b^\ast = 3$.
4. Perché un'euristica consistente è ammissibile? Vale il contrario? Si sommano le disuguaglianze $h(n_i) \le c_{i+1} + h(n_{i+1})$ lungo il cammino ottimo fino all'obiettivo, dove $h = 0$: $h(n) \le h^\ast(n)$. Il contrario non vale in generale.
5. Quale valore di $W$ rende A∗ pesato uguale al greedy? E al costo uniforme? $W \to \infty$ (cioè $f = h$); $W = 0$ (cioè $f = g$).
6. Probabilità di accettare con il simulated annealing una mossa con $\Delta E = -2$ a $T = 1$ e a $T = 4$. $e^{-2} \approx 0{,}135$ e $e^{-1/2} \approx 0{,}607$.
7. Perché l'hill climbing può non trovare una soluzione e come si rimedia? Si blocca su massimi locali e plateau; si rimedia con riavvii casuali, mosse laterali o simulated annealing.