Ricerca non informata
Algoritmi analizzati:
- Breadth first search (BFS)
- Uniform cost search (Dijkstra)
- Depth first search (DFS)
- Depth-limited search
- Iterative-deepening DFS
- Ricerca bidirezionale
Breadth first search (BFS)
Si parte dal nodo radice e si espande la ricerca a partire da esso. Ci si espande di volta in volta sui nodi più vicini ad ognuno di quelli già esplorati, espandendosi equamente in tutte le direzioni.
Per i nodi della frontiera e capire quali espandere per primi si utilizza una coda FIFO.
- Completezza: sì
- Ottimalità: Sì, se tutti i rami hanno lo stesso costo, ma non in generale
- Complessità temporale: O\left(b^d\right) → ogni stato ha b successori (b si chiama infatti branching factor) e una soluzione è a profondità d
- Complessità spaziale: O\left(b^d\right)
Uniform cost search (Dijkstra)
È basato sulla stessa idea del Breadth first, però, a differenza di esso, l’espansione dei nodi è ordinata secondo una funzione di costo g(n) che ordina i nodi della frontiera selezionando prima quelli di costo minore.
Nota bene: il goal test viene applicato quando un nodo viene selezionato per essere espanso, non quando viene generato.
La problematica di cui questo algoritmo potrebbe soffrire è la possibilità di bloccarsi all’interno di un loop a costo costante o nullo, che non gli permettono di avvicinarsi abbastanza in fretta alla soluzione.
- Completezza: Sì (assumendo che ogni costo sia positivo)
- Ottimalità: Sì (se si espandono i nodi in ordine crescente di costo)
- Complessità temporale: O\left(b^d\right) → ogni stato ha b successori (b si chiama infatti branching factor) e una soluzione a profondità d
- Complessità spaziale: O\left(b^d\right)
Depth first search (DFS)
È un algoritmo che può essere considerato la “versione opposta” del breadth first, infatti invece di espandersi equamente in tutte le direzioni, tramite questo algoritmo, una volta che è stata scelta una direzione, la si esplora in tutta la sua profondità, ripetendo il processo finché non si arriva a trovare una soluzione.
Per memorizzare i nodi della frontiera e capire quali espandere per primi si utilizza una coda LIFO.
- Completezza: No (nel caso in cui il problema abbia profondità infinita)
- Ottimalità: No (si ferma appena trova una soluzione, che però non è necessariamente la migliore)
- Complessità temporale: O(b^m) → ogni stato ha b successori e m rappresenta la maggior profondità del nodo in considerazione. Le prestazioni peggiorano quando m\gg b
- Complessità spaziale: O(b\cdot m) → è il punto di forza dell’algoritmo DFS
Depth-limited search
Partendo dall’algoritmo DFS poniamo un limite alla massima profondità di ricerca \ell che l’algoritmo raggiunge.
- Completezza: No
- Ottimalità: No
- Complessità temporale: O\left(b^\ell\right)
- Complessità spaziale: O(b \cdot\ell)
Iterative-deepening depth first search
Utilizza le tecniche di base dell’algoritmo depth first, assieme al depth-limited. In particolare, utilizzando una profondità massima d variabile, l’algoritmo esplora tutte le direzioni fino alla profondità d tramite l’algoritmo DFS, per aggiornare poi il valore di d in d' espandendo equamente la profondità di esplorazione in tutte le direzioni come il BFS. Una volta che sono stati esplorati tutti i nodi fino alla nuova distanza d' viene aggiornato il suo valore in d'' e la procedura viene ripetuta.
- Completezza: Sì
- Ottimalità: Sì (se ogni ramo ha costo unitario)
- Complessità temporale: O\left(b^d\right)
- Complessità spaziale: O(b\cdot d)
Ricerca bidirezionale
Vengono svolte due ricerche allo stesso momento, una che parte dallo stato iniziale e l’altra dallo stato finale. Le due ricerche—se trovano una soluzione!—si incontrano al centro.
Il goal test viene sostituito con un controllo per vedere se le due frontiere si sono incontrate.
Di fatto, la ricerca bidirezionale viene usata assieme a qualche altro algoritmo di ricerca, che viene fatto partire dai punti di inizio e fine, aspettando che si incontri al centro.
- Completessa: Sì
- Ottimalità: Sì
- Complessità temporale: O\left(b^{d/2}\right) → ogni stato ha b successori (b si chiama infatti branching factor) e una soluzione a profondità d
- Complessità spaziale: O\left(b^{d/2}\right) → utilizziamo il valore d/2 perché, generalmente, i due algoritmi si incontreranno a metà, dunque a distanza d/2 dal punto di partenza
Algoritmi di ricerca informata
A differenza degli algoritmi di ricerca non informata, questi nuovi algoritmi utilizzano una funzione euristica h(n) definita come
h(n)=\text{costo stimato dal nodo attuale al nodo obiettivo}Se il nodo coincide con l’obiettivo si ha h(n)=0.
Poiché h(n) sia un’euristica valida si deve avere h(n)>0 per ogni ramo.
Talvolta, può essere utile utilizzare anche delle euristiche di tipo composto, ognuna con un peso diverso sulla decisione finale, in maniera tale da ottenere la miglior euristica per la risoluzione del problema.
Si avrà dunque una combinazione lineare delle I diverse sotto-euristiche h_i'(n) pesate ognuna della quantità w_i sul risultato finale
h(n)=\sum_{i\in I}w_i \cdot h_i'(n)Algoritmi analizzati:
- Greedy best first search
- A^*
- A^* pesato
Greedy best first search
Viene espanso il nodo che sembra portarci più vicino all’obiettivo (secondo la metrica utilizzata per il problema), sperando che tale nodo porti ci conduca in fretta a trovare la soluzione cercata. Si tratta però di un algoritmo greedy, dunque esegue qualunque azione che migliori lo stato attuale, senza molta lungimiranza verso quale possa essere il miglior percorso in generale.
- Completezza: No
- Ottimalità: No
- Complessità temporale: O(b^m)
- Complessità spaziale: O(b^m)
A*
Oltre alla funzione euristica h(n), l’algoritmo A^* utilizza anche una funzione g(n) per rappresentare il costo per arrivare fino al nodo corrente. La funzione utilizzata per trovare il percorso ottimale per risolvere un problema sarà dunque data da
f(n)=h(n)+g(n)
dove si vorrà minimizzare il valore di f(n), consentendoci quindi di trovare il percorso di distanza minore tra quello iniziale e quello finale—a patto che l’euristica h(n)
- non sovrastimi mai il vero costo di raggiungere l’obiettivo
- deve essere consistente, cioè deve rispettare la proprietà
h(n) < c(n, \, a, \, n')+h(n')
A parole: il costo stimato di raggiungere l’obiettivo da un qualunque nodo n deve essere minore della somma tra il costo di raggiungere il nodo successivo n' tramite un’azione a e il costo di raggiungere il nodo obiettivo partendendo direttamente dal nodo n' (cfr. l’ipotenusa nei triangoli).
- Completezza: Sì
- Ottimalità: Sì (a patto che h(n) rispetti le caratteristiche citate)
- Chiamando C^* il costo della soluzione ottimale si avrà:
- A^* espande tutti i nodi in cui f(n)<C^*
- A^* potrebbe espandere alcuni dei nodi in cui f(n)=C^*
- A^* non espande alcun nodo in cui f(n)>C^*
A* pesato
Rende possibile la visitazione dello spazio in maniera più veloce. Vengono infatti presi maggiori rischi esplorando dei nodi che sembrano non essere ottimali, ma che potrebbero portare a soluzioni migliori.
In termini di f(n) si ha:
f(n)=g(n)+W\cdot h(n)\qquad W\in[1, \, +\infty)
Di fatto, l’utilizzo di un peso variabile nell’algoritmo A^* permette di ricreare diversi altri algoritmi già analizzati. Si avrà, per esempio
- Se W=1\Rightarrow f(n)=g(n)+h(n), ovvero il semplice algoritmo A^*
- Se W=0\Rightarrow f(n)=g(n), dunque non si riesce a stimare la distanza dall’obiettivo, proprio come nell’uniform-cost search (Dijkstra)
- Se W=+\infty\Rightarrow f(n)\to h(n), quindi siamo in grado di vedere soltanto la distanza rispetto all’obiettivo, ignorando quella dal punto di partenza, come nel caso dell’algoritmo greedy best-first
- Se W\in[0,\,+\infty) si ottengono delle variabili pesate dell’A^* che hanno caratteristiche diverse a seconda del peso scelto
Oltre la ricerca classica
Algoritmi trattati:
- Ricerca locale
- Hill climbing
- Stochastic hill climbing
- First choice hill climbing
- Random restart hill climbing
- Simulated annealing
- Local beam search
- Genetic algorithms (GAs)
Ricerca locale
Utilizza poca memoria ed è utile per trovare soluzioni a problemi che appartengono a spazi molto grandi o infiniti.
Spesso vengono utilizzati per trovare soluzioni a problemi di pura ottimizzazione come il TSP (Travelling Sales Person) o il problema delle n-regine.
Si tratta di algoritmi di tipo iterativo che cercano di migliorare lo stato corrente senza tener conto né degli stati passati né di quelli futuri.
Hill climbing
Se siamo in uno spazio 2D si chiama hill climbing, mentre se siamo in spazio 3D (o maggiore) prende il nome di gradient ascent/descent.
L’algoritmo cerca di muoversi in maniera iterativa nella direzione del massimo/minimo in uno spazio come quello in figura.
Si definisce talvolta greedy, infatti non gli importano gli stati lontani nel futuro ma soltanto la ricerca di uno stato successivo che sia migliore di quello corrente.
Non e né un algoritmo ottimo né completo. Potrebbe infatti bloccarsi, ad esempio, in dei punti di massimo/minimo locale.
Esistono però delle variazioni per evitare che ciò accada:
- Stochastic hill climbing: sceglie un movimento in maniera casuale tra le molteplici possibilità disponibili. Converge a una soluzione in maniera più lenta rispetto a quello normale però e in grado di trovare delle soluzioni migliori
- First choice hill climbing: genera dei successori in maniera casuale finché non ne viene generato uno che è migliore rispetto a quello attuale. È una buona strategia se sono presenti grandi quantità di successori
- Random restart hill climbing: esegue una serie di restart da degli stati iniziali generati in maniera casuale finché non converge all’obiettivo. In media, il numero di restart necessari è pari a 1/p nel caso in cui ci siano p successori per ogni stato di restart
Simulated annealing
È simile all’hill climbing, però invece di scegliere la miglior mossa per uno stato (ovvero quella che minimizza la distanza dall’obiettivo), viene scelta una mossa casuale tra quelle che si avvicinano all’obiettivo.
Nel caso in cui il movimento migliori la situazione attuale viene sempre accettato, altrimenti l’algoritmo accetta mosse che non migliorano la situazione attuale con probabilità minore di 1 in base a “quanto negativa” una mossa è. Col passare del tempo le mosse negative diminuiscono.
Local beam search
Funziona in maniera simile al simulated annealing, però tiene traccia di k stati invece che uno solo.
Comincia generando in maniera casuale k stati. Per ognuno di essi vengono generati k possibili successori, da tale insieme (formato da k k successori totali poiché ognuno dei k stati genera a sua volta k successori) vengono scelti i migliori k stati per continuare la ricerca ripetendo i precedenti passaggi finché non si raggiunge l’obiettivo.
Un problema che si viene a riscontrare nella ricerca local beam è che spesso tutti i k stati finiscono nella stessa zona di massimo/minimo locale—fatto che viene però limitato grazie alla scelta casuale dei k successori.
Genetic algorithms (GAs)
È una variante della ricerca locale stocastica in cui vengono applicate delle mutazioni ai k stati nei quali due coppie sono selezionate in maniera casuale per la riproduzione. In questo modo la prole prende caratteristiche che appartengono a entrambi i genitori.
Questo tipo di algoritmi hanno bisogno di codificare ogni stato tramite una stringa, in maniera tale da poterla combinare con altre stringhe per creare dei figli. La mutation rate determina quanto spesso i figli hanno delle mutazioni casuali che vengono inserite nella loro struttura.
Viene inoltre introdotta una fitness function per giudicare la bontà di una certa generazione.
In poche parole
Gli algoritmi di ricerca più comuni includono
✅ Ricerca non informata
- Breadth First Search (BFS): espande la ricerca uniformemente in tutte le direzioni.
- Uniform Cost Search (Dijkstra): espande i nodi con il costo minore.
- Depth First Search (DFS): espande i nodi fino alla massima profondità prima di tornare indietro.
- Depth-Limited Search: DFS con limite di profondità.
- Iterative-Deepening Depth First Search: DFS con profondità massima variabile.
- Ricerca Bidirezionale: due ricerche simultanee da nodo iniziale e nodo finale.
✅ Ricerca informata
- Greedy Best First Search: espande il nodo che porta più vicini all’obiettivo.
- A*: utilizza una funzione di valutazione f(n) per selezionare il percorso più promettente.
- A pesato*: variazione di A* che permette una ricerca più veloce accettando percorsi con rischio maggiore, ovvero che potrebbero non portare a una soluzione.
✅ Oltre la ricerca classica
- Ricerca Locale: algoritmi iterativi che migliorano lo stato corrente accettando ogni movimento che migliora lo stato corrente senza considerare passato o futuro.
- Hill Climbing: si muove verso il massimo/minimo in maniera greedy.
- Stochastic hill climbing
- First choice hill climbing
- Random restart hill climbing
- Simulated Annealing: sceglie in maniera casuale delle mosse (che non necessariamente migliorano la situazione attuale) per avvicinarsi all’obiettivo.
- Local Beam Search: mantiene in memoria più stati contemporaneamente generandone più di quanti effettivamente ne utilizzi, concentrandosi soltanto sugli stati migliori.
- Algoritmi Genetici (GAs): algoritmi ispirati all’evoluzione biologica per la ricerca di soluzioni ottimali, sceglie le caratteristiche di due o più stati tramite cui creare un ulteriore stato che abbia delle caratteristiche intermedie tra essi.