Esercizio - Euristiche ammissibili (esempio d'esame 2)

Teoria: Ricerca informata - greedy best-first, A* ed euristicheLa ricerca informata usa una funzione euristica h(n) che stima il costo da n all'obiettivo. Greedy best-first espande il nodo con h minima (f = h): veloce ma non ottima né in generale completa. A∗ usa f = g + h e, con h ammissibile (mai sopra il costo vero) e, sul grafo con tabella dei raggiunti, consistente, è completa e ottima; il fattore di diramazione effettivo b∗ misura la qualità di h, e un'euristica che ne domina un'altra espande meno nodi. A∗ pesato (f = g + W h) rinuncia all'ottimalità per espandere meno nodi. Per i problemi in cui conta solo lo stato finale esiste la ricerca locale (hill climbing, simulated annealing, beam search, algoritmi genetici). In appendice, cenni di ricerca avversaria (minimax e potatura alfa-beta).Ricerca informata - greedy best-first, A* ed euristiche → (sezione sull'euristica ammissibile e consistente). Esercizio collegato: Esercizio - Euristiche dell'8-puzzle e fattore di diramazione effettivo (slide del corso). Domanda 7 del quiz da 9 CFU e domanda 5 di quello da 6 CFU: testo identico.

Testo (risposta aperta). Nell'ambito degli algoritmi di ricerca, si spieghi che cosa vuol dire che un'euristica è ammissibile (admissible heuristic), aiutandosi con uno o più esempi.

Risposta modello

Una funzione euristica $h(n)$ stima il costo del cammino più economico da un nodo $n$ a un obiettivo. È ammissibile se non sovrastima mai il costo reale: per ogni nodo $n$, $$0\le h(n)\le h^\ast(n),$$ dove $h^\ast(n)$ è il costo del cammino ottimo da $n$ all'obiettivo (e $h(G)=0$ se $G$ è un obiettivo). È un'euristica ottimista: dice che manca al massimo quanto manca davvero.

Perché serve. L'algoritmo A∗ espande il nodo con il minimo $f(n)=g(n)+h(n)$. Se $h$ è ammissibile, A∗ (nella versione ad albero) restituisce una soluzione ottima. Idea della prova: quando A∗ estrae un obiettivo con costo $C$, ogni nodo $n$ sulla frontiera lungo un cammino ottimo ha $f(n)=g(n)+h(n)\le g(n)+h^\ast(n)=C^\ast$, e per la scelta del minimo $C\le f(n)\le C^\ast$, quindi $C=C^\ast$. Per la versione su grafo con tabella dei nodi raggiunti serve una proprietà più forte, la consistenza: $h(n)\le c(n,a,n')+h(n')$, che implica l'ammissibilità.

Esempi di euristiche ammissibili.

• Mappa della Romania: la distanza in linea retta fino a Bucarest è ammissibile, perché nessuna strada è più corta della retta. Da Arad $h=366$, mentre il cammino ottimo Arad, Sibiu, Rimnicu Vilcea, Pitesti, Bucarest costa $140+80+97+101=418$: $366\le418$.
• 8-puzzle: $h_1$ = numero di tessere fuori posto e $h_2$ = somma delle distanze di Manhattan delle tessere dalla loro posizione finale. Ogni mossa sposta una tessera di una casella, quindi servono almeno $h_1$ e almeno $h_2$ mosse: entrambe ammissibili, con $h_2\ge h_1$ ($h_2$ domina $h_1$ ed espande meno nodi). Si ottengono dal costo esatto di un problema rilassato (con meno vincoli).

Controesempio: euristica non ammissibile. Grafo con $S\to A$ (costo 1), $A\to G$ (1), $S\to B$ (1), $B\to G$ (3): il cammino ottimo è $S,A,G$ con costo $2$. Se $h(A)=10$ (il costo reale da $A$ è $1$: sovrastima), $h(B)=3$, $h(S)=0$: dopo aver espanso $S$ si ha $f(A)=1+10=11$ e $f(B)=1+3=4$; A∗ espande $B$ e arriva a $G$ con $f=4$, restituendo il cammino $S,B,G$ di costo $4$, non ottimo. Con $h(A)=1$ (ammissibile) $f(A)=2$ e trova $S,A,G$ di costo $2$ (verificato con un programma).

Compromesso. Un'euristica che sovrastima può espandere meno nodi (come A∗ pesato) ma perde l'ottimalità; un'euristica ammissibile ma debole (per esempio $h=0$, che dà Dijkstra) garantisce l'ottimo ma espande molti nodi.

Errori tipici nella risposta: dire "stima esattamente" (è un limite inferiore); confondere ammissibile con consistente; non dare un esempio o dare un'euristica che sovrastima (per esempio il doppio della distanza in linea retta).