Dijkstra의 알고리즘과 A- 스타는 어떻게 비교됩니까?

Dijkstra의 알고리즘과 A- 스타는 어떻게 비교됩니까?

---

나는 마리오 AI 경쟁 의 사람들이 무엇을하고 있었는지보고 있었고, 그들 중 일부는 A * (A-Star) Pathing Algorithm을 사용하여 아주 깔끔한 마리오 봇을 만들었습니다.

( 마리오 A * 봇 작동 비디오 )

제 질문은 A-Star가 Dijkstra와 어떻게 비교됩니까? 그것들을 살펴보면 비슷해 보입니다.

왜 누군가가 다른 것을 사용합니까? 특히 게임에서의 경로와 관련하여?

---

Dijkstra는 A *의 특별한 경우입니다 (휴리스틱이 0 인 경우).

---

다이크 스트라 :

여기에는 소스에서 각 노드까지의 실제 비용 값인 하나의 비용 함수가 f(x)=g(x)있습니다.
실제 비용 만 고려하여 소스에서 다른 모든 노드로의 최단 경로를 찾습니다.

검색:

두 가지 비용 함수가 있습니다.

1. g(x): Dijkstra와 동일 노드에 도달하는 실제 비용 x.
2. h(x): 노드 x에서 목표 노드 까지의 대략적인 비용 . 휴리스틱 함수입니다. 이 휴리스틱 함수는 비용을 과대 평가해서는 안됩니다. 즉, 노드에서 목표 노드에 도달하는 실제 비용 x은보다 크거나 같아야 h(x)합니다. 허용되는 휴리스틱이라고합니다.

각 노드의 총 비용은 f(x)=g(x)+h(x)

A * 검색은 유망한 것으로 보이는 경우에만 노드를 확장합니다. 다른 모든 노드에 도달하지 않고 현재 노드에서 목표 노드에 도달하는 데에만 초점을 맞 춥니 다. 휴리스틱 기능이 허용되는 경우 최적입니다.

따라서 휴리스틱 함수가 미래 비용을 근사하기에 좋은 경우 Dijkstra보다 훨씬 적은 수의 노드를 탐색해야합니다.

---

Dijkstra는 휴리스틱이 없으며 각 단계에서 가장 작은 비용으로 가장자리를 선택하기 때문에 이전 포스터의 내용과 함께 더 많은 그래프를 "덮는"경향이 있습니다. Dijkstra는 A *보다 유용 할 수 있습니다. 좋은 예는 여러 후보 대상 노드가 있지만 어느 것이 가장 가까운 지 알 수 없습니다 (A *의 경우 여러 번 실행해야합니다 (각 후보 노드마다 한 번씩)).

---

Dijkstra의 알고리즘은 경로 찾기에 절대 사용되지 않습니다. 괜찮은 휴리스틱 (일반적으로 게임, 특히 2D 세계에서 쉬움)을 생각해 낼 수 있다면 A *를 사용하는 것은 쉬운 일이 아닙니다. 검색 공간에 따라 반복 심화 A *가 적은 메모리를 사용하기 때문에 선호되는 경우가 있습니다.

---

Dijkstra는 A *의 특별한 경우입니다.

Dijkstra는 시작 노드에서 다른 모든 노드까지의 최소 비용을 찾습니다. A *는 시작 노드에서 목표 노드까지의 최소 비용을 찾습니다.

Dijkstra의 알고리즘은 경로 찾기에 사용되지 않습니다. A *를 사용하면 괜찮은 휴리스틱을 얻을 수 있습니다. 검색 공간에 따라 반복적 인 A *가 더 적은 메모리를 사용하므로 바람직합니다.

Dijkstra의 알고리즘 코드는 다음과 같습니다.

// 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;
}

A * 알고리즘의 코드는 다음과 같습니다.

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는 시작 노드에서 다른 모든 노드까지의 최소 비용을 찾습니다. A *는 시작 노드에서 목표 노드까지의 최소 비용을 찾습니다.

따라서 Dijkstra는 한 노드에서 다른 노드까지의 최소 거리 만 있으면 효율성이 떨어질 것입니다.

---

A *를 Dijkstra의 안내 버전으로 고려할 수 있습니다. 즉, 모든 노드를 탐색하는 대신 휴리스틱을 사용하여 방향을 선택합니다.

To put it more concretely, if you're implementing the algorithms with a priority queue then the priority of the node you're visiting will be a function of the cost (previous nodes cost + cost to get here) and the heuristic estimate from here to the goal. While in Dijkstra, the priority is only influenced by the actual cost to nodes. In either case, the stop criterion is reaching the goal.

---

If you look at the psuedocode for Astar :

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

Whereas, if you look at the same for Dijkstra :

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

So, the point is, Astar will not evaluate a node more than once,
since it believes that looking at a node once is sufficient, due
to its heuristics.

OTOH, Dijkstra's algorithm isn't shy of correcting itself, in case
a node pops up again.

Which should make Astar faster and more suitable for path finding.

---

Dijkstra's algorithm finds the shortest path definitely. On the other hand A* depends on the heuristic. For this reason A* is faster than Dijkstra's algorithm and will give good results if you have a good heuristic.

---

Dijkstra's algorithm is definitely complete and optimal that you will always find the shortest path. However it tends to take longer since it is used mainly to detect multiple goal nodes.

A* search on the other hand matters with heuristic values, which you can define to reach your goal nearer, such as manhattan distance towards goal. It can be either optimal or complete which depends on heuristic factors. it is definitely faster if you have a single goal node.

---

In A*, for each node you check the outgoing connections for their .
For each new node you calculate the lowest cost so far (csf) depending on the weights of the connections to this node and the costs you had to reach the previous node.
Additionally you estimate the cost from the new node to the target node and add this to the csf. You now have the estimated total cost (etc). (etc = csf + estimated distance to target) Next you choose from the new nodes the one with the lowest etc.
Do the same as before until one of the new nodes will be the target.

Dijkstra works almost the same. Except that the estimated distance to target is always 0, and the algorithm first stops when the target is not only one of the new nodes, but also the one with the lowest csf.

A *는 일반적으로 dijstra보다 빠르지 만 항상 그런 것은 아닙니다. 비디오 게임에서는 종종 "게임에 충분히 근접한"접근 방식을 사용합니다. 따라서 A *에서 "충분히 근접한"최적 경로로 충분합니다.

참고 URL : https://stackoverflow.com/questions/1332466/how-does-dijkstras-algorithm-and-a-star-compare