Jak porównuje się algorytm Dijkstry i A-Star?

Dijkstra:

Ma jedną funkcję kosztów, która jest rzeczywistą wartością 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.

A* Szukaj:

Ma dwie funkcje kosztów.

1. g(x): to samo co Dijkstra. Rzeczywisty koszt dotarcia do węzła x.
2. h(x): przybliżony koszt od węzła x do węzła docelowego. Jest to funkcja heurystyczna. Ta funkcja heurystyczna nigdy nie powinna przecenić koszty. Oznacza to, że rzeczywisty koszt osiągnięcia węzła docelowego z węzła x powinien być większy lub równy h(x). Nazywa się ją dopuszczalną heurystyką.

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

Wyszukiwanie* rozszerza węzeł tylko wtedy, gdy wydaje się obiecujące. Skupia się tylko na dotarciu do węzła docelowego z bieżącego węzła, a nie na dotarciu do każdego innego węzła. Jest optymalna, jeśli funkcja heurystyczna jest dopuszczalna.

Więc jeśli funkcja heurystyczna jest dobre przybliżenie przyszłych kosztów, niż trzeba będzie zbadać o wiele mniej węzłów niż Dijkstra.

Co powiedział poprzedni plakat, dodatkowo ponieważ Dijkstra nie ma heurystyki i na każdym kroku wybiera krawędzie przy najmniejszym koszcie ma tendencję do "pokrywania" większej części wykresu. Z tego powodu Dijkstra może być bardziej przydatna niż*. Dobrym przykładem jest sytuacja, gdy masz kilka węzłów docelowych kandydata, ale nie wiesz, który z nich jest najbliższy (w przypadku* musisz uruchomić go kilka razy: raz dla każdego węzła kandydata).

Algorytm Dijkstry nigdy nie zostałby użyty do wyszukiwania ścieżek. Korzystanie z* jest nie do pomyślenia, jeśli można wymyślić przyzwoitą heurystykę (zwykle łatwe w grach, szczególnie w światach 2D). W zależności od przestrzeni wyszukiwania, iteracyjne pogłębienie A* jest czasami preferowane, ponieważ zużywa mniej pamięci.

Dijkstra jest szczególnym przypadkiem*.

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

Algorytm Dijkstry nigdy nie zostałby użyty do znalezienia ścieżki. Używając* można wymyślić przyzwoitą heurystykę. W zależności od miejsca 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* jest:

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)

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

Mówiąc dokładniej, jeśli implementujesz algorytmy z kolejką priorytetów, priorytet odwiedzanego węzła będzie funkcją kosztu (koszt poprzednich węzłów + koszt, aby tu dotrzeć) i heurystycznego oszacowania stąd do celu. Podczas gdy w Dijkstrze, na priorytet ma wpływ tylko rzeczywisty koszt węzłów. W obu przypadkach kryterium zatrzymania jest osiągnięcie celu.

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

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

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

Jeśli spojrzysz na psuedocode dla Astar:

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

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

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

OTOH, algorytm Dijkstry nie wstydzi się poprawiać samego siebie, w przypadku
ponownie pojawia się węzeł.

Które powinny sprawić, że Astar będzie szybszy i bardziej odpowiedni do znalezienia ścieżki.

W*, dla każdego węzła sprawdzasz połączenia wychodzące pod kątem ich .
Dla każdego nowego węzła oblicza się najniższy dotychczas koszt (csf) w zależności od wagi połączeń do tego węzła i kosztów, które trzeba było osiągnąć poprzedni węzeł.
Dodatkowo szacujesz koszt od nowego węzła do węzła docelowego i dodajesz go do csf. Masz teraz szacowany całkowity koszt (itp.). (etc = csf + szacowana odległość do celu) Następnie wybieramy z nowych węzłów ten z NAJNIŻSZYM itd.
Zrób to samo, dopóki jeden z nowych węzłów nie będzie celem.

Dijkstra działa prawie tak samo. Z tym wyjątkiem, że szacowana odległość do celu jest zawsze równa 0, a algorytm najpierw zatrzymuje się, gdy cel jest nie tylko jednym z nowych węzłów, ale także tym z NAJNIŻSZYM csf.

A * jest zwykle szybszy niż dijstra, choć nie zawsze tak będzie. W grach wideo często preferujesz podejście "wystarczająco blisko dla gry". Dlatego " blisko wystarczy " optymalna ścieżka Z* zwykle wystarcza.

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

A* search z drugiej strony chodzi o wartości heurystyczne, które można zdefiniować, aby osiągnąć cel bliżej, takie jak odległość Manhattanu do celu. Może być optymalny lub kompletny, co zależy od czynników heurystycznych. jest zdecydowanie szybszy, jeśli masz pojedynczy węzeł bramkowy.