Algoritmi di ricerca su Grafo

Una volta ottenuto G, è necessario sfruttare le informazioni che vi sono contenute al fine di trovare il miglior percorso, tra quelli possibili.

Un caso molto comune è quello di andare a considerare ogni arco del grafo associato ad un peso, rappresentato dalla lunghezza dell’arco stesso. Ricordando come il peso tra i vertici ni e nj sia stato definito come w(ni, nj), si può estendere genericamente

questa funzione definendo w(ni, nj) = ∞qualora non esista l’arco e(ni, nj). An-

dando adesso a definire come vertici finali ns(nodo start) e ng (nodo goal), la somma

dei costi sugli archi che definiscono il path ns− ng fisserà il costo del path stesso. La

distanza minima del path ns− ng è chiamata shortest path da nsa ng.

Esistono diversi metodi per risolvere tale problema e ricercare il miglior percorso con- sentito dal grafo.

Questo risulta essere un problema trattato di frequente in differenti ambiti. Va sotto- lineato comunque che, apportate le dovute modifiche, risulta adattabile a svariati casi di studio. Infatti, la grandezza che definisce il costo dell’arco può, sotto determinati limiti in funzione dell’algoritmo utilizzato, essere sostituita o modificata da un valore più consono rispetto al problema specifico, così come fatto in questo elaborato. Per questo motivo, risulta importante specificare come il concetto di "migliore" sia una caratteristica che debba essere descritta opportunamente all’interno dell’algorit- mo stesso e non forzatamente associato alla ricerca del percorso più breve.

Tra gli algoritmi di ricerca presenti in letteratura, sicuramente i più diffusi sono l’al- goritmo di Dijkstra e l’algoritmo A*. Senza perdere di generalità verrà presentata una loro descrizione di seguito ai fini di ricercare lo shortest path. Successivamente ver- ranno specificate le modifiche apportate in questa tesi affinché la ricerca rispondesse ai criteri di ottimalità derivanti dal problema trattato.

Dijkstra

Questo algoritmo, inventato dall’omonimo informatico olandese nel 1956, può essere utilizzato col fine di ricercare i cammini minimi in un grafo con o senza ordinamento e con pesi non negativi sugli archi.

Come già detto, andiamo a denotare con N i nodi di G. Introduciamo anche l’insieme S ⊂ N tale che s ∈ S; definiamo ¯S come il complemento di S, contenuto in N, cioè

¯

S = N − S.

Tra tutti i possibili path diretti da s ad un nodo in ¯S, identifichiamo con P quello a lunghezza minima e chiamiamo quest’ultima distanza d(s, ¯S), da s a ¯S. Quindi, P = s, ..., u, v, con v ∈ ¯Se tutti gli altri nodi s, ..., u ∈ S. Ne deriva che la sezione di P da s ad u deve rappresentare il più breve s-u path con tutti i nodi in S. Da cui:

d(s, ¯S) = d(s, u) + w(u, v). (3.1)

Per cui la distanza che risolve il problema dello shortest path può essere ottenuta attraverso la formula

d(s, ¯S) = min

u∈ S, v∈ ¯S

{d(s, u) + w(u, v)}. (3.2)

Se v è il nodo di ¯S tale per cui d(s, ¯S) = d(s, u) + w(u, v)per una u ∈ S, allora

d(s, v) = d(s, ¯S). (3.3)

L’algoritmo di Dijkstra va a costruire una sequenza S0 = {s}; S1 S2, ... di sottoin-

siemi di N tale che vengano rispettate le seguenti condizioni:

• se s = u0; u1, u2, ..., un−1sono nodi di N tali che d(s, u1) ≤ d(s, u2) ≤ ... ≤

d(s, un−1), allora Si = {s, u1, u2, ..., ui}per i > 0.

• Quando l’insieme Sisarà determinato, allora lo shortest path da s ad u1, u2, ..., ui

Se l’insieme Si è definito in partenza, allora grazie a (3.3) abbiamo che

d(s, ui+1) = d(s, ¯Si). (3.4)

Per cui andrà determinato l’insieme Si+1 a partire da Si, utilizzando la conoscen-

za di d(s, ¯Si). Risulta, quindi, possibile costruire iterativamente la successione di

sottoinsiemi S1, S2, ..., Sn−1attraverso (3.2): d(s, ¯S0) = min u∈ S0, v∈ ¯S0 {d(s, u) + w(u, v)} = min v∈ ¯S0 {w(s, v)} (3.5) e tramite (3.4) d(s, u1) = min v∈ ¯S0 {w(s, v)}. (3.6)

Se usiamo la notazione secondo cui Piindica il path a costo minore dal nodo s al nodo

ui, naturalmente P1 è il path più breve tra s ed u1.

Supponiamo adesso di aver calcolato i sottoinsiemi S0, S1, ..., Si ed i relativi path

P1, P2, ..., Pi. Sarà ora necessario determinare Si+1, per farlo passiamo dal calco-

lo di d(s, ¯Si) usando (3.2). Da (3.4), ui+1 è in nodo di ¯Si per cui vale la proprietà

che d(s, ui+1) = d(s, ¯Si). Per cui, esiste un vertice uj ∈ Si tale che d(s, ui+1) =

d(s, uj) + w(uj, ui+1). Possiamo ottenere Pi+1aggiungendo l’arco (uj, ui+1)al path

Pi.

A questo punto va specificato l’obiettivo dell’algoritmo. Esso può essere utilizzato per calcolare l’albero di copertura minimo, cioè il cammino aperto tale per cui, dato un nodo di partenza, tutti i nodi siano raggiunti. Nel caso in esame, invece, siamo in- teressati a raggiungere un nodo specifico. Detto questo nodo ng ∈ N, la procedura

dovrà prevedere di arrestarsi nel momento in cui venga trovato il primo sottoinsieme Si ⊂ N | ng ∈ Si.

Per una realizzazione del processo, verrà formata una coda dei nodi, ordinati per costo decrescente. Essa verrà inizializzata con i costi relativi al cammino tra la sorgente ed il singolo nodo, generalmente definito cost-to-come, tutti parti ad infinito, in quanto il cammino non è ancora noto. Solo quello relativo al nodo sorgente è definito conven- zionalmente pari a zero. Ogni ciclo il nodo a costo minore verrà estratto dalla coda

e ne verranno analizzate le adiacenze. Se il costo per arrivare al nodo sommato al costo per andare in quello adiacente, risulta minore rispetto a quanto quest’ultimo ha attualmente in memoria, vorrà dire che si è trovato un percorso migliore e dovranno essere aggiornati costo e genitore del nodo visitato. Per l’obiettivo di questo lavoro verrà inizializzato l’algoritmo a partire da un nodo sorgente e dato uno o più nodi tar- get. Per una più semplice comprensione, viene di seguito riportato uno pseudo-codice descrittivo di una possibile implementazione.

A*

L’A* è una variante della programmazione dinamica che tenta di ridurre il numero di iterazioni da effettuare per calcolare il cammino minimo tra due nodi. Nel 1968 Peter Hart, Nils Nilsson, e Bertram Raphael hanno per la prima volta descritto l’algoritmo[34]. Il problema della ricerca su grafo, infatti, è un problema molto studiato e che ha gene- ricamente due vie di risoluzione: quella matematica e quella euristica.

La prima delle due prende in considerazione esclusivamente la realizzazione di un al- goritmo che fornisca una soluzione, basandosi su un grafo astratto per ricercare un percorso a costo minimo.

La via euristica, invece, tenta di rispondere anche a delle esigenze tecnologiche nel dare un’efficienza computazionale al processo di ricerca.

L’A* è stato il primo esempio di algoritmo che andava ad incorporare entrambe le ca- ratteristiche col fine di produrre una soluzione ottima, ma anche computazionalmente soddisfacente. Fa parte della categoria di algoritmi definiti come best-first search, con i quali si tenta di interpolare suppletive conoscenze sul problema in esame in modo da diminuire il calcolo computazionale richiesto al sistema.

Questo viene fatto incorporando un’euristica di stima della distanza dal target, nota come cost-to-go. La differenza sostanziale tra quest’algoritmo e il precedente, infatti, sta nella modalità di ordinamento della coda: essa non sarà più ordinata in funzione del solo cost-to-come, bensì della somma cost-tot = cost-to-come + cost-to-go.

Algorithm 1 Dijkstra ( G, start, goal )

% G := Grafo; start:=nodo di partenza; goal:=nodo d’arrivo

1: % Inizializzazione

2: goalRaggiunto = f alse;

3: for each nodo n ∈ N ⊂ G

4: cost[n] = ∞; %cost − to − come non conosciuto

5: genitore[n] = −1; %genitore non conosciuto

6: end for

7: cost[start] = 0; %cost_to_come di partenza

8: Open := insieme ordinato dei nodi in f unzione del vettore cost

9: while( !isempty(Open) ) do 10: a = Open[0]; 11: if (a == goal) then 12: goalRaggiunto = f alse; 13: endWhile 14: rimuovi a da Open

15: if ( cost[a] = ∞ ) then return ERROR;

16: for each adiacenze[a] ← b %con b ∈ Open

17: tmp_cost = cost[a] + cost[a → b];

18: if ( tmp_cost < cost[b] ) then

19: %Aggiornamento dei dati relativi al nodo b

20: cost[b] = tmp_cost;

21: genitore[b] = a;

22: end for

23: sort(Open);

24: if (!goalRaggiunto) then return ERROR;

intermedio a quello target. È però possibile avere una stima inferiore di tale valore. Fondamentalmente, quindi, lo pseudocodice riportato vale anche in questo caso, con l’unica differenza che il valore da associare ciclicamente al nodo sarà formato da due parti: il cost-to-come ed il cost-to-go. Essendo quest’ultimo un’euristica non potrà es- sere effettivamente assegnato al nodo, bensì verrà utilizzato per il calcolo del costo totale, rispetto al quale verrà ordinata la lista Open().