我正在查看马里奥 AI 竞赛中的人一直在做什么，其中一些人利用 A*（A-Star）路径算法构建了一些非常简洁的马里奥机器人。
我的问题是，A-Star 与 Dijkstra 相比如何？看着它们，它们看起来很相似。
为什么有人会使用一个而不是另一个？尤其是在游戏路径的背景下？
问问题
83220 次
12 回答
197
Dijkstra 是 A* 的一个特例（当启发式为零时）。
于 2009-08-26T05:18:30.183 回答
123
迪杰斯特拉：
它有一个成本函数，即从源到每个节点的真实成本值：f(x)=g(x)。
它通过仅考虑实际成本来找到从源到每个其他节点的最短路径。
A* 搜索：
它有两个成本函数。
g(x): 和迪杰斯特拉一样。到达一个节点的实际成本x。h(x)x：从节点到目标节点的近似成本。这是一个启发式函数。这种启发式函数永远不应高估成本。这意味着，从节点到达目标节点的实际成本x应该大于或等于h(x)。它被称为可接受的启发式。
每个节点的总成本由下式计算f(x)=g(x)+h(x)
A* 搜索仅在看起来很有希望时才会扩展节点。它只关注从当前节点到达目标节点，而不是到达所有其他节点。如果启发式函数是可接受的，则它是最优的。
因此，如果您的启发式函数能够很好地估计未来成本，那么您将需要探索比 Dijkstra 少得多的节点。
于 2013-04-28T22:36:35.900 回答
21
之前的海报所说的，再加上因为 Dijkstra 没有启发式方法，并且在每一步都选择成本最小的边，它往往会“覆盖”更多的图表。因此，Dijkstra 可能比 A* 更有用。很好的例子是当您有多个候选目标节点，但您不知道哪个最接近（在 A* 情况下，您必须多次运行它：每个候选节点一次）。
于 2009-08-26T05:45:10.580 回答
9
Dijkstra 的算法永远不会用于寻路。如果你能想出一个像样的启发式算法（通常对于游戏来说很容易，尤其是在 2D 世界中），那么使用 A* 是一件轻而易举的事。根据搜索空间，迭代深化 A* 有时更可取，因为它使用的内存更少。
于 2009-08-26T05:45:11.050 回答
8
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)
于 2017-03-14T19:45:52.963 回答
6
您可以将 A* 视为 Dijkstra 的指导版本。这意味着，您将使用启发式方法来选择方向，而不是探索所有节点。
更具体地说，如果您使用优先级队列实现算法，那么您正在访问的节点的优先级将是成本（先前节点成本+到达此处的成本）和启发式估计的函数here到目标。而在 Dijkstra 中，优先级仅受节点的实际成本影响。在任何一种情况下，停止标准都是达到目标。
于 2015-05-28T03:28:04.093 回答
5
Dijkstra 找到从起始节点到所有其他节点的最小成本。A* 找到从起始节点到目标节点的最小成本。
因此，当您只需要从一个节点到另一个节点的最小距离时，Dijkstra 的效率似乎会降低。
于 2010-05-22T23:19:34.117 回答
2
Dijkstra 算法肯定会找到最短路径。另一方面，A* 取决于启发式。出于这个原因，A* 比 Dijkstra 的算法更快，如果你有一个好的启发式算法，它会给出好的结果。
于 2009-09-20T03:40:58.030 回答
0
如果您查看 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 的算法并不羞于自我纠正，以防
节点再次弹出。
这应该使 Astar 更快，更适合寻路。
于 2010-12-05T11:11:54.677 回答
0
在 A* 中，对于每个节点，您检查其传出连接的 .
对于每个新节点，您计算迄今为止的最低成本 (csf)，具体取决于与该节点的连接权重以及您必须到达前一个节点的成本。
此外，您估计从新节点到目标节点的成本并将其添加到 csf。您现在有了估计的总成本（等）。（etc = csf + 到目标的估计距离）接下来，您从新节点中选择具有最低等的节点。
与以前一样，直到新节点之一成为目标。
Dijkstra 的工作原理几乎相同。除了估计到目标的距离始终为 0，当目标不仅是新节点之一，而且是具有最低 csf 的节点时，算法首先停止。
A* 通常比 dijstra 快，但情况并非总是如此。在电子游戏中，您经常喜欢“足够接近游戏”的方法。因此，来自 A* 的“足够接近”的最优路径通常就足够了。
于 2013-06-11T12:45:24.053 回答
0
BFS 和 Dijkstra 的算法非常相似；它们都是 A* 算法的特例。
A* 算法不仅更通用；它在某些情况下提高了 Dijkstra 算法的性能，但这并不总是正确的；在一般情况下，Dijkstra 算法的速度与 A* 一样快。
Dijkstra 算法有 3 个参数。如果您曾经解决过网络延迟时间问题：
class Solution:
def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
A* 方法有额外的 2 个参数：
function aStar(graph, start, isGoal, distance, heuristic)
queue ← new PriorityQueue()
queue.insert(start, 0)
# hash table to keep track of the distance of each vertex from vertex "start",
#that is, the sum of the weight of edges that needs to be traversed to get from vertex start to each other vertex.
# Initializes these distances to infinity for all vertices but vertex start .
distances[v] ← inf (∀ v ε graph | v <> start)
# hash table for the f-score of a vertex,
# 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".
fScore[v] ← inf (∀ v ε graph | v <> start)
# Finally, creates another hash table to keep track, for each vertex u, of the vertex through which u was reached.
parents[v] ← null ( v ε graph)
A* 接受两个额外的参数 adistance function和 a heuristic。它们都有助于计算所谓的 f 分数。该值是从源到达当前节点 u 的成本和从 u 到达目标所需的预期成本的混合。
通过控制这两个参数，我们可以获得 BFS 或 Dijkstra 算法（或两者都不是）。对于他们两个，heuristicwill 需要是一个完全等于 0 的函数，我们可以这样写
lambda(v) → 0
事实上，这两种算法都完全忽略了关于顶点到目标距离的任何概念或信息。
对于距离度量，情况有所不同：
Dijkstra 的算法使用边缘的权重作为距离函数，所以我们需要传递类似
distance = lambda(e) → e.weightBFS 只考虑遍历的边数，相当于认为所有边的权重相同，等于 1！因此，我们可以通过
distance = lambda(e) → 1
A* 仅在我们拥有可以以某种方式使用的额外信息的某些情况下获得优势。当我们有关于从所有或部分顶点到目标的距离的信息时，我们可以使用 A* 将搜索更快地驱动到目标。
请注意，在这种特殊情况下，关键因素是顶点带有额外的信息（它们的位置是固定的），可以帮助估计它们到最终目标的距离。这并不总是正确的，并且通常不是通用图的情况。换句话说，这里的额外信息不是来自图表，而是来自领域知识。
The key, here and always, is the quality of the extra information
captured by the Heuristic function: the more reliable and closer
to real distance the estimate, the better A* performs.
于 2021-10-27T00:43:14.857 回答
-1
Dijkstra 的算法绝对是完整和最优的，你总能找到最短路径。然而，它往往需要更长的时间，因为它主要用于检测多个目标节点。
A* search另一方面，启发式值很重要，您可以定义它以更接近您的目标，例如曼哈顿到目标的距离。它可以是最优的或完整的，这取决于启发式因素。如果您有一个目标节点，它肯定会更快。
于 2011-10-30T14:45:02.317 回答