artificial-intelligence - 在什么情况下BFS和DFS会比A *搜索算法更有效？

Question

我已经针对广度优先搜索(BFS)和深度优先搜索(DFS)测试了A *搜索，发现使用A *扩展的节点越来越少。

我知道A *通过使用启发式和边缘成本函数来扩展本来就不那么昂贵的路径。

与A *搜索算法相比，在什么情况下BFS和DFS会更有效？

Answer 1

BFS使用队列，而A *使用优先级队列。通常，队列比优先级队列快得多(例如Dequeue()是O(1)与O(log n))。 A *的优势在于，它通常比BFS扩展更少的节点，但是如果不是这种情况，BFS将更快。如果使用的启发式方法较差，或者图形非常稀疏或很小，或者对于给定的图形，启发式方法失败，则可能会发生这种情况。

请记住，BFS仅对未加权图有用。如果该图经过加权，则需要使用BFS的哥哥Dijkstra的Algorithm。该算法使用优先级队列，因此，除非启发式算法失败，否则它几乎永远不会比A *快。