Dijkstra的算法和A-Star如何比较？

Question

我在看马里奥人工智能大赛中的人一直在做什么,其中一些人利用A*(A-Star)路径算法构建了一些漂亮的马里奥机器人.

替代文字http://julian.togelius.com/mariocompetition2009/screen1.png
(马里奥·博特在行动视频)

我的问题是,A-Star与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的算法永远不会用于寻路.如果你能想出一个不错的启发式(通常很容易用于游戏,特别是在2D世界中),使用A*是不费脑子的.根据搜索空间的不同,Iterative Deepening A*有时更可取,因为它使用的内存更少.

Answer 5

Dijkstra是A*的一个特例.

Dijkstra找到从起始节点到所有其他节点的最低成本.A*查找从起始节点到目标节点的最低成本.

Dijkstra的算法永远不会用于路径寻找.使用A*one可以提出一个不错的启发式算法.根据搜索空间,迭代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

\n

BFS 和 Dijkstra\xe2\x80\x99s 算法彼此非常相似；它们都是 A* 算法的特例。

\n

A* 算法不仅更通用，而且更通用。在某些情况下，它提高了 Dijkstra\xe2\x80\x99s 算法的性能，但这并不总是如此；\n一般情况下，Dijkstra\xe2\x80\x99s 算法渐近与 A* 一样快。

\n

\n

Dijkstra 算法有 3 个参数。如果您曾经解决过网络延迟时间问题：

\n

class Solution:\n    def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:\n

\n

A* 方法有额外的 2 个参数：

\n

 function aStar(graph, start, isGoal, distance, heuristic)\n        queue \xe2\x86\x90 new PriorityQueue()\n        queue.insert(start, 0)\n\n        # hash table to keep track of the distance of each vertex from vertex "start", \n        #that is, the sum of the weight of edges that needs to be traversed to get from vertex start to each other vertex. \n        # Initializes these distances to infinity for all vertices but vertex start .\n        distances[v] \xe2\x86\x90 inf (\xe2\x88\x80 v \xce\xb5 graph | v <> start)\n      \n       # hash table for the f-score of a vertex, \n       # capturing the estimated cost to be sustained to reach the goal from start in a path passing through a certain vertex. Initializes these values to infinity for all vertices but vertex "start".\n        fScore[v] \xe2\x86\x90 inf (\xe2\x88\x80 v \xce\xb5 graph | v <> start)\n\n        # Finally, creates another hash table to keep track, for each vertex u, of the vertex through which u was reached.\n        parents[v] \xe2\x86\x90 null ( v \xce\xb5 graph)\n

\n

\n

A* 需要两个额外的参数， adistance function和 a\n heuristic。它们都有助于计算所谓的\nf-score。该值是从源到达当前节点\n 的成本和从 u 到达\n目标所需的预期成本的组合。

\n

通过控制这两个参数，我们可以获得 BFS 或\nDijkstra\xe2\x80\x99s 算法（或两者都不是）。对于它们两个，heuristic\n 将需要是一个等于 0 的函数，\n我们可以这样写

\n

\n

   lambda(v) \xe2\x86\x92 0 \n

\n

\n

事实上，这两种算法完全忽略了任何有关顶点到目标距离的概念或信息。

\n

对于距离度量，情况有所不同：

\n

\n

\n

• Dijkstra\xe2\x80\x99s 算法使用边\xe2\x80\x99s 权重作为距离函数，因此我们需要传递类似

  \n

    distance = lambda(e) \xe2\x86\x92 e.weight \n

  \n
\n

• BFS只考虑遍历的边数，相当于认为所有边具有相同的权重，同样等于1！因此，我们可以通过

  \n

    distance = lambda(e) \xe2\x86\x92 1 \n

  \n
\n

\n

A* 仅在某些我们拥有可以以某种方式使用的额外信息的情况下才会获得优势。当我们有关于所有或某些顶点到目标的距离的信息时，我们可以使用 A* 来更快地推动搜索到目标。

\n

\n

\n

请注意，在这种特殊情况下，关键因素是顶点携带额外的信息（它们的位置是固定的），这可以帮助估计它们到最终目标的距离。这\nisn\xe2\x80\x99t始终为真，但对于通用图通常不是这种情况。换句话说，这里的额外信息不是来自图表，而是来自领域知识。

\n

\n

The key, here and always, is the quality of the extra information \ncaptured by the Heuristic function: the more reliable and closer \nto real distance the estimate, the better A* performs.\n

\n

参考

\n