我已经测试了A*搜索算法与广度优先搜索（BFS）和深度优先搜索（DFS），发现A*搜索算法扩展更少的节点。
我理解A*使用启发式和边缘成本函数扩展已经更便宜的路径。
在哪些情况下，相较于A*搜索算法，BFS和DFS会更加高效呢？
BFS和DFS算法在什么情况下比A*搜索算法更有效？
12
- Marjan
1
有趣的问题伙计。你能为这个问题添加一个总结，详细说明A*、BFS和DFS的节点扩展吗？ - Rann Lifshitz
2个回答
15
BFS使用队列，而A*使用优先级队列。一般来说，队列比优先级队列快得多（例如
请记住，BFS仅适用于未加权的图。如果图具有权值，则需要使用BFS的老兄Dijkstra算法。该算法使用优先级队列，因此除非启发式函数失效，否则几乎永远不应该比A*快。
Dequeue()的时间复杂度为O(1)，而优先级队列为O(log n)）。A*的优点在于它展开的节点通常比BFS少得多，但如果不是这种情况，BFS会更快。这可能发生在启发式函数很差、图非常稀疏或小，或者启发式函数无法针对给定的图进行操作。请记住，BFS仅适用于未加权的图。如果图具有权值，则需要使用BFS的老兄Dijkstra算法。该算法使用优先级队列，因此除非启发式函数失效，否则几乎永远不应该比A*快。
- BlueRaja - Danny Pflughoeft
1
当启发式函数不一致时，广度优先搜索可能会比A*更快。 (不一致的启发式函数不遵守三角不等式。一致的启发式函数从一个状态到下一个状态永远不会改变超过边缘成本。)
使用不一致的启发式函数，A*可能会将N个状态扩展多达2^N次。可以在网上找到这种情况的示例。如果您想了解发生了什么，请逐步执行示例。BFS每个状态最多只会扩展一次。请注意，算法B可以部分修复此问题（最多将N个状态扩展N^2次），但这仍然是一个很大的开销。最近的IBEX算法具有更好的最坏情况保证-N log C*，其中C*是最优解决方案成本。
如果目标位于第一分支，则深度优先搜索可能优于A*和BFS。在此演示中，您可以将目标放置在树的不同状态中以查看发生的情况。
使用不一致的启发式函数，A*可能会将N个状态扩展多达2^N次。可以在网上找到这种情况的示例。如果您想了解发生了什么，请逐步执行示例。BFS每个状态最多只会扩展一次。请注意，算法B可以部分修复此问题（最多将N个状态扩展N^2次），但这仍然是一个很大的开销。最近的IBEX算法具有更好的最坏情况保证-N log C*，其中C*是最优解决方案成本。
如果目标位于第一分支，则深度优先搜索可能优于A*和BFS。在此演示中，您可以将目标放置在树的不同状态中以查看发生的情况。
还有其他常数因素需要考虑。DFS只需要一个状态的副本，而A*在OPEN/CLOSED列表上保留许多状态。但在这些情况下，应使用IDA*。
请注意，在具有一致启发式的单向搜索中，理论上，A*执行必要扩展的数量最少，以证明解决方案是最优的。
- Nathan S.
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接