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

Dijkstra 是 A * 的一个特例(当启发式为零时)。

之前的海报说，加上因为 Dijkstra 没有启发式，在每一步挑选边缘最小的成本，它往往“覆盖”更多的图表。因为 Dijkstra 可能比 A * 更有用。一个很好的例子是，当您有几个候选目标节点，但是您不知道哪一个是最接近的(在 A * 的情况下，您必须多次运行它: 对于每个候选节点运行一次)。

Dijkstra 的算法永远不会用于寻路。如果你能想出一个像样的启发式方法(通常对游戏来说很容易，特别是在2D 世界中) ，使用 A * 是一个不需要动脑筋的方法。根据搜索空间的不同，迭代深化 A * 有时更可取，因为它使用较少的内存。

Dijkstra 的算法绝对能找到最短路径。另一方面，A * 取决于启发式。由于这个原因，A * 比 Dijkstra 的算法更快，如果你有一个好的启发式算法，它会给出很好的结果。

Dijkstra 找到从起始节点到所有其他节点的最小开销。A * 查找从开始节点到目标节点的最小开销。

因此，当您所需要的只是从一个节点到另一个节点的最小距离时，似乎 Dijkstra 的效率较低。

如果你看看阿斯塔的 伪代码:

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 不会多次计算一个节点,
因为它认为只查看一次节点就足够了
它的启发式。

以防万一，Dijkstra 的算法不怕自我修正
一个节点再次出现。

其中 应该使阿斯塔尔更快，更适合路径寻找。

Dijkstra 的算法是绝对完整和最优的，你总是会找到最短的路径。然而，它往往需要更长的时间，因为它主要用于检测多个目标节点。

另一方面，A* search与启发式值有关，您可以定义启发式值以更接近您的目标，例如曼哈顿到目标的距离。它可以是最优的，也可以是完整的，这取决于启发式因素。如果你有一个单一的目标节点，它肯定会更快。

迪克斯特拉:

它有一个成本函数，即从源到每个节点的实际成本价值: f(x)=g(x)。
该算法只考虑实际成本，找出从源节点到其他节点的最短路径。

搜索:

它有两个成本函数。

1. 与 Dijkstra 相同。到达节点 x的实际成本。
2. 从节点 x到目标节点的大致费用。这是一个启发式函数。这个启发式函数不应该高估成本。这意味着，从节点 x到达目标节点的实际成本应该大于或等于 h(x)。这就是所谓的可采纳的启发式。

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

A * 搜索只在有希望的情况下扩展节点。它只关注从当前节点到达目标节点，而不是到达每个其他节点。这是最优的，如果启发式函数是允许的。

因此，如果您的启发式函数能够很好地估计未来的成本，那么您将需要探索比 Dijkstra 少得多的节点。

在 A * 中，对于每个节点，检查它们的输出连接。
对于每个新节点，根据到这个节点的连接权重和到达前一个节点的成本，计算到目前为止的最低成本(csf)。
此外，还要估算从新节点到目标节点的成本，并将其添加到 csf 中。你现在有了估计的总成本(等)。(etc = csf + 到目标的估计距离) 接下来，从新节点中选择具有最低等级的节点。
像以前一样做，直到其中一个 新节点成为目标。

Dijkstra 的工作原理几乎一样。除了估计到目标的距离始终为0以外，算法首先在目标不仅是 新节点目标之一，而且是 csf 最低的目标时停止。

A * 通常比 dijstra 快，尽管情况并非总是如此。 在视频游戏中，你通常会推崇“足够接近一个游戏”的方法。因此，从 A * 开始的“足够接近”的最佳路径通常就足够了。

您可以考虑 A * 是 Dijkstra 的引导版本。也就是说，不是探索所有的节点，而是使用启发式方法来选择一个方向。

更具体地说，如果你使用一个优先级队列来实现算法，那么你访问的节点的优先级将是成本(先前的节点成本 + 到达这里的成本)和从这里到目标的启发式估计的函数。而在 Dijkstra 中，优先级仅受节点的实际成本的影响。无论哪种情况，停止标准都是达到目标的。

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)

BFS 和 Dijkstra 的算法非常相似; 都是 A * 算法的特例。

A * 算法不仅更通用，而且提高了 Dijkstra 的算法在某些情况下，但这并不总是正确的; 在一般情况下，Dijkstra 算法的渐近速度与 A * .

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

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

A * 方法有额外的两个参数:

 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 * 需要两个额外的参数，一个 distance function和一个 它们都有助于计算所谓的 这个值是到达当前节点的成本的组合 从来源和预期的成本需要，以达到 来自你的目标。

通过控制这两个参数，我们可以获得 BFS 或 Dijkstra 的算法(或者两者都不是) 需要是一个等于0的函数 我们可以写

   lambda(v) → 0

事实上，这两种算法都完全忽略了 或关于顶点到目标的距离的信息。

至于距离指标，情况则有所不同:

• Dijkstra 的算法使用边缘的权重作为距离函数，所以我们需要传递

    distance = lambda(e) → e.weight
  

• BFS 只考虑了遍历的边的数量，这相当于考虑所有的边都有相同的权重，完全等于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.

参考文献