dijkstra & 的区别和优势一个明星 [英] Difference and advantages between dijkstra & A star

问题描述

我读到了这个:http://en.wikipedia.org/wiki/A*_search_algorithm

它说 A* 比使用 dijkstra 更快，并且使用最佳优先搜索来加快速度.

It says A* is faster than using dijkstra and uses best-first-search to speed things up.

如果我需要算法以毫秒为单位运行，那么 A* 什么时候成为最突出的选择.

If I need the algorithm to run in milliseconds, when does A* become the most prominent choice.

据我所知，它不一定能返回最好的结果.

From what I understand it does not necessarily return the best results.

如果我需要快速的结果，预先计算路径是否更好?存储它们可能需要数兆字节的空间.

If I need quick results, is it better to pre-compute the paths? It may take megabytes of space to store them.

推荐答案

它说 A* 比使用 dijkstra 更快，并且使用最佳优先搜索加快速度.

It says A* is faster than using dijkstra and uses best-first-search to speed things up.

A* 基本上是 Dijkstra 的知情变体.
A* 被认为是最佳优先搜索"，因为它贪婪地根据 f(v) [f(v) = h(v) + g(v)] - 其中 h 是启发式，g 是到目前为止的成本.

A* is basically an informed variation of Dijkstra.
A* is considered a "best first search" because it greedily chooses which vertex to explore next, according to the value of f(v) [f(v) = h(v) + g(v)] - where h is the heuristic and g is the cost so far.

请注意，如果您使用非信息启发式函数:h(v) = 0 对于每个 v:您会得到 A* 根据仅用于到目前为止的成本"(g(v))，与 Dijkstra 算法相同 - 所以如果 h(v) = 0，A* 默认为 Dijkstra 算法.

Note that if you use a non informative heuristic function: h(v) = 0 for each v: you get that A* chooses which vertex to develop next according to the "so far cost" (g(v)) only, same as Dijkstra's algorithm - so if h(v) = 0, A* defaults to Dijkstra's Algorithm.

如果我需要算法以毫秒为单位运行，那么 A* 什么时候变成最突出的选择.

If I need the algorithm to run in milliseconds, when does A* become the most prominent choice.

不完全是，这取决于很多事情.如果你有一个下降启发式函数——根据我的个人经验，贪心最好(仅根据启发式函数进行选择)——通常比 A* 快得多(但甚至不是接近最优).

Not quite, it depends on a lot of things. If you have a descent heuristic function - from my personal experience, greedy best first (choosing according to the heuristic function alone) - is usually significantly faster than A* (but is not even near optimal).

据我所知，它不一定返回最好的结果.

From what I understand it does not necessarily return the best results.

如果您使用 可接受的启发式函数.如果您的功能不被接受 - 所有赌注都将关闭.

A* is both complete (finds a path if one exists) and optimal (always finds the shortest path) if you use an Admissible heuristic function. If your function is not admissible - all bets are off.

如果我需要快速的结果，预先计算路径是否更好?有可能占用数兆字节的空间来存储它们.

If I need quick results, is it better to pre-compute the paths? It may take megabytes of space to store them.

这是对某些问题的常见优化，例如在 15-puzzle 问题，但它更先进.从 A 点到 B 点的路径称为宏.有些路径非常有用，应该记住.机器学习组件被添加到算法中，以便通过记住这些宏来加快速度.

This is a common optimization done on some problems, for example on the 15-puzzle problem, but it is more advanced. A path from point A to point B is called a Macro. Some paths are very useful and should be remembered. A Machine Learning component is added to the algorithm in order to speed things up by remembering these Macros.

请注意，这里从 A 点到 B 点的路径通常不在状态图上——而是在问题本身(例如，如何将一个正方形从最低线移动到最高线...)

Note that the path from point A to point B in here is usually not on the states graph - but in the problem itself (for example, how to move a square from the lowest line to the upper line...)

加快速度:
如果你有一个启发式算法并且你发现它太慢了，你想要一个更快的解决方案，即使不是最优的 - A* Epsilon 通常比 A* 快，同时给你一个关于路径最优性的界限(它与最优的接近程度).

To speed things up:
If you have a heuristic and you find it too slow, and you want a quicker solution, even if not optimal - A* Epsilon is usually faster then A*, while giving you a bound on the optimality of the path (how close it is to being optimal).

这篇关于dijkstra & 的区别和优势一个明星的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！