Dijkstra의 알고리즘과 A-Star는 어떻게 비교됩니까?
https://stackoverflow.com/questions/1332466
-
19-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian문제
나는 사람들이 무엇을보고 있었다 마리오 AI 경쟁 하고 있었고 그들 중 일부는 A* (A-Star) Pathing 알고리즘을 사용하여 꽤 깔끔한 마리오 봇을 만들었습니다.
내 질문은 A-Star가 Dijkstra와 어떻게 비교됩니까? 그들을 바라보며, 그들은 비슷해 보입니다.
왜 누군가가 다른 사람을 사용합니까? 특히 게임에서의 경주의 맥락에서?
해결책
dijkstra는 a*의 특별한 경우입니다 (휴리스틱이 0 일 때).
다른 팁
dijkstra :
소스에서 각 노드로의 실제 비용 값 인 하나의 비용 기능이 있습니다. f(x)=g(x).
실제 비용 만 고려하여 소스에서 다른 모든 노드로 가장 짧은 경로를 찾습니다.
검색:
두 가지 비용 기능이 있습니다.
g(x): dijkstra와 동일합니다. 노드에 도달하는 데 필요한 실제 비용x.h(x): 노드의 대략적인 비용x목표 노드로. 휴리스틱 기능입니다. 이 휴리스틱 기능은 비용을 과대 평가하지 않아야합니다. 즉, 노드에서 목표 노드에 도달하는 데 필요한 실제 비용은x보다 크거나 동일해야합니다h(x). 허용 휴리스틱이라고합니다.
각 노드의 총 비용은 계산됩니다 f(x)=g(x)+h(x)
A* 검색은 유망한 것처럼 보이는 경우 노드 만 확장합니다. 다른 모든 노드에 도달하지 않도록 현재 노드에서 목표 노드에 도달하는 데 초점을 맞 춥니 다. 휴리스틱 기능이 허용되는 경우 최적입니다.
따라서 휴리스틱 기능이 미래 비용을 근사화하는 데 좋은 경우 Dijkstra보다 훨씬 적은 노드를 탐색해야합니다.
이전 포스터가 말한 내용과 Dijkstra는 휴리스틱이없고 각 단계에서 가장 적은 비용으로 가장자리를 선택하면 그래프를 더 "덮는"경향이 있습니다. 그 때문에 dijkstra는 A*보다 더 유용 할 수 있습니다. 좋은 예는 여러 후보 대상 노드가있을 때 가장 가까운 후보 대상 노드가있을 때입니다. 어느 것이 가장 가까운 지 알 수 없습니다 (* 경우 각 후보 노드에 대해 여러 번 실행해야합니다).
Dijkstra의 알고리즘은 경로 찾기에 사용되지 않습니다. 괜찮은 휴리스틱 (일반적으로 게임, 특히 2D 세계에서는 쉽게 게임, 특히 2D 세계에서 쉽게)을 만들 수 있다면 A*를 사용하는 것은 쉬운 일이 아닙니다. 검색 공간에 따라 반복 심화 a*가 메모리를 덜 사용하기 때문에 때때로 바람직합니다.
dijkstra는 a*의 특별한 경우입니다.
Dijkstra는 시작 노드에서 다른 모든 것까지 최소 비용을 찾습니다. A*는 시작 노드에서 목표 노드까지 최소 비용을 찾습니다.
Dijkstra의 알고리즘은 경로 찾기에 사용되지 않습니다. * 하나를 사용하면 괜찮은 휴리스틱을 만들 수 있습니다. 검색 공간에 따라 메모리를 적게 사용하기 때문에 반복 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;
}
* 알고리즘 코드는 다음과 같습니다.
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의 가이드 버전을 고려할 수 있습니다. 즉, 모든 노드를 탐색하는 대신 휴리스틱을 사용하여 방향을 선택합니다.
보다 구체적으로 말하면 우선 순위 대기열이있는 알고리즘을 구현하는 경우 방문하는 노드의 우선 순위는 비용의 함수 (이전 노드 비용 + 여기에 도착하는 데 드는 비용) 및 여기에서 휴리스틱 추정치가 발생합니다. 목표에. DIJKSTRA에서는 우선 순위가 실제 노드 비용에 의해서만 영향을받습니다. 두 경우 모두 정지 기준이 목표에 도달하고 있습니다.
Dijkstra는 시작 노드에서 다른 모든 것까지 최소 비용을 찾습니다. A*는 시작 노드에서 목표 노드까지 최소 비용을 찾습니다.
따라서 한 노드에서 다른 노드까지 최소 거리가 필요한 경우 Dijkstra가 덜 효율적일 것 같습니다.
당신이 보면 psuedocode Astar의 경우 :
foreach y in neighbor_nodes(x)
if y in closedset
continue
반면에, 당신이 똑같이 보면 dijkstra :
for each neighbor v of u:
alt := dist[u] + dist_between(u, v) ;
따라서 요점은 Astar가 노드를 두 번 이상 평가하지 않을 것입니다.
노드를 한 번 보는 것이 충분하다고 믿기 때문에
휴리스틱에.
Otoh, Dijkstra의 알고리즘은 경우를 대비하여 스스로를 수정하는 것을 부끄러워하지 않습니다.
노드가 다시 나타납니다.
어느 ~해야 한다 아스타르를 더 빠르고 경로 찾기에 더 적합하게 만드십시오.
Dijkstra의 알고리즘은 가장 짧은 경로를 확실히 찾습니다. 반면에*는 휴리스틱에 달려 있습니다. 이러한 이유로 A*는 Dijkstra 알고리즘보다 빠르며 휴리스틱이 좋은 경우 좋은 결과를 제공합니다.
Dijkstra의 알고리즘은 항상 가장 짧은 경로를 찾을 수 있도록 완전하고 최적입니다. 그러나 주로 여러 목표 노드를 감지하는 데 사용되기 때문에 더 오래 걸리는 경향이 있습니다.
A* search 반면에 맨해튼의 목표를 향한 맨해튼의 거리와 같이 목표에 더 가까워 지도록 정의 할 수있는 휴리스틱 가치가 중요합니다. 휴리스틱 요인에 따라 최적이거나 완전 할 수 있습니다. 단일 골 노드가 있으면 확실히 빠릅니다.
A*에서 각 노드에 대해 나가는 연결을 확인합니다.
각각의 새 노드에 대해이 노드 연결의 가중치와 이전 노드에 도달 해야하는 비용에 따라 지금까지 가장 낮은 비용 (CSF)을 계산합니다.
또한 새 노드에서 대상 노드로의 비용을 추정하고이를 CSF에 추가합니다. 이제 총 비용 (등)이 예상됩니다. (etc = csf + target까지의 추정 거리) 다음에 새 노드에서 선택한 것 중 가장 낮은 노드 등을 선택합니다.
하나가 될 때까지 이전과 동일하게 수행하십시오 새로운 노드 목표가 될 것입니다.
Dijkstra는 거의 동일하게 작동합니다. 대상까지의 추정 거리는 항상 0이고, 대상이 하나만이 아니라면 먼저 알고리즘이 중지됩니다. 새로운 노드, 또한 CSF가 가장 낮은 것도 있습니다.
A*는 일반적으로 Dijstra보다 빠르지 만 항상 그렇지는 않습니다. 비디오 게임에서는 종종 "게임에 충분히 가까운"접근 방식을 조정합니다. 그러므로*에서 "충분히 가까운"최적의 경로는 일반적으로 충분합니다.
