Ricerca nello spazio degli stati - formulazione dei problemi e ricerca non informata

Un agente basato su obiettivi (Agenti intelligenti - ambienti, PEAS e tipi di agenteUn agente è una funzione dalle sequenze di percezioni alle azioni; è razionale se per ogni sequenza sceglie l'azione che massimizza il valore atteso della misura di prestazione, date le percezioni e la conoscenza incorporata. L'ambiente di lavoro si descrive con PEAS (Performance, Environment, Actuators, Sensors) e si classifica con sette coppie di proprietà (osservabile, deterministico, episodico, statico, discreto, singolo/multi-agente, noto). Le architetture crescono in complessità: reattivo semplice, reattivo basato su modello, basato su obiettivi, basato su utilità, più l'agente che apprende (elemento esecutivo, di apprendimento, critico, generatore di problemi).Agenti intelligenti - ambienti, PEAS e tipi di agente →) deve trovare da solo la sequenza di azioni che porta all'obiettivo. Questa nota mostra come si formula un problema e come lo si risolve cercando nello spazio degli stati con algoritmi che conoscono solo la definizione del problema (ricerca non informata). Gli algoritmi che usano una stima della distanza dall'obiettivo sono in 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 →. Fonte: slide del corso di Intelligenza Artificiale, Ing. dell'Informazione UniPD, con le implementazioni Python del laboratorio 3.

Agente risolutore di problemi

Un agente risolutore di problemi (problem-solving agent) è un caso particolare di agente basato su obiettivi che pianifica in anticipo: considera sequenze di azioni che portano a un obiettivo. Usa una rappresentazione atomica: uno stato è una scatola nera che cattura tutta l'informazione necessaria, senza strutture interne da esaminare. Le soluzioni si cercano tra sequenze stato $\to$ azione, spesso su grafi.

Esempio: la Romania. Si è in vacanza in Romania, ad Arad; il volo parte domani da Bucarest. Il ciclo è: (1) formulare l'obiettivo: essere a Bucarest; (2) formulare il problema: stati = le città, azioni = guidare tra città; (3) cercare una soluzione: una sequenza di città, per esempio Arad $\to$ Sibiu $\to$ Fagaras $\to$ Bucarest; (4) eseguire la sequenza di azioni.

La fase 3 è offline: si simula l'esplorazione senza muoversi, e si esegue il piano solo dopo averlo trovato (in un ambiente deterministico, osservabile e noto, Agenti intelligenti - ambienti, PEAS e tipi di agenteUn agente è una funzione dalle sequenze di percezioni alle azioni; è razionale se per ogni sequenza sceglie l'azione che massimizza il valore atteso della misura di prestazione, date le percezioni e la conoscenza incorporata. L'ambiente di lavoro si descrive con PEAS (Performance, Environment, Actuators, Sensors) e si classifica con sette coppie di proprietà (osservabile, deterministico, episodico, statico, discreto, singolo/multi-agente, noto). Le architetture crescono in complessità: reattivo semplice, reattivo basato su modello, basato su obiettivi, basato su utilità, più l'agente che apprende (elemento esecutivo, di apprendimento, critico, generatore di problemi).Agenti intelligenti - ambienti, PEAS e tipi di agente →).

La mappa del laboratorio (posizioni dalle coordinate del notebook, distanze in chilometri) è questa, con in evidenza il cammino ottimo da Arad ($A$) a Bucarest ($B$):

Le lettere sono le iniziali usate nel codice: A Arad, B Bucarest, C Craiova, D Drobeta, E Eforie, F Fagaras, G Giurgiu, H Hirsova, I Iasi, L Lugoj, M Mehadia, N Neamt, O Oradea, P Pitesti, R Rimnicu Vilcea, S Sibiu, T Timisoara, U Urziceni, V Vaslui, Z Zerind.

Formulazione di un problema

Definizione. Un problema è definito da:

• l'insieme degli stati possibili (lo spazio degli stati, un grafo);
• lo stato iniziale (per esempio "in Arad");
• uno o più stati obiettivo, descritti in modo esplicito ("in Bucarest") o implicito (NoDirt(x), nessuna sporcizia), con un test dell'obiettivo is_goal(s);
• le azioni: Actions(s) è l'insieme delle azioni applicabili in $s$ (Actions(Arad) = {verso Timisoara, verso Zerind, verso Sibiu});
• il modello di transizione: Result(s, a) è lo stato raggiunto applicando $a$ in $s$ (Result(Arad, verso Zerind) = Zerind);
• la funzione di costo delle azioni $c(s, a, s')$, supposta $\ge 0$, e il costo del cammino come somma dei costi dei passi (somma di distanze, numero di azioni eseguite, ecc.).

Una soluzione è una sequenza di azioni che porta dallo stato iniziale a uno stato obiettivo; una soluzione ottima è quella di costo minimo.

La scelta di che cosa mettere nello stato è una astrazione del mondo reale: si tiene solo ciò che serve al problema (nella Romania non conta il meteo).

Esempi di formulazione

Mondo dell'aspirapolvere. Stati: posizione del robot e sporcizia (trascurando la quantità). Quanti? $2$ posizioni $\times\ 2^2$ configurazioni di sporco $= 8$. Qualunque stato può essere iniziale. Azioni: Left, Right, Suck, NoOp. Modello di transizione: quello descritto dal grafo delle 8 configurazioni. Obiettivo: nessuna sporcizia. Costo: 1 per azione (0 per NoOp).

Puzzle dell'8 (8-puzzle). Stati: la posizione intera delle 8 tessere e dello spazio vuoto. Azioni: muovere lo spazio vuoto a sinistra, destra, su, giù (4 azioni al massimo, sono meno ai bordi). Costo: 1 per mossa. Obiettivo: una configurazione assegnata. Le configurazioni sono $9! = 362\,880$, ma raggiungibili da una data sono solo la metà, $9!/2 = 181\,440$, per una proprietà di parità delle permutazioni.

Assemblaggio robotico. Stati: coordinate reali degli angoli dei giunti e parti dell'oggetto già assemblate. Azioni: moti continui dei giunti. Modello: modelli cinematici e dinamici. Obiettivo: assemblaggio completo. Costo: tempo di esecuzione. Qui lo spazio è continuo (Agenti intelligenti - ambienti, PEAS e tipi di agenteUn agente è una funzione dalle sequenze di percezioni alle azioni; è razionale se per ogni sequenza sceglie l'azione che massimizza il valore atteso della misura di prestazione, date le percezioni e la conoscenza incorporata. L'ambiente di lavoro si descrive con PEAS (Performance, Environment, Actuators, Sensors) e si classifica con sette coppie di proprietà (osservabile, deterministico, episodico, statico, discreto, singolo/multi-agente, noto). Le architetture crescono in complessità: reattivo semplice, reattivo basato su modello, basato su obiettivi, basato su utilità, più l'agente che apprende (elemento esecutivo, di apprendimento, critico, generatore di problemi).Agenti intelligenti - ambienti, PEAS e tipi di agente →).

Commesso viaggiatore (Travelling Salesperson Problem, TSP). Ogni vertice di un grafo va visitato (le città di una mappa, oppure i fori da praticare con una trapanatrice automatica sulle schede a circuito stampato).

8 regine. Mettere 8 regine su una scacchiera $8 \times 8$ senza che nessuna ne attacchi un'altra. Si può formulare in due modi, con spazi di dimensioni molto diverse.

Formulazione 1 (incrementale ingenua). Stato: qualunque disposizione di 0-8 regine; iniziale: scacchiera vuota; azione: aggiungere una regina in una qualsiasi casella vuota; obiettivo: 8 regine sulla scacchiera e nessuna attaccata. Le sequenze da esaminare sono $$64 \cdot 63 \cdots 57 = \frac{64!}{56!} \approx 1{,}8 \cdot 10^{14} .$$

Formulazione 2 (migliore). Si vieta di mettere una regina in una casella già attaccata. Stato: disposizioni di $n$ regine ($0 \le n \le 8$), una per colonna nelle $n$ colonne più a sinistra, con nessuna regina che ne attacca un'altra; azione: aggiungere una regina in una casella della colonna vuota più a sinistra che non sia attaccata. Gli stati diventano 2057, e le soluzioni si trovano facilmente. Il numero si verifica contando con un programma (ricorsione sulle colonne): 2057 stati, di cui 92 soluzioni complete.

La lezione: la formulazione conta quanto l'algoritmo. La seconda riduce lo spazio di nove ordini di grandezza.

Alberi di ricerca e frontiera

Si simula l'esplorazione dello spazio degli stati generando i successori degli stati già esplorati (espandere uno stato).

function Tree-Search(problem, strategy) returns a solution, or failure
    initialize the search tree using the initial state of problem
    loop do
        if there are no candidates for expansion then return failure
        choose a leaf node for expansion according to strategy
        if the node contains a goal state then return the corresponding solution
        else expand the node and add the resulting nodes to the search tree

Stati e nodi

Definizione. Uno stato è (la rappresentazione di) una configurazione fisica. Un nodo è una struttura dati che fa parte dell'albero di ricerca e contiene: stato, genitore (parent), azione che l'ha generato, figli, profondità $d$ e costo del cammino $g$.

Gli stati non hanno genitore, figli, profondità o costo. Due nodi diversi possono contenere lo stesso stato (si arriva alla stessa città per strade diverse). Nel codice del laboratorio Node(state, parent, action, path_cost); la lunghezza len(node) è la profondità, e path_states, path_actions risalgono i genitori per ricostruire il cammino.

Frontiera

I nodi non ancora espansi (le foglie) formano la frontiera (frontier): separa lo spazio degli stati in due regioni, visitata e non visitata. Esempio nella Romania da Arad: frontiera iniziale $\{\text{Arad}\}$; dopo aver espanso Arad $\{\text{Sibiu}, \text{Timisoara}, \text{Zerind}\}$; dopo aver espanso Sibiu $\{\text{Arad}, \text{Fagaras}, \text{Oradea}, \text{Rimnicu Vilcea}, \text{Timisoara}, \text{Zerind}\}$. Arad ricompare: nell'albero lo stesso stato può tornare, e senza controlli la ricerca può girare in tondo (Arad $\to$ Sibiu $\to$ Arad $\to \dots$).

Due regole:

• Il test dell'obiettivo si fa quando il nodo viene scelto per l'espansione, non quando entra nella frontiera. È necessario per la correttezza della ricerca a costo uniforme (si vede sotto); la ricerca in ampiezza può farlo prima, alla generazione, come fa il codice del laboratorio.
• Una strategia è determinata dall'ordine in cui si sceglie il nodo da espandere.

Ricerca su albero e ricerca su grafo

La versione sopra è la ricerca su albero (tree search): ignora che gli stati si ripetono. La ricerca su grafo (graph search) aggiunge una tabella reached degli stati già raggiunti con il costo migliore trovato finora: un figlio entra nella frontiera solo se il suo stato non è mai stato raggiunto, oppure se ora è raggiunto con un costo minore. Nel codice del laboratorio:

def best_first_search(problem, f):
    "Search nodes with minimum f(node) value first."
    node = Node(problem.initial)
    frontier = PriorityQueue([node], key=f)
    reached = {problem.initial: node}
    while frontier:
        node = frontier.pop()
        if problem.is_goal(node.state):
            return node
        for child in expand(problem, node):
            s = child.state
            if s not in reached or child.path_cost < reached[s].path_cost:
                reached[s] = child
                frontier.add(child)
    return failure

expand genera i figli di un nodo e PriorityQueue estrae l'elemento con $f$ minima (è uno heap, Code con prioritàEntry chiave-valore; ADT coda con priorità (insert, min, removeMin) con chiave minima = priorità massima; esempio di esecuzione; applicazioni; implementazioni con lista non ordinata e ordinata e relativi costi; ordinamento tramite coda con priorità.Code con priorità →). Il grafo di ricerca è quello delle Grafi - definizioni e proprietàGrafo G=(V,E) diretto e non diretto, grafo semplice e pesato; incidenza, adiacenza, grado; cammini, cicli, sottografi, grafi connessi e componenti connesse; alberi liberi, foreste, spanning tree e spanning forest; proprietà con dimostrazioni (somma dei gradi = 2m, m <= n(n-1)/2, alberi m = n-1, connessi m >= n-1, foreste m <= n-1).Grafi - definizioni e proprietà → e le visite sono le stesse di Visite di grafi - BFS e DFSVisite in ampiezza (BFS) e in profondità (DFS) come design pattern; etichette discovery, cross e back edge; BFS tree e distanze; complessità Theta(n+m) con liste di adiacenza; applicazioni (connettività, componenti, spanning tree, cammini minimi non pesati, cicli, vertici a distanza al più d); esempio svolto su un grafo di 7 vertici.Visite di grafi - BFS e DFS →, con in più i costi.

Valutare una strategia

Quattro criteri:

• completezza: se esiste una soluzione, la trova sempre?
• ottimalità: trova sempre quella di costo minimo?
• complessità in tempo: proporzionale al numero di nodi generati o espansi;
• complessità in spazio: massimo numero di nodi in memoria.

Tempo e spazio si esprimono con tre parametri:

• $b$ = fattore di diramazione massimo (branching factor) dell'albero di ricerca;
• $d$ = profondità della soluzione di costo minimo;
• $m$ = profondità massima dello spazio degli stati (può essere $\infty$).

Ricerca non informata

Le strategie non informate usano solo le informazioni della definizione del problema: non sanno "quanto è lontano" l'obiettivo. Sono sei.

Ricerca in ampiezza (breadth-first search, BFS)

Si espande il nodo meno profondo non ancora espanso. La frontiera è una coda FIFO (first in, first out): i nuovi successori vanno in fondo. Funziona se tutte le azioni hanno lo stesso costo.

Sull'albero binario completo di profondità 3 delle slide (A radice; B, C figli di A; D, E figli di B; F, G figli di C; H, I figli di D; J, K di E; L, M di F; N, O di G), con obiettivo $M$, le frontiere sono: $$\{A\} \to \{B, C\} \to \{C, D, E\} \to \{D, E, F, G\} \to \cdots$$ e l'ordine di espansione è $A, B, C, D, E, F, G, H, I, J, K, L, M$ (13 nodi). Con goal test alla generazione si ferma appena $M$ viene generato espandendo $F$.

Proprietà:

• Completa: sì, se $b$ è finito.
• Tempo: $b + b^2 + b^3 + \dots + b^d = O(b^d)$.
• Spazio: $O(b^d)$, perché tiene in memoria ogni nodo. È il vero problema (a $b = 10$ e $d = 10$ servono $10^{10}$ nodi).
• Ottima: sì se il costo dei passi è 1 (più in generale costante); non in generale. Trova il cammino con meno passi, non quello più economico.

Ricerca a costo uniforme (uniform-cost search, UCS, algoritmo di Dijkstra)

Si espande il nodo di costo $g$ minimo nella frontiera, che è una coda con priorità ordinata per costo del cammino. Equivale alla ricerca in ampiezza se tutti i passi costano uguale, ed è l'algoritmo di Dijkstra (Cammini minimi e algoritmo di DijkstraGrafi pesati, lunghezza di un cammino e distanza; sottocammini di un cammino minimo; problema SSSP; algoritmo di Dijkstra con cloud e priority queue, rilassamento degli archi, esempio svolto; correttezza (due lemmi) e complessità O(min(n^2, (n+m) log n)) con lista non ordinata o heap; pesi non negativi.Cammini minimi e algoritmo di Dijkstra →) fermato quando si estrae l'obiettivo.

Esempio (slide): da Sibiu a Bucarest. Costi tra città dalla mappa.

1. Sibiu (g=0) viene espansa. I successori sono Rimnicu Vilcea (80), Fagaras (99) e, tornando indietro, Arad (140) e Oradea (151).
2. Il minimo è Rimnicu Vilcea (80): si espande e si aggiunge Pitesti ($80 + 97 = 177$) e Craiova ($80 + 146 = 226$).
3. Il minimo è Fagaras (99): si espande e si aggiunge Bucarest con costo $99 + 211 = 310$. Non ci si ferma: l'obiettivo si controlla all'estrazione, non all'inserimento.
4. Seguono Arad (140) e Oradea (151) (che non portano a nulla di meglio: la slide li omette), poi si espande Pitesti (177) e si genera un secondo cammino verso Bucarest, di costo $177 + 101 = 278$.
5. $278 < 310$: il cammino Sibiu $\to$ Rimnicu Vilcea $\to$ Pitesti $\to$ Bucarest sostituisce quello per Fagaras.
6. Si espandono ancora Zerind (215), Craiova (226), Timisoara (258); poi Bucarest (278) è estratta con il costo minore ed è riconosciuta come obiettivo.

Soluzione: Sibiu, Rimnicu Vilcea, Pitesti, Bucarest, costo 278. L'esecuzione in Python (grafo con tabella reached) dà questo ordine di espansione: Sibiu, Rimnicu Vilcea, Fagaras, Arad, Oradea, Pitesti, Zerind, Craiova, Timisoara, Bucarest.

Proprietà:

• Completa: sì se ogni passo costa almeno $\varepsilon > 0$ (così i cammini diventano sempre più costosi e non si resta bloccati su cammini a costo zero).
• Ottima: sì, perché i nodi sono espansi in ordine crescente di $g$: il primo obiettivo estratto ha costo minimo.
• Tempo e spazio: possono essere molto peggiori di $O(b^d)$ per passi piccoli; con $C^\ast$ costo della soluzione ottima e $\varepsilon$ il costo minimo di un passo, sono $O(b^{1+\lfloor C^\ast/\varepsilon\rfloor})$, perché esplora tutti i cammini di costo fino a $C^\ast$, e non solo quelli corti.

Ricerca in profondità (depth-first search, DFS)

Si espande il nodo più profondo non ancora espanso. La frontiera è una pila LIFO (last in, first out): i successori si mettono in testa. Sullo stesso albero: $$\{A\} \to \{B, C\} \to \{D, E, C\} \to \{H, I, E, C\} \to \cdots$$ con ordine di espansione $A, B, D, H, I, E, J, K, C, F, L, M$ (12 nodi).

Proprietà:

• Non completa: fallisce negli spazi a profondità infinita e in quelli con cicli. Si corregge evitando gli stati ripetuti lungo il cammino o fissando una profondità massima (ricerca a profondità limitata).
• Tempo: $O(b^m)$; pessimo se $m \gg d$, ma può essere molto più veloce dell'ampiezza se le soluzioni sono dense.
• Spazio: $O(bm)$, lineare, $\ll O(b^d)$: si tiene solo il cammino corrente con i fratelli non espansi (al più $m(b-1) + 1$ nodi).
• Non ottima: si ferma alla prima soluzione trovata.

Nella Romania, DFS da Arad a Bucarest dipende dall'ordine con cui si provano i vicini. Con i vicini in ordine alfabetico trova Arad $\to$ Sibiu $\to$ Fagaras $\to$ Bucarest (costo 450) espandendo 4 nodi; con l'ordine inverso trova Arad $\to$ Zerind $\to$ Oradea $\to$ Sibiu $\to$ Rimnicu Vilcea $\to$ Pitesti $\to$ Bucarest, di costo 575, dopo aver espanso 12 nodi (con il controllo dei cicli sul cammino): ottimo non è, e dipende dalla fortuna.

Ricerca a profondità limitata (depth-limited search)

È la DFS con una profondità massima $\ell$: i nodi a profondità $\ell$ non si espandono. Restituisce "fallimento" se non esiste soluzione, "cutoff" se il limite ha tagliato qualcosa. Tempo $O(b^\ell)$, spazio $O(b\ell)$. Non è completa se $\ell < d$; non è ottima se $\ell > d$.

Ricerca ad approfondimento iterativo (iterative deepening search, IDS)

Si esegue la ricerca a profondità limitata con $\ell = 0, 1, 2, \dots$ finché si trova la soluzione (o non si ha più "cutoff"). Sull'albero binario con obiettivo $M$:

Combina i vantaggi: completa (come l'ampiezza), spazio $O(bd)$ (come la profondità), ottima se i costi dei passi sono uguali.

Rifare le iterazioni precedenti sembra uno spreco, ma il costo è dominato dall'ultimo livello. I nodi del livello $i$ sono generati $d - i + 1$ volte: $$N(\text{IDS}) = d\,b + (d-1)\,b^2 + \dots + 2\,b^{d-1} + b^d = O(b^d).$$

Esempio (slide). $b = 10$, $d = 5$, soluzione nella foglia più a destra: $N(\text{IDS}) = 50 + 400 + 3\,000 + 20\,000 + 100\,000 = 123\,450$, $N(\text{BFS}) = 10 + 100 + 1\,000 + 10\,000 + 100\,000 = 111\,110$. Il sovraccosto è il $11\%$ circa, $123\,450/111\,110 \approx 1{,}111 = b/(b-1)$.

Per questo l'IDS è la strategia non informata di scelta quando lo spazio è grande e la profondità della soluzione è ignota.

Ricerca bidirezionale

Due ricerche simultanee, una in avanti dallo stato iniziale e una all'indietro dall'obiettivo, con ampiezza o costo uniforme; ha successo quando le due frontiere si incontrano. Il motivo: $O(b^{d/2}) + O(b^{d/2}) \ll O(b^d)$. Con $b = 10$ e $d = 6$: $2 \cdot 10^3 = 2000$ contro $10^6$.

• Completa se $b$ e lo spazio sono finiti; tempo e spazio $O(b^{d/2})$; ottima se i costi sono uguali.
• Si applica bene a problemi con un solo stato obiettivo (il miglior percorso da Arad a Bucarest). Con più obiettivi espliciti (due stanze pulite nel mondo dell'aspirapolvere) si aggiunge uno stato obiettivo fittizio i cui predecessori immediati sono tutti gli obiettivi veri. Se l'obiettivo è una descrizione astratta ("nessuna regina ne attacca un'altra") è difficile da usare.
• Sulla Romania da Arad a Bucarest (ampiezza dai due lati, alternando) le frontiere si incontrano a Fagaras dopo 3 espansioni in tutto (contro 5 dell'ampiezza semplice).

Tutte le strategie sono best-first search

Il codice di best_first_search sopra sceglie sempre il nodo con $f$ minimo. Cambiando solo $f$ si ottengono le strategie:

def g(n): return n.path_cost
def uniform_cost_search(problem):   return best_first_search(problem, f=g)
def breadth_first_bfs(problem):     return best_first_search(problem, f=len)                # profondità
def depth_first_bfs(problem):       return best_first_search(problem, f=lambda n: -len(n))  # profondità negata
def greedy_bfs(problem, h=None):    return best_first_search(problem, f=h or problem.h)
def astar_search(problem, h=None):  return best_first_search(problem, f=lambda n: g(n) + (h or problem.h)(n))

len(n) è la profondità del nodo. Le versioni "vere" della ricerca in ampiezza e in profondità del laboratorio (breadth_first_search con coda FIFO e iterative_deepening_search) sono più efficienti: non pagano la priority queue e la prima fa il test dell'obiettivo alla generazione. Il laboratorio è svolto in Esercizio - Algoritmi di ricerca in Python con Problem, Node e best-first search (laboratorio 3); le due ricerche informate sono nella nota seguente.

Sulla Romania del laboratorio, con $A$ Arad e $B$ Bucarest, uniform_cost_search restituisce il cammino ['A', 'S', 'R', 'P', 'B'] (costo $140 + 80 + 97 + 101 = 418$), mentre breadth_first_search restituisce ['A', 'S', 'F', 'B']: meno passi (3) ma costo maggiore, $140 + 99 + 211 = 450$. È la differenza tra ottimalità sui passi e sul costo.

Confronto

Sulla Romania (da Arad a Bucarest, vicini in ordine alfabetico, nodi espansi con la ricerca su grafo):

Il costo uniforme espande più nodi di tutti (esplora in ogni direzione fino a costo 418), ma è l'unico, con l'ampiezza sui passi, a garantire la soluzione ottima: per spendere meno serve l'informazione di 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 →.

Domande d'esame

1. Con $b = 10$ e $d = 5$ quanti nodi genera, al più, la ricerca in ampiezza (soluzione nell'ultima foglia) e quanti l'approfondimento iterativo? BFS $10 + 100 + 1\,000 + 10\,000 + 100\,000 = 111\,110$; IDS $5 \cdot 10 + 4 \cdot 100 + 3 \cdot 1\,000 + 2 \cdot 10\,000 + 1 \cdot 100\,000 = 123\,450$.
2. Con la ricerca a costo uniforme da Sibiu a Bucarest, qual è il costo della soluzione e perché non ci si ferma quando Bucarest entra nella frontiera? Costo 278 (Sibiu, Rimnicu Vilcea, Pitesti, Bucarest). Bucarest entra la prima volta con costo $99 + 211 = 310$ (via Fagaras), ma poi si trova $80 + 97 + 101 = 278$: il test dell'obiettivo si fa all'estrazione dalla coda, quando il costo è minimo.
3. Quanta memoria usa la ricerca in profondità con $b = 3$ e $m = 10$ (al massimo)? Il cammino corrente più i fratelli non espansi: $m(b-1) + 1 = 10 \cdot 2 + 1 = 21$ nodi, contro $3^{10} = 59\,049$ nodi dell'ultimo livello.
4. Perché la ricerca bidirezionale è più efficiente? Quanto vale con $b = 10$, $d = 6$? Ciascuna delle due ricerche arriva solo a profondità $d/2$: $2 \cdot 10^3 = 2\,000$ nodi invece di $10^6$.
5. Quanti stati ha la formulazione migliore delle 8 regine? 2057 (una regina per colonna a sinistra, nessuna attaccata) contro $\approx 1{,}8 \cdot 10^{14}$ sequenze della prima.