统一成本搜索和最佳优先搜索方法之间有什么区别？

Question

这两种方法都有一个数据结构,可以保持节点(及其成本)的扩展.两种方法首先以最高成本扩展节点.那么,它们之间有什么区别？

有人告诉我,统一成本搜索是一种盲目的方法,最好先搜索不是,这让我更加困惑(两者都有关于节点成本的信息？).

Answer 1

不同之处在于启发式功能.

统一成本搜索是不知情的搜索:它不使用任何领域知识.它扩展了成本最低的节点,并且它在每个方向都这样做,因为没有提供有关目标的信息.它可以被视为一种函数f(n) = g(n),其中g(n)是路径成本("路径成本"本身是一个函数,它根据性能度量为路径分配数字成本,例如以千米为单位的距离或移动的数量等).到达节点n只需要一个成本.

最佳优先搜索是通知搜索:它使用启发式函数来估计当前状态与目标的接近程度(我们是否接近目标？).因此,我们的成本函数f(n) = g(n)与从n到达目标的成本h(n)(估计成本的启发函数)相结合f(n) = g(n) + h(n).最优先搜索算法的示例是A*算法.

是的,这两种方法都有一个扩展节点列表,但是最好的搜索将尝试最小化扩展节点的数量(路径成本+启发式函数).

Answer 2

对接受的答案稍作修正

最佳优先搜索不估计当前状态与目标的接近程度，而是估计每个下一个状态（从当前状态）与目标的接近程度以影响所选路径。

统一成本搜索扩展了最低成本节点（不管启发式），最佳优先搜索扩展了最低成本（成本+启发式）节点。

• f(n) 是用于评估要扩展的潜在节点的成本函数
• g(n) 是移动到节点 n 的成本
• h(n) 是到达最终目标状态所需的估计成本，如果我们要转到 n

用于统一成本搜索的 f(n)

f(n) = g(n)

最佳优先搜索中使用的 f(n)（A* 是最佳优先搜索的示例）

f(n) = g(n) + h(n)

这些函数中的每一个都在评估潜在的扩展节点，而不是在遍历树以寻找作为目标状态的 n 时的当前节点

Answer 3

这里有一点误会.统一成本搜索,最佳第一搜索和A*搜索算法都是不同的算法.当Best First和A*搜索算法是通知搜索算法时,统一成本是一种不知情的搜索算法.通知意味着它使用启发式函数来决定扩展节点.最佳第一次搜索和A*之间的差异是最好首先用于扩展和A*用于选择扩展节点.是启发式功能.是从起始节点到节点n的实际成本.f(n) = h(n)f(n) = g(n)+h(n)h(n)g(n)

https://www.cs.utexas.edu/~mooney/cs343/slide-handouts/heuristic-search.4.pdf这里可以看到更详细的信息.