如何Dijkstra算法和A-星比较？(How does Dijkstra's Algori

我一直在寻找什么样的家伙马里奥AI比赛一直在做，其中一些已建成利用A *（A-星）Pathing的算法一些漂亮整洁的马里奥机器人。

（ 马里奥视频A *博特在行动 ）

我的问题是，如何做一个明星与Dijkstra算法比较？ 纵观他们，他们似乎相似。

为什么要使用一个比其他？ 尤其是在游戏寻路的范围内？

Answer 1:

Dijkstra算法是A *（当启发式为零）的特殊情况。

Answer 2:

Dijkstra算法：

它有一个成本函数，该函数是从源到每个节点实际成本值： f(x)=g(x)
它通过只考虑实际成本找到从源到所有其他节点的最短路径。

A *搜索：

它有两个成本函数。

1. g(x)同的Dijkstra。 实际成本达到一个节点x 。
2. h(x)近似成本从节点x到节点目标。 它是一种启发式的功能。 这种启发式功能不应该高估成本。 这意味着，实际成本达到从节点目标节点x应大于或等于h(x) 这就是所谓的启发的。

每个节点的总成本由下式计算f(x)=g(x)+h(x)

A *搜索，只有当它似乎有希望展开一个节点。 它只着眼于从当前节点到达目标节点，则不能达到所有其他节点。 这是最佳的，如果启发式功能是可以受理的。

所以，如果你的启发式功能是很好的近似未来的成本，比你需要探索少了很多节点比Dijkstra算法。

Answer 3:

什么以前的海报说，再加上因为Dijkstra算法有没有启发，并在每一步挑选具有最小的成本边缘也容易“捂”你的图形多。 正因为如此Dijkstra算法可能比A *更有用。 很好的例子就是当你有几个候选目标节点，但你不知道哪一个才是最接近（你将不得不多次运行A *的情况：每个候选节点一次）。

Answer 4:

Dijkstra算法将永远不会被用于寻路。 使用A *是想都不用想，如果你能拿出一个像样的启发式（通常是容易的游戏，尤其是在2D世界）。 根据不同的搜索空间，迭代深化A *有时是可取的，因为它使用较少的内存。

Answer 5:

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)

Answer 6:

Dijkstra算法找到从起始节点到所有其他人的最低成本。 A *发现从起始节点到目标节点的最低成本。

因此，它似乎是Dijkstra算法将是效率较低，当你需要的是从一个节点到另一个节点的最小距离。

Answer 7:

你可以考虑A *的Dijkstra的引导版本。 含义，而不是探索所有节点，您将使用启发式选择一个方向。

说得更加具体，如果你有那么优先级队列你访问将是成本的函数（以前的节点成本+费用到这里），并从这里启发式估计节点的优先级执行的算法的目标。 而在Dijkstra算法，优先级仅由实际成本节点的影响。 在这两种情况下，停止基准达到目标。

Answer 8:

如果你看一下伪代码为爱仕达：

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) ;

所以，问题是，亚士都不会评价一个节点一次以上，
因为它认为，在一个节点看一次就足够了，因为
它的启发。

OTOH，Dijkstra算法是不避讳修正自身的，万一
一个节点再次弹出。

这应该路径寻找更快，更适合做爱仕达。

Answer 9:

Dijkstra算法确实找到最短路径。 在另一方面A *依赖于启发式。 为此A *比Dijkstra算法更快，会得到好的结果，如果你有一个很好的启发。

Answer 10:

Dijkstra算法肯定是完整的和最佳的，你总能找到最短路径。 但是它往往需要更长的时间，因为它主要是用来探测多个目标节点。

A* search ，另一方面与启发式值，你可以定义达到自己的目标更近，如朝目标曼哈顿距离很重要。 它可以是最佳的或完全依赖于启发式的因素。 这绝对是更快，如果你有一个单一的目标节点。

Answer 11:

在A *，为每个节点您检查他们的传出连接。
对于每一个新的节点，则取决于连接到这个节点，你必须达到前一个节点的成本的权重计算出成本最低，到目前为止（CSF）。
此外，您估计来自新节点到目标节点的成本，这增加了CSF。 你现在有预计总费用（ETC）。 （等等= CSF +估计的距离来定位）接下来，从新节点选择一个具有最低等
一样做，直到新的节点之一将是目标之前。

Dijkstra算法的工作原理几乎相同。 除估计距离目标始终为0，而当目标不仅是新的一个节点 ，也是一个具有最低CSF算法首先停止。

A *通常比dijstra更快，虽然这并不总是如此。 在视频游戏中，你经常prefare的“足够接近的一场比赛”的做法。 因此，从A *已经足够“足够接近”最优路径。

文章来源: How does Dijkstra's Algorithm and A-Star compare?