Esercizio - Ricerca di costo uniforme, greedy e A∗ sulla mappa della Romania (slide del corso)

Esercizio ricavato dalle slide del corso di Intelligenza Artificiale, Ing. dell'Informazione UniPD, sulla mappa della Romania: tre esecuzioni di algoritmi a mano (costo uniforme da Sibiu a Bucarest, greedy e A∗ da Arad a Bucarest), più un caso aggiuntivo (da Lugoj a Bucarest) per vedere quando il greedy sbaglia e quando no. Teoria in 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 → e 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 →. Ogni esecuzione è verificata con il programma in fondo.

Testo

Sulla mappa della Romania (costi in chilometri) con la distanza in linea retta da Bucarest $h_{SLD}$ come euristica:

1. Con la ricerca a costo uniforme, trovare il cammino da Sibiu a Bucarest: ordine di espansione, frontiera a ogni passo, costo.
2. Con la ricerca greedy best-first ($f = h$), trovare il cammino da Arad a Bucarest. È ottimo?
3. Con A∗ ($f = g + h$), trovare il cammino da Arad a Bucarest. Quante espansioni servono? È ottimo?
4. Ripetere con A∗, greedy e costo uniforme da Lugoj a Bucarest.
5. Verificare che $h_{SLD}$ è ammissibile e consistente sulle strade della mappa.

Strade (km): Oradea–Zerind 71, Oradea–Sibiu 151, Arad–Zerind 75, Arad–Sibiu 140, Arad–Timisoara 118, Lugoj–Timisoara 111, Lugoj–Mehadia 70, Mehadia–Drobeta 75, Drobeta–Craiova 120, Craiova–Rimnicu Vilcea 146, Craiova–Pitesti 138, Rimnicu Vilcea–Sibiu 80, Fagaras–Sibiu 99, Fagaras–Bucarest 211, Pitesti–Bucarest 101, Pitesti–Rimnicu Vilcea 97, Bucarest–Giurgiu 90, Bucarest–Urziceni 85, Urziceni–Hirsova 98, Hirsova–Eforie 86, Urziceni–Vaslui 142, Vaslui–Iasi 92, Iasi–Neamt 87.

$h_{SLD}$ (km): Arad 366, Bucarest 0, Craiova 160, Drobeta 242, Eforie 161, Fagaras 176, Giurgiu 77, Hirsova 151, Iasi 226, Lugoj 244, Mehadia 241, Neamt 234, Oradea 380, Pitesti 100, Rimnicu Vilcea 193, Sibiu 253, Timisoara 329, Urziceni 80, Vaslui 199, Zerind 374.

Punto 1 - costo uniforme da Sibiu a Bucarest

Regola. Si estrae sempre il nodo di costo $g$ minimo; il test dell'obiettivo si fa all'estrazione. Se uno stato si raggiunge con un costo minore, il nuovo nodo prende il posto del vecchio (la voce vecchia, più costosa, non serve più).

Cammino: Sibiu $\to$ Rimnicu Vilcea $\to$ Pitesti $\to$ Bucarest, costo $80 + 97 + 101 = 278$, dopo 10 espansioni. La slide del corso racconta la stessa storia in sei passi: non cita Arad e Oradea (successori di Sibiu "all'indietro"), che però costano 140 e 151, meno di Pitesti (177), e quindi vengono espansi prima di Pitesti, senza cambiare il risultato. Si noti il punto 3: Bucarest compare per la prima volta con 310 ma non viene estratta, perché nella frontiera ci sono nodi più economici; il 278 si scopre solo espandendo Pitesti.

Punto 2 - greedy da Arad a Bucarest

Si estrae il nodo con $h$ minima, senza guardare $g$.

Cammino Arad $\to$ Sibiu $\to$ Fagaras $\to$ Bucarest, costo $140 + 99 + 211 = 450$, con 4 espansioni. Non è ottimo: il cammino ottimo (punto 3) costa 418. A Sibiu il greedy sceglie Fagaras ($h = 176$, che "sembra" più vicina) invece di Rimnicu Vilcea ($h = 193$), ma la strada da Fagaras a Bucarest è lunga 211 contro $97 + 101 = 198$ da Rimnicu Vilcea via Pitesti, e $80 + 97 + 101 = 278$ contro $99 + 211 = 310$ da Sibiu.

Punto 3 - A∗ da Arad a Bucarest

I costi $g$: Sibiu $140$; Rimnicu Vilcea $140 + 80 = 220$; Fagaras $140 + 99 = 239$; Pitesti $220 + 97 = 317$; Bucarest via Pitesti $317 + 101 = 418$. Cammino Arad $\to$ Sibiu $\to$ Rimnicu Vilcea $\to$ Pitesti $\to$ Bucarest, costo 418, ottimo, con 6 espansioni (l'ordine $f$ non decrescente è $366, 393, 413, 415, 417, 418$). Al passo 4 A∗ espande Fagaras perché $415 < 417$: è una deviazione che si rivela inutile ma costa poco. Il costo uniforme da Arad a Bucarest ne farebbe 13.

Punto 4 - da Lugoj a Bucarest

A∗ ($f = g + h$):

Cammino Lugoj $\to$ Mehadia $\to$ Drobeta $\to$ Craiova $\to$ Pitesti $\to$ Bucarest, costo $70 + 75 + 120 + 138 + 101 = 504$, 7 espansioni (la deviazione per Timisoara al passo 5 serve a escludere un percorso migliore: $f = 440 < 503$). Il greedy trova lo stesso cammino (504) con 6 espansioni: da Lugoj la strada "che sembra giusta" è davvero quella ottima, perché da Lugoj non c'è una scorciatoia ingannevole. Il costo uniforme trova ancora 504 ma con 13 espansioni (Lugoj, Mehadia, Timisoara, Drobeta, Arad, Craiova, Zerind, Sibiu, Oradea, Pitesti, Rimnicu Vilcea, Fagaras, Bucarest).

Morale: il greedy non è sempre sbagliato, è solo senza garanzie; A∗ dà sempre l'ottimo (con $h$ ammissibile e consistente) con molte meno espansioni del costo uniforme (6 contro 13 da Arad, 7 contro 13 da Lugoj).

Punto 5 - $h_{SLD}$ è ammissibile e consistente

Ammissibile: $h_{SLD}(n) \le h^\ast(n)$, perché la distanza in linea retta non supera mai il percorso stradale. Per Arad: $366 \le 418$; Sibiu $253 \le 278$; Rimnicu Vilcea $193 \le 198$; Fagaras $176 \le 211$; Pitesti $100 \le 101$. Consistente: $h(n) \le c(n, n') + h(n')$ in entrambi i versi di ogni strada, per esempio Arad–Sibiu: $366 \le 140 + 253 = 393$ e $253 \le 140 + 366$; Pitesti–Bucarest: $100 \le 101 + 0$ e $0 \le 101 + 100$. Il programma sotto controlla tutte le 23 strade.

Programma di verifica

import heapq, itertools

strade = {('Oradea', 'Zerind'): 71, ('Oradea', 'Sibiu'): 151, ('Arad', 'Zerind'): 75, ('Arad', 'Sibiu'): 140,
          ('Arad', 'Timisoara'): 118, ('Lugoj', 'Timisoara'): 111, ('Lugoj', 'Mehadia'): 70, ('Drobeta', 'Mehadia'): 75,
          ('Craiova', 'Drobeta'): 120, ('Craiova', 'Rimnicu Vilcea'): 146, ('Craiova', 'Pitesti'): 138,
          ('Rimnicu Vilcea', 'Sibiu'): 80, ('Fagaras', 'Sibiu'): 99, ('Bucharest', 'Fagaras'): 211,
          ('Bucharest', 'Pitesti'): 101, ('Bucharest', 'Giurgiu'): 90, ('Bucharest', 'Urziceni'): 85,
          ('Hirsova', 'Urziceni'): 98, ('Eforie', 'Hirsova'): 86, ('Urziceni', 'Vaslui'): 142,
          ('Iasi', 'Vaslui'): 92, ('Iasi', 'Neamt'): 87, ('Pitesti', 'Rimnicu Vilcea'): 97}
vicini = {}
for (a, b), c in strade.items():
    vicini.setdefault(a, {})[b] = c
    vicini.setdefault(b, {})[a] = c

h = {'Arad': 366, 'Bucharest': 0, 'Craiova': 160, 'Drobeta': 242, 'Eforie': 161, 'Fagaras': 176, 'Giurgiu': 77,
     'Hirsova': 151, 'Iasi': 226, 'Lugoj': 244, 'Mehadia': 241, 'Neamt': 234, 'Oradea': 380, 'Pitesti': 100,
     'Rimnicu Vilcea': 193, 'Sibiu': 253, 'Timisoara': 329, 'Urziceni': 80, 'Vaslui': 199, 'Zerind': 374}

def best_first(start, goal, f):
    "f(stato, g) -> priorità. Restituisce cammino, costo e ordine di espansione."
    conta = itertools.count()                       # per rompere i pareggi in ordine di inserimento
    frontiera = [(f(start, 0), next(conta), start, 0, [start])]
    raggiunti = {start: 0}                          # stato -> miglior g trovato
    espansi = []
    while frontiera:
        _, _, s, g, cammino = heapq.heappop(frontiera)
        if g > raggiunti[s]:                        # voce vecchia: c'è un cammino migliore
            continue
        espansi.append(s)
        if s == goal:
            return cammino, g, espansi
        for t, costo in sorted(vicini[s].items()):
            g2 = g + costo
            if t not in raggiunti or g2 < raggiunti[t]:
                raggiunti[t] = g2
                heapq.heappush(frontiera, (f(t, g2), next(conta), t, g2, cammino + [t]))

print(best_first('Sibiu', 'Bucharest', lambda s, g: g))          # costo uniforme
print(best_first('Arad', 'Bucharest', lambda s, g: h[s]))        # greedy
print(best_first('Arad', 'Bucharest', lambda s, g: g + h[s]))    # A*
print(all(h[a] <= c + h[b] and h[b] <= c + h[a] for (a, b), c in strade.items()))   # consistenza

Output (cammino, costo, città espanse in ordine):

(['Sibiu', 'Rimnicu Vilcea', 'Pitesti', 'Bucharest'], 278, ['Sibiu', 'Rimnicu Vilcea', 'Fagaras', 'Arad', 'Oradea', 'Pitesti', 'Zerind', 'Craiova', 'Timisoara', 'Bucharest'])
(['Arad', 'Sibiu', 'Fagaras', 'Bucharest'], 450, ['Arad', 'Sibiu', 'Fagaras', 'Bucharest'])
(['Arad', 'Sibiu', 'Rimnicu Vilcea', 'Pitesti', 'Bucharest'], 418, ['Arad', 'Sibiu', 'Rimnicu Vilcea', 'Fagaras', 'Pitesti', 'Bucharest'])
True

I pareggi si rompono in ordine di inserimento e i vicini sono scorsi in ordine alfabetico, ma qui nessun pareggio cambia le espansioni mostrate. Il codice scarta le voci vecchie nello heap (if g > raggiunti[s]), cosa che il codice del laboratorio non fa (Esercizio - Algoritmi di ricerca in Python con Problem, Node e best-first search (laboratorio 3)).