dijkstra&公司之间的差异和优势一个明星 [英] Difference and advantages between dijkstra & A star

问题描述

我读到：
http://en.wikipedia.org/wiki/ A * _search_algorithm

它表示A *比使用dijkstra更快，并且使用最先搜索来加快速度。

如果我需要算法以毫秒为单位运行，A *成为什么时候成为最显眼的选择。

据我所知，必然会返回最佳结果。

如果我需要快速结果，预先计算路径会更好吗？它可能需要兆字节的空间来存储它们。

解决方案

它表示A *比使用dijkstra并使用最优先搜索到
的速度。

A *基本上是Dijkstra知情的变体。

A *被认为是最好的第一搜索，因为它根据 f（v）的值来贪婪地选择接下来探索哪个顶点。 f（v）= h（v）+ g（v）] - 其中 h 是启发式， g 是目前的成本。

请注意，如果您使用非信息性启发式函数：对于每一个 v ，h（v）= 0 ：你得到A *根据迄今为止的成本选择下一个要开发的顶点。 g（v）），与Dijkstra算法相同 - 所以如果 h（v）= 0 ，A * defaults到Dijkstra算法。

如果我需要算法以毫秒为单位运行，那么A *何时变成
是最重要的选择。

不完全取决于很多事情。如果你有一个下降启发式功能 - 从我个人的经验来看，最好先贪心（根据启发式功能单独选择） - 通常比A *快得多（但并不接近最佳）。

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

$ b $如果您使用可接受的启发式功能。如果您的功能不可接受 - 所有投注都关闭。

如果我需要快速结果，预先计算路径会更好吗？可能
需要兆字节的空间来存储它们。

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

请注意，这里从点A到点B的路径通常不是在状态图上 - 但在问题本身（例如，如何将方块从最低行移动到上一行...）

要加快速度：

如果您有启发式并且发现速度太慢，并且您想要更快的解决方案，即使不是最佳解决方案 - A * Epsilon通常比A *更快，同时给你一个路径最优性的界限（它与最佳）。

I read this: http://en.wikipedia.org/wiki/A*_search_algorithm

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

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.

解决方案

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

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.

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.

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

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.

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.

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

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屋！