3

A* 搜索算法会在什么条件下探索搜索空间中的所有状态？这是最坏的情况吗？

根据我的说法，如果通往目标的路线上每个节点的 f(n) 高于同一级别的其他节点，它将被迫搜索整个搜索空间。这是最坏的情况，因为必须扩展生成的所有节点才能达到目标。

这个对吗？

4

1 回答 1

1

来自维基百科：

A* 的时间复杂度取决于启发式。在最坏的情况下，扩展的节点数在解的长度（最短路径）上呈指数，但是当搜索空间是一棵树，存在单一目标状态，启发式函数h满足a时，它是多项式的某些标准：

于 2012-11-17T10:29:54.840 回答