Dijkstraalgorithm和A-Star如何比较？
我正在研究马里奥人工智能竞赛中的人，他们中的一些人使用A *（A-Star）Pathingalgorithm构build了一些漂亮的马里奥机器人。
替代文字http://julian.togelius.com/mariocompetition2009/screen1.png
（ 马里奥A *机器人的video在行动 ）
我的问题是，A-Star与Dijkstra相比如何？ 看着他们，他们看起来很相似。
为什么有人会用另一个呢？ 特别是在游戏中的path？
Dijkstra是A *的特例（当启发式为零时）。
Dijkstraalgorithm：
它有一个成本函数，它是从源到每个节点的实际成本值： f(x)=g(x) 。
它只考虑实际成本，find从源到其他节点的最短path。
A *search：
它有两个成本函数。
-
g(x)：与Dijkstra相同。 到达节点x的实际成本。 -
h(x)：从节点x到目标节点的近似成本。 这是一个启发式function。 这个启发式function决不应该高估成本。 这意味着，从节点x到达目标节点的实际成本应大于或等于h(x)。 它被称为可接受的启发式。
每个节点的总成本由f(x)=g(x)+h(x)
如果看起来有希望，*search只展开一个节点。 它只着重于从当前节点到达目标节点，而不是到达每个其他节点。 如果启发函数是可接受的，则是最优的。
所以，如果你的启发函数能很好的逼近未来的成本，那么比起Dijkstra你将需要探索更less的节点。
以前的海报说过，再加上因为Dijkstra没有启发式，每一步都会以最小的代价挑选边缘，所以它往往会“覆盖”更多的graphics。 因为Dijkstra可能比A *更有用。 很好的例子是当你有几个候选目标节点，但你不知道哪一个是最接近的（在A *的情况下，你将不得不多次运行它：每个候选节点一次）。
Dijkstraalgorithm永远不会用于寻路。 如果你能想出一个体面的启发式（通常对于游戏来说很容易，特别是在2D世界中），使用A *是一件不容易的事情。 根据search空间的不同，迭代深化A *有时更可取，因为它使用较less的内存。
你可以考虑A * Dijkstra的指导版本。 意思是，而不是探索所有的节点，你会使用启发式来挑选一个方向。
更具体地说，如果你正在实现具有优先级队列的algorithm，那么你所访问的节点的优先级将是成本（以前的节点成本+到这里得到的成本）和启发式估计的函数到目标。 而在Dijkstra中，优先级只受节点实际成本的影响。 在任何一种情况下，停止标准都达到了目标。
Dijkstra是A *的特例。
Dijkstra发现从起始节点到所有其他节点的最低成本。 A *查找从起始节点到目标节点的最低成本。
Dijkstraalgorithm永远不会用于path查找。 使用A *可以提出一个体面的启发式。 取决于search空间，迭代A *是更可取的，因为它使用较less的内存。
Dijkstraalgorithm的代码是：
// AC / 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 *algorithm的代码是：
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:oG + oH) #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似乎效率会更低。
如果你看一下Astar的伪代码 ：
foreach y in neighbor_nodes(x) if y in closedset continue
而如果你看一看迪杰斯特拉的话 ：
for each neighbor v of u: alt := dist[u] + dist_between(u, v) ;
所以，重点是，Astar不会多次评估一个节点，
因为它认为一次查看节点就足够了
到它的启发式。
如果是OTOH，Dijkstra的algorithm不怕自纠
一个节点再次popup。
这应该使Astar更快，更适合寻路。
Dijkstra的algorithm肯定会find最短的path。 另一方面，A *取决于启发式。 出于这个原因，A *比Dijkstra的algorithm更快，如果你有一个很好的启发式algorithm，将会给出好的结果。
Dijkstra的algorithm绝对是完整和最优的，你总能find最短的path。 然而，由于主要用于检测多个目标节点，所以它往往需要更长的时间。
另一方面， A* search具有启发式价值，您可以定义这些价值以达到目标距离，例如曼哈顿距离目标的距离。 它可以是最佳的或完整的，这取决于启发式因素。 如果你有一个单一的目标节点，它肯定会更快。
在A *中，为每个节点检查其传出连接。
对于每个新节点，计算迄今为止的最低成本（csf），具体取决于到该节点的连接的权重以及必须达到前一个节点的成本。
另外，您可以估算从新节点到目标节点的成本，并将其添加到csf中。 你现在有估计的总成本（等）。 （etc = csf +到目标的估计距离）接下来从新节点中select最低的节点
和以前一样，直到其中一个新节点成为目标。
迪克斯特拉的作品几乎是一样的。 除了估计的到目标的距离总是为0，algorithm首先停止时，目标不仅是新的节点之一 ，而且还有最低的csf。
A *通常比dijstra快，尽pipe情况并非总是如此。 在video游戏中，你经常预先“足够靠近游戏”的方法。 因此，从A *到“足够接近”的最佳path通常就足够了。
