Jak wypada porównanie algorytmu Dijkstry i A-Star?

Patrzyłem na to, co robią zawodnicy Mario AI Competition , a niektórzy z nich zbudowali całkiem zgrabne boty Mario, wykorzystując algorytm ścieżki A * (A-Star).

( Wideo Mario A * Bot w akcji )

Moje pytanie brzmi: jak wypada A-Star w porównaniu z Dijkstrą? Patrząc na nie, wydają się podobne.

Dlaczego ktoś miałby używać jednego nad drugim? Zwłaszcza w kontekście pathingu w grach?

Dijkstra to szczególny przypadek dla A * (gdy heurystyka wynosi zero).

Dijkstra:

Posiada jedną funkcję kosztów, co jest rzeczywistą wartość kosztów od źródła do każdego węzła: f(x)=g(x).
Znajduje najkrótszą ścieżkę od źródła do każdego innego węzła, biorąc pod uwagę tylko rzeczywisty koszt.

Wyszukiwanie:

Ma dwie funkcje kosztowe.

1. g(x): tak samo jak Dijkstra. Rzeczywisty koszt dotarcia do węzła x.
2. h(x): przybliżony koszt od węzła xdo węzła celu. Jest to funkcja heurystyczna. Ta funkcja heurystyczna nigdy nie powinna przeceniać kosztów. Oznacza to, że rzeczywisty koszt dotarcia do węzła docelowego z węzła xpowinien być większy lub równy h(x). Nazywa się to dopuszczalną heurystyką.

Całkowity koszt każdego węzła jest obliczany według f(x)=g(x)+h(x)

Wyszukiwanie * rozszerza węzeł tylko wtedy, gdy wydaje się obiecujący. Koncentruje się tylko na dotarciu do węzła docelowego z bieżącego węzła, a nie na dotarciu do wszystkich innych węzłów. Jest optymalne, jeśli dopuszczalna jest funkcja heurystyczna.

Więc jeśli twoja funkcja heurystyczna jest dobra do oszacowania przyszłego kosztu, będziesz musiał zbadać o wiele mniej węzłów niż Dijkstra.

To, co powiedział poprzedni plakat, a ponadto ponieważ Dijkstra nie ma heurystyki i na każdym kroku wybiera krawędzie przy najmniejszym koszcie, ma tendencję do „zakrywania” większej części wykresu. Z tego powodu Dijkstra może być bardziej przydatny niż A *. Dobrym przykładem jest sytuacja, gdy masz kilka kandydujących węzłów docelowych, ale nie wiesz, który z nich jest najbliższy (w przypadku A * musiałbyś uruchamiać go wiele razy: raz dla każdego kandydującego węzła).

Algorytm Dijkstry nigdy nie zostałby użyty do odnajdywania ścieżki. Używanie A * nie wymaga myślenia, jeśli możesz wymyślić przyzwoitą heurystykę (zwykle łatwa w grach, szczególnie w światach 2D). W zależności od przestrzeni wyszukiwania, czasami preferowane jest Iteracyjne pogłębianie A *, ponieważ zużywa mniej pamięci.

Dijkstra to szczególny przypadek dla A *.

Dijkstra znajduje minimalne koszty od węzła początkowego do wszystkich pozostałych. A * znajduje minimalny koszt od węzła początkowego do węzła docelowego.

Algorytm Dijkstry nigdy nie zostałby użyty do znalezienia ścieżki. Używając A * można wymyślić przyzwoitą heurystykę. W zależności od przestrzeni wyszukiwania iteracyjne A * jest preferowane, ponieważ zużywa mniej pamięci.

Kod algorytmu Dijkstry to:

// A C / C++ program for Dijkstra's single source shortest path algorithm.
// The program is for adjacency matrix representation of the graph

#include <stdio.h>
#include <limits.h>

// Number of vertices in the graph
#define V 9

// A utility function to find the vertex with minimum distance value, from
// the set of vertices not yet included in shortest path tree
int minDistance(int dist[], bool sptSet[])
{
 // Initialize min value
 int min = INT_MAX, min_index;

  for (int v = 0; v < V; v++)
   if (sptSet[v] == false && dist[v] <= min)
     min = dist[v], min_index = v;

   return min_index;
}

 int printSolution(int dist[], int n)
 {
  printf("Vertex   Distance from Source\n");
  for (int i = 0; i < V; i++)
     printf("%d \t\t %d\n", i, dist[i]);
  }

void dijkstra(int graph[V][V], int src)
{
 int dist[V];     // The output array.  dist[i] will hold the shortest
                  // distance from src to i

 bool sptSet[V]; // sptSet[i] will true if vertex i is included in shortest
                 // path tree or shortest distance from src to i is finalized

 // Initialize all distances as INFINITE and stpSet[] as false
 for (int i = 0; i < V; i++)
    dist[i] = INT_MAX, sptSet[i] = false;

 // Distance of source vertex from itself is always 0
 dist[src] = 0;

 // Find shortest path for all vertices
 for (int count = 0; count < V-1; count++)
 {
   // Pick the minimum distance vertex from the set of vertices not
   // yet processed. u is always equal to src in first iteration.
   int u = minDistance(dist, sptSet);

   // Mark the picked vertex as processed
   sptSet[u] = true;

   // Update dist value of the adjacent vertices of the picked vertex.
   for (int v = 0; v < V; v++)

     // Update dist[v] only if is not in sptSet, there is an edge from 
     // u to v, and total weight of path from src to  v through u is 
     // smaller than current value of dist[v]
     if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX 
                                   && dist[u]+graph[u][v] < dist[v])
        dist[v] = dist[u] + graph[u][v];
 }

 // print the constructed distance array
 printSolution(dist, V);
 }

// driver program to test above function
int main()
 {
 /* Let us create the example graph discussed above */
 int graph[V][V] = {{0, 4, 0, 0, 0, 0, 0, 8, 0},
                  {4, 0, 8, 0, 0, 0, 0, 11, 0},
                  {0, 8, 0, 7, 0, 4, 0, 0, 2},
                  {0, 0, 7, 0, 9, 14, 0, 0, 0},
                  {0, 0, 0, 9, 0, 10, 0, 0, 0},
                  {0, 0, 4, 14, 10, 0, 2, 0, 0},
                  {0, 0, 0, 0, 0, 2, 0, 1, 6},
                  {8, 11, 0, 0, 0, 0, 1, 0, 7},
                  {0, 0, 2, 0, 0, 0, 6, 7, 0}
                 };

dijkstra(graph, 0);

return 0;
}

Kod algorytmu A * to:

class Node:
def __init__(self,value,point):
    self.value = value
    self.point = point
    self.parent = None
    self.H = 0
    self.G = 0
def move_cost(self,other):
    return 0 if self.value == '.' else 1

def children(point,grid):
x,y = point.point
links = [grid[d[0]][d[1]] for d in [(x-1, y),(x,y - 1),(x,y + 1),(x+1,y)]]
return [link for link in links if link.value != '%']
def manhattan(point,point2):
return abs(point.point[0] - point2.point[0]) + abs(point.point[1]-point2.point[0])
def aStar(start, goal, grid):
#The open and closed sets
openset = set()
closedset = set()
#Current point is the starting point
current = start
#Add the starting point to the open set
openset.add(current)
#While the open set is not empty
while openset:
    #Find the item in the open set with the lowest G + H score
    current = min(openset, key=lambda o:o.G + o.H)
    #If it is the item we want, retrace the path and return it
    if current == goal:
        path = []
        while current.parent:
            path.append(current)
            current = current.parent
        path.append(current)
        return path[::-1]
    #Remove the item from the open set
    openset.remove(current)
    #Add it to the closed set
    closedset.add(current)
    #Loop through the node's children/siblings
    for node in children(current,grid):
        #If it is already in the closed set, skip it
        if node in closedset:
            continue
        #Otherwise if it is already in the open set
        if node in openset:
            #Check if we beat the G score 
            new_g = current.G + current.move_cost(node)
            if node.G > new_g:
                #If so, update the node to have a new parent
                node.G = new_g
                node.parent = current
        else:
            #If it isn't in the open set, calculate the G and H score for the node
            node.G = current.G + current.move_cost(node)
            node.H = manhattan(node, goal)
            #Set the parent to our current item
            node.parent = current
            #Add it to the set
            openset.add(node)
    #Throw an exception if there is no path
    raise ValueError('No Path Found')
def next_move(pacman,food,grid):
#Convert all the points to instances of Node
for x in xrange(len(grid)):
    for y in xrange(len(grid[x])):
        grid[x][y] = Node(grid[x][y],(x,y))
#Get the path
path = aStar(grid[pacman[0]][pacman[1]],grid[food[0]][food[1]],grid)
#Output the path
print len(path) - 1
for node in path:
    x, y = node.point
    print x, y
pacman_x, pacman_y = [ int(i) for i in raw_input().strip().split() ]
food_x, food_y = [ int(i) for i in raw_input().strip().split() ]
x,y = [ int(i) for i in raw_input().strip().split() ]

grid = []
for i in xrange(0, x):
grid.append(list(raw_input().strip()))

next_move((pacman_x, pacman_y),(food_x, food_y), grid)

Dijkstra znajduje minimalne koszty od węzła początkowego do wszystkich pozostałych. A * znajduje minimalny koszt od węzła początkowego do węzła docelowego.

Dlatego wydawałoby się, że Dijkstra byłaby mniej wydajna, gdy wystarczyłaby minimalna odległość od jednego węzła do drugiego.

Możesz uznać A * za wersję Dijkstry z przewodnikiem. Oznacza to, że zamiast badać wszystkie węzły, użyjesz heurystyki, aby wybrać kierunek.

Mówiąc bardziej konkretnie, jeśli implementujesz algorytmy z kolejką priorytetów, wówczas priorytet odwiedzanego węzła będzie funkcją kosztu (koszt poprzednich węzłów + koszt uzyskania tutaj) i oszacowania heurystycznego z tego miejsca do celu. Podczas gdy w Dijkstra na priorytet ma wpływ tylko rzeczywisty koszt węzłów. W obu przypadkach kryterium zatrzymania jest osiągnięcie celu.

Algorytm Dijkstry zdecydowanie znajduje najkrótszą ścieżkę. Z drugiej strony A * zależy od heurystyki. Z tego powodu A * jest szybszy niż algorytm Dijkstry i da dobre wyniki, jeśli masz dobrą heurystykę.

Jeśli spojrzysz na psuedokod dla Astar:

foreach y in neighbor_nodes(x)
             if y in closedset
                 continue

Natomiast jeśli spojrzeć na to samo dla Dijkstry :

for each neighbor v of u:         
             alt := dist[u] + dist_between(u, v) ;

Chodzi więc o to, że Astar nie oceni węzła więcej niż jeden raz,
ponieważ uważa, że ​​wystarczy jedno spojrzenie na węzeł, ze względu
na jego heurystykę.

OTOH, algorytm Dijkstry nie boi się sam korygować, w przypadku
ponownego pojawienia się węzła.

Co powinno sprawić, że Astar będzie szybszy i bardziej odpowiedni do znajdowania ścieżki.

W A *, dla każdego węzła sprawdzasz połączenia wychodzące pod kątem ich.
Dla każdego nowego węzła obliczasz najniższy do tej pory koszt (csf) w zależności od wagi połączeń do tego węzła i kosztów, jakie musiałeś uzyskać, aby dotrzeć do poprzedniego węzła.
Dodatkowo szacujesz koszt od nowego węzła do węzła docelowego i dodajesz go do csf. Masz teraz szacunkowy koszt całkowity (itp.). (etc = csf + szacowana odległość do celu) Następnie wybierasz z nowych węzłów ten z najniższym itd.
Rób to samo co wcześniej, aż do jednego z nowych węzłów będzie celem.

Dijkstra działa prawie tak samo. Tyle że szacowana odległość do celu wynosi zawsze 0, a algorytm zatrzymuje się najpierw, gdy celem nie jest tylko jeden z nowych węzłów , ale także ten o najniższym csf.

* Jest zwykle szybsze niż dijstra, chociaż nie zawsze tak będzie. W grach wideo często preferujesz podejście „wystarczająco blisko do gry”. Dlatego „dostatecznie blisko” optymalna ścieżka z A * zwykle wystarcza.

Algorytm Dijkstry jest zdecydowanie kompletny i optymalny, aby zawsze znaleźć najkrótszą ścieżkę. Jednak zwykle trwa to dłużej, ponieważ jest używany głównie do wykrywania wielu węzłów docelowych.

A* searchz drugiej strony ma znaczenie w przypadku wartości heurystycznych, które można zdefiniować, aby zbliżyć się do celu, takich jak odległość między Manhattanem a celem. Może być optymalny lub kompletny, co zależy od czynników heurystycznych. jest zdecydowanie szybszy, jeśli masz pojedynczy węzeł celu.