Esercizio - Route finding sulla Romania e pancake sorting con euristica del gap (laboratorio 3)

Esercizi extra del laboratorio 3 del corso di Intelligenza Artificiale, Ing. dell'Informazione UniPD: due domini di prova per gli algoritmi di ricerca di Esercizio - Algoritmi di ricerca in Python con Problem, Node e best-first search (laboratorio 3), cioè la ricerca di percorsi su una mappa (route finding) e l'ordinamento di una pila di frittelle (pancake sorting) con l'euristica del gap. Teoria: 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 →. Il codice presuppone le classi Problem, Node e gli algoritmi dell'esercizio precedente.

Parte 1 - Route finding

Testo (traduzione). In un RouteProblem gli stati sono nomi di "città" (o altri luoghi), come 'A' per Arad. Anche le azioni sono nomi di città: 'Z' è l'azione che porta alla città 'Z'. La disposizione delle città è data da una struttura dati a parte, una Map, cioè un grafo con vertici (città), collegamenti tra vertici, distanze (costi) di quei collegamenti (se non sono specificate, il valore predefinito è 1 per ogni collegamento) e, facoltativamente, la posizione 2D $(x, y)$ di ogni città. Un RouteProblem prende questa Map in ingresso e permette azioni che si spostano tra città collegate. L'euristica predefinita è la distanza in linea retta dall'obiettivo, o è uniformemente zero se le posizioni non sono date.

La classe Map

Il grafo si passa come links, un dizionario {(v1, v2): distanza} oppure un elenco di coppie [(v1, v2), ...] (allora ogni distanza è 1: hasattr(links, 'items') controlla se l'oggetto è un dizionario). Se il grafo non è orientato (predefinito), per ogni collegamento $(v_1, v_2)$ si aggiunge anche $(v_2, v_1)$. I vicini sono memorizzati in una multimappa, un dizionario vertice -> lista di vicini; se mancano le posizioni, ogni città ha la posizione $(0, 0)$ (defaultdict).

def multimap(pairs) -> dict:
    "Date coppie (chiave, valore), costruisce {chiave: [valore, ...]}."
    result = defaultdict(list)
    for key, val in pairs:
        result[key].append(val)
    return result

class Map:
    def __init__(self, links, locations=None, directed=False):
        if not hasattr(links, 'items'):          # distanze 1 per default
            links = {link: 1 for link in links}
        if not directed:
            for (v1, v2) in list(links):
                links[v2, v1] = links[v1, v2]
        self.distances = links
        self.neighbors = multimap(links)
        self.locations = locations or defaultdict(lambda: (0, 0))

multimap applicata ai collegamenti della Romania dà, per esempio, 'A': ['Z', 'S', 'T'], 'O': ['Z', 'S'], 'B': ['F', 'P', 'G', 'U'] (l'ordine dei vicini segue l'ordine del dizionario e cambia l'ordine di espansione a parità di punteggio).

RouteProblem e distanza in linea retta

class RouteProblem(Problem):
    def actions(self, state):
        "Le località vicine a state."
        return self.map.neighbors[state]

    def result(self, state, action):
        "Va nella località action, se la mappa lo permette."
        return action if action in self.map.neighbors[state] else state

    def action_cost(self, s, action, s1):
        "La distanza per andare da s a s1."
        return self.map.distances[s, s1]

    def h(self, node):
        "Distanza in linea retta tra lo stato e l'obiettivo."
        locs = self.map.locations
        return straight_line_distance(locs[node.state], locs[self.goal])

def straight_line_distance(A, B):
    return sum(abs(a - b)**2 for (a, b) in zip(A, B)) ** 0.5

zip(A, B) accoppia le coordinate corrispondenti (le tuple (x1, y1) e (x2, y2) danno le coppie $(x_1, x_2)$ e $(y_1, y_2)$); la somma dei quadrati delle differenze, elevata a $1/2$, è la distanza euclidea $\sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2}$. Per Arad $(76, 497)$ e Bucarest $(400, 327)$: $\sqrt{324^2 + 170^2} = \sqrt{133\,876} \approx 365{,}9$, cioè i $366$ km della tabella delle slide: le coordinate sono in scala con i chilometri.

I problemi di prova

romania = Map(
    {('O', 'Z'):  71, ('O', 'S'): 151, ('A', 'Z'): 75, ('A', 'S'): 140, ('A', 'T'): 118,
     ('L', 'T'): 111, ('L', 'M'):  70, ('D', 'M'):  75, ('C', 'D'): 120, ('C', 'R'): 146,
     ('C', 'P'): 138, ('R', 'S'):  80, ('F', 'S'):  99, ('B', 'F'): 211, ('B', 'P'): 101,
     ('B', 'G'):  90, ('B', 'U'):  85, ('H', 'U'):  98, ('E', 'H'):  86, ('U', 'V'): 142,
     ('I', 'V'):  92, ('I', 'N'):  87, ('P', 'R'):  97},
    {'A': ( 76, 497), 'B': (400, 327), 'C': (246, 285), 'D': (160, 296), 'E': (558, 294),
     'F': (285, 460), 'G': (368, 257), 'H': (548, 355), 'I': (488, 535), 'L': (162, 379),
     'M': (160, 343), 'N': (407, 561), 'O': (117, 580), 'P': (311, 372), 'R': (227, 412),
     'S': (187, 463), 'T': ( 83, 414), 'U': (471, 363), 'V': (535, 473), 'Z': ( 92, 539)})

r0 = RouteProblem('A', 'A', map=romania)   # partenza = arrivo
r1 = RouteProblem('A', 'B', map=romania)   # Arad -> Bucarest
r2 = RouteProblem('N', 'L', map=romania)   # Neamt -> Lugoj
r3 = RouteProblem('E', 'T', map=romania)   # Eforie -> Timisoara
r4 = RouteProblem('O', 'M', map=romania)   # Oradea -> Mehadia

I collegamenti sono quelli della mappa della teoria. Il problema r0 è banale: il test dell'obiettivo sullo stato iniziale riesce subito, quindi nessun nodo è generato. I percorsi trovati, con costo (tutti i cammini sono stati verificati con il codice del corso):

Si vedono i comportamenti attesi: A∗ e il costo uniforme danno sempre l'ottimo (A∗ con meno espansioni: per r1, 6 contro 13); il greedy dà cammini più lunghi, anche molto (1207 contro 910 per r2); l'ampiezza minimizza i passi, non il costo (1085 contro 910 in r2; in r4 capita che coincida con l'ottimo).

Parte 2 - Pancake sorting

Testo (traduzione). Data una pila di frittelle di taglie diverse, si possono ordinare in una pila di taglie decrescenti, con la più grande in basso e la più piccola in alto? Si ha una spatola con cui si possono capovolgere le prime $i$ frittelle della pila (per $i = 3$, la spatola afferra le prime tre frittelle e le capovolge). Quante inversioni servono per ordinare tutta la pila? (È un problema di ordinamento; fonte: Jones e Pevzner, An Introduction to Bioinformatics Algorithms.)

Rappresentazione. Le frittelle sono classificate per taglia: la più piccola è 1, la seconda 2, e così via. Uno stato è la tupla delle taglie, dalla frittella in alto a quella in basso; l'obiettivo è sempre (1, 2, ..., n); lo stato iniziale della figura è (2, 1, 4, 6, 3, 5). Un'azione è l'indice $i$ delle frittelle da capovolgere ($i = 2, \dots, n$: con $i = 1$ non cambia niente). Capovolgere le prime $i$ significa rovesciare il prefisso e lasciare il resto: state[:i][::-1] + state[i:]. Con $i = 3$ su (2, 1, 4, 6, 3, 5): state[:3] = (2, 1, 4), rovesciata (4, 1, 2), resto (6, 3, 5), risultato (4, 1, 2, 6, 3, 5). Si usano tuple (immutabili e hashable) perché gli stati servono come chiavi della tabella reached.

Euristica del gap. Se due frittelle vicine hanno taglie consecutive (la seconda più piccola vicina alla terza), è bene: devono restare vicine. Se la seconda più piccola è vicina alla quarta, è male: servirà almeno una mossa per separarle e infilare la terza in mezzo. L'euristica del gap conta il numero di vicini con un gap di questo tipo, cioè con taglie che differiscono per più di 1.

class PancakeProblem(Problem):
    """Obiettivo sempre tuple(range(1, n+1)); lo stato iniziale è una permutazione.
    Un'azione è l'indice i delle prime i frittelle da capovolgere."""

    def __init__(self, initial):
        self.initial, self.goal = tuple(initial), tuple(sorted(initial))

    def actions(self, state): return range(2, len(state) + 1)

    def result(self, state, i): return state[:i][::-1] + state[i:]

    def h(self, node):
        "L'euristica del gap."
        s = node.state
        return sum(abs(s[i] - s[i - 1]) > 1 for i in range(1, len(s)))

c0 = PancakeProblem((2, 1, 4, 6, 3, 5))
c1 = PancakeProblem((4, 6, 2, 5, 1, 3))
c2 = PancakeProblem((1, 3, 7, 5, 2, 6, 4))
c3 = PancakeProblem((1, 7, 2, 6, 3, 5, 4))
c4 = PancakeProblem((1, 3, 5, 7, 9, 2, 4, 6, 8))

La somma di booleani conta i True (True vale 1). Nelle slide il calcolo per (2, 1, 4, 6, 3, 5) è passo passo: coppia $(2, 1)$ differenza $1$, no; $(1, 4)$ differenza $3$, sì ($+1$); $(4, 6)$ differenza $2$, sì ($+2$); $(6, 3)$ differenza $3$, sì ($+3$); $(3, 5)$ differenza $2$, sì ($+4$). Dunque $h = 4$.

Soluzione di c0 con A∗.

path_states(astar_search(c0))

[(2, 1, 4, 6, 3, 5),
 (6, 4, 1, 2, 3, 5),
 (5, 3, 2, 1, 4, 6),
 (4, 1, 2, 3, 5, 6),
 (3, 2, 1, 4, 5, 6),
 (1, 2, 3, 4, 5, 6)]

Le azioni sono capovolgere le prime $4, 6, 5, 4, 3$ frittelle: 5 inversioni. Si controlla a mano il primo passo, $i = 4$: (2, 1, 4, 6) rovesciata dà (6, 4, 1, 2), resto (3, 5): (6, 4, 1, 2, 3, 5). I valori di $h$ lungo il cammino sono $4, 3, 3, 2, 1, 0$: per ogni passo $h$ scende al più di 1 (ogni inversione crea o rimuove al più un'adiacenza problematica), perciò con costo 1 per passo l'euristica è consistente.

Soluzioni ottime trovate da A∗ per gli altri stati: c1 7 inversioni, c2 8, c3 6, c4 9.

L'euristica del gap è ammissibile e consistente. Ogni inversione di un prefisso cambia al più una coppia di vicini (quella al bordo del prefisso; dentro il prefisso le coppie restano coppie, solo in ordine inverso), quindi $h$ cala al più di 1 per passo e vale 0 solo sull'obiettivo: $h(s) \le 1 + h(s')$ e di conseguenza $h(s) \le h^\ast(s)$. Verifica sperimentale: con una ricerca in ampiezza all'indietro dall'obiettivo (le inversioni sono reversibili) si calcolano le distanze vere di tutte le permutazioni; per $n = 4, 5, 6, 7$ la disuguaglianza $h \le h^\ast$ (ammissibilità) e $h(s) \le 1 + h(s')$ per ogni vicino (consistenza) valgono sempre. La distanza massima è 4, 5, 7, 8 inversioni per $n = 4, 5, 6, 7$.

Nota. L'euristica del corso non conta il bordo con il piatto sotto la pila: la versione completa aggiunge 1 se la frittella in fondo non è la più grande. Resta ammissibile e più accurata (per $n = 6$ coincide con la distanza vera in circa il 62% degli stati, per $n = 5$ nel 67%).

Confronto degli algoritmi sui dieci problemi

Con la funzione report (Esercizio - Confronto degli algoritmi di ricerca con CountCalls, report e grafici (laboratorio 3)) si contano i nodi generati. Per i problemi delle frittelle (c0–c4), dalle esecuzioni del corso:

(nodi generati per problema). Greedy genera pochissimi nodi ma non è ottimo (9 inversioni contro 8 per c2; 11 contro 9 per c4); A∗ è ottimo con una frazione dei nodi del costo uniforme (per c4, 2256 contro più di 2,2 milioni). L'euristica del gap è una buona euristica: il fattore di diramazione effettivo scende di molto (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 →).