Soluzione: Algoritmo A*
Complessità: Dipende dall'implementazione della coda di minima priorità (si veda [4]). In questo caso, per non complicare inutilmente il codice, si aggira completamente il problema usando semplicemente un array che porta ad un tempo totale $O(V^2)$
Il problema è praticamente lo stesso di quello che si risolve con l'algoritmo di Dijkstra (si veda [2]) solo che qui si cerca un cammino preciso invece che tutti i cammini minimi dalla sorgente.
Di fatto basterebbe una piccola modifica al codice dell'algoritmo di Dijkstra (3 righe al massimo) per ottenere la soluzione al problema del cammino minimo da sorgente a destinazione. Nella figura sotto, a sinistra, si vede che l'algoritmo di Dijkstra impiega 5 iterazioni per raggiungere il vertice $6$ a partite da $1$.
bool dijkstra(Edge **g, Vertex *v, Vertex *t, size_t size) { v->distance = 0; std::queue<Vertex*> v_queue; std::vector<unsigned int> arr_distance(size); for (size_t i = 0; i < size; ++i) { if (i == v->index) arr_distance[i] = v->distance; else arr_distance[i] = (unsigned)-1; } while (v_queue.size() != (size - 1)) { size_t index = extract_min(arr_distance.data(), size); arr_distance[index] = (unsigned)-1; Edge *e = g[index]; v = e->head; v_queue.push(v); if (v == t) return true; while (e != nullptr) { relax(e, arr_distance.data()); e = e->next; } } return false; }
L'algoritmo A* (A star) non è altro che una ottimizzazione dell'algoritmo di Dijkstra. Quest'ultimo (come visto in [2]) attraversa il grafo selezionando i vertici che hanno distanza minore dalla sorgente, calcolata sommando i pesi degli archi (chiamiamo la funzione che calcola queste distanze $G$). Quindi se gli archi dei percorsi che portano al vertice destinazione hanno dei pesi grandi è probabile che ci vogliano parecchie iterazioni, e quindi più tempo, prima che l'algoritmo di Dijkstra lo selezioni. L'algoritmo A* cerca invece di indirizzare la ricerca verso il vertice destinazione "aggiustando" la funzione $G$ attraverso un'altra funzione che chiamiamo, in modo del tutto arbitrario, $H$.
L'algoritmo A* dunque estrarrà il vertice corrente da processare dalla coda di minima priorità prendendo non più il vertice con $G$ minore ma piuttosto il vertice che avrà valore $F = G + H$ minore rispetto a tutti gli altri. Se, per ipotesi, $H$ restituisse sempre $0$ l'algoritmo sarebbe praticamente quello di Dijkstra.
$G$, dunque, resta uguale alla funzione usata nell'algoritmo di Dijkstra per calcolare il cammino minimo corrente (considerando esclusivamente i pesi degli archi) dei vertici $v$ collegati al vertice $u$, che è il vertice selezionato all'iterazione corrente.
$\mathbf{G(u, v):}$
$\quad \mathbf{return}\enspace u.\!distance + peso(u, v)$
$H$ invece dipende da come si vuole indirizzare l'algoritmo verso il vertice destinazione $t$. Se, ad esempio, i vertici del grafo hanno, tra le loro proprietà, anche la descrizione della loro posizione all'interno dello spazio 2D o 3D allora si può definire $H$ come distanza euclidea, o come distanza euclidea al quadrato (in modo da evitare il costoso calcolo della radice; anche se una versione ottimizzata esiste, si veda [5]), oppure , come nel codice utilizzato in questo articolo, si può usare la distanza di Manhattan (si veda [3]).
$\mathbf{H(v,t):}$
$\quad \mathbf{return}\enspace |t.x - v.x| + |t.y - v.y|$
Quindi la funzione relax implementata per l'algoritmo di Dijkstra diventa
$\mathbf{relax(u,v,t):}$
$\quad \mathbf{if}(F(v) > G(u, v) + H(v,t))$
$\quad \quad F(v) = G(u,v) + H(v,t)$
Nella figura sopra, a destra, si vede che l'algoritmo A*, con $H$ definita come distanza di Manhattan, impiega 3 iterazioni per raggiungere il vertice $6$ a partire da $1$. Nella figura sotto si può vedere la rappresentazione del grafo utilizzato per l'esempio di codice seguente.
#include <iostream> #include <queue> #include <vector> struct Vertex { Vertex *parent; unsigned int distance; unsigned int index; float x; float y; }; struct Edge { Vertex *head; Vertex *tail; Edge *next; unsigned int weight; }; bool A_star(Edge**, Vertex*, Vertex*, size_t); size_t extract_min(float*, float*, size_t); void calculate_H(Edge*, Vertex*, float*); void relax(Edge*, Vertex*, float*, float*); void print_path(Edge**, Vertex*, Vertex*, size_t); int main(int argc, char* argv[], char* env[]) { Vertex v1{ nullptr, (unsigned int)-1, 1, 0.0f, 0.0f }; Vertex v2{ nullptr, (unsigned int)-1, 2, 15.0f, 20.0f }; Vertex v3{ nullptr, (unsigned int)-1, 3, 40.0f, 16.0f }; Vertex v4{ nullptr, (unsigned int)-1, 4, 50.0f, 0.0f }; Vertex v5{ nullptr, (unsigned int)-1, 5, 10.0f, -20.0f }; Vertex v6{ nullptr, (unsigned int)-1, 6, 35.0f, -15.0f }; Vertex *v[7] = { nullptr, &v1, &v2, &v3, &v4, &v5, &v6 }; Edge *graph[7] = { nullptr }; Edge e1_25{ v[1], v[5], nullptr, 3 }; Edge e1_12{ v[1], v[2], &e1_25, 6 }; graph[1] = &e1_12; Edge e2_53{ v[2], v[3], nullptr, 3 }; Edge e2_25{ v[2], v[5], &e2_53, 1 }; graph[2] = &e2_25; Edge e3_34{ v[3], v[4], nullptr, 5 }; graph[3] = &e3_34; Edge e4_46{ v[4], v[6], nullptr, 1 }; graph[4] = &e4_46; Edge e5_36{ v[5], v[6], nullptr, 6 }; Edge e5_23{ v[5], v[3], &e5_36, 7 }; Edge e5_52{ v[5], v[2], &e5_23, 2 }; graph[5] = &e5_52; Edge e6_64{ v[6], v[4], nullptr, 2 }; graph[6] = &e6_64; size_t size = sizeof(v) / sizeof(Vertex*); if (A_star(graph, v[1], v[6], size)) print_path(graph, v[1], v[6], v[6]->index); else std::cout << "Such a vertex is out of reach!"; return 0; } bool A_star(Edge **g, Vertex *v, Vertex *t, size_t size) { v->distance = 0; std::queue<Vertex*> v_queue; std::vector<float> arr_F(size); std::vector<float> arr_H(size); for (size_t i = 0; i < size; ++i) { if (i == v->index) // per sorgente G = 0 e H non importante: si deve partire comunque da vertice sorgente arr_F[i] = arr_H[i] = v->distance; else arr_F[i] = arr_H[i] = FLT_MAX; } while (v_queue.size() != (size - 1)) { size_t index = extract_min(arr_F.data(), arr_H.data(), size); arr_F[index] = arr_H[index] = FLT_MAX; Edge *e = g[index]; v = e->head; v_queue.push(v); if (v == t) return true; while (e != nullptr) { relax(e, t, arr_F.data(), arr_H.data()); e = e->next; } } return false; } size_t extract_min(float *arr_F, float *arr_H, size_t size) { size_t min_index = -1; float min = FLT_MAX; for (size_t i = 0; i < size; ++i) { if (arr_F[i] < min) { min = arr_F[i]; min_index = i; } } return min_index; } void calculate_H(Edge *e, Vertex* t, float *arr_H) { arr_H[e->tail->index] = fabs(t->x - e->tail->x) + fabs(t->y - e->tail->y); } void relax(Edge* e, Vertex *t, float* arr_F, float *arr_H) { calculate_H(e, t, arr_H); if (arr_F[e->tail->index] > (e->head->distance + e->weight + arr_H[e->tail->index])) { e->tail->distance = e->head->distance + e->weight; e->tail->parent = e->head; arr_F[e->tail->index] = e->tail->distance + arr_H[e->tail->index]; } } void print_path(Edge **g, Vertex *s, Vertex *t, size_t index) { if (t == s) std::cout << s->index << " --> "; else if (t->parent == nullptr) std::cout << "No path between vertices."; else { print_path(g, s, t->parent, index); std::cout << t->index << ((t->index != index) ? " --> " : ""); } }
Riferimenti:
[1] Programming Game AI by Example - Buckland
[2] Grafi: Algoritmo di Dijkstra
[3] https://it.wikipedia.org/wiki/Geometria_del_taxi
[4] Ordinamento: Heap Sort
[5] Radice quadrata inversa veloce
Nessun commento:
Posta un commento