这两种方法都有一个数据结构来保存要扩展的节点及其成本。这两种方法首先扩展成本最佳的节点。那么它们之间有什么区别呢?
有人告诉我,均一成本搜索是一种盲目的方法,而最佳优先搜索则不是,这让我更加困惑了(它们都具有有关节点成本的信息吗?)。
这两种方法都有一个数据结构来保存要扩展的节点及其成本。这两种方法首先扩展成本最佳的节点。那么它们之间有什么区别呢?
有人告诉我,均一成本搜索是一种盲目的方法,而最佳优先搜索则不是,这让我更加困惑了(它们都具有有关节点成本的信息吗?)。
f(n) = g(n)
,其中g(n)
是路径成本(“路径成本”本身是将数值成本分配给路径的函数,与性能度量相关,例如公里数或移动次数等)。它只是到达节点n的成本。
最佳优先搜索是启发式搜索:它使用启发式函数来估计当前状态与目标的接近程度(我们是否正在接近目标?)。因此,我们的成本函数f(n) = g(n)
与从n到目标的成本h(n)
(估计该成本的启发式函数)相结合,给出f(n) = g(n) + h(n)
。最佳优先搜索算法的一个例子是A*算法。
是的,两种方法都有一个扩展节点列表,但最佳优先搜索将尝试最小化已扩展节点的数量(路径成本+启发式函数)。
f(n)=h(n)
进行扩展,而 A* 使用f(n)=g(n)+h(n)
来选择扩展节点。h(n)
是启发式函数,g(n)
是从起始节点到节点n的实际成本。
这里可以看到更详细的内容。对被接受的答案进行轻微更正
最佳优先搜索并不估计当前状态距离目标有多近,而是估计从当前状态开始,每个下一状态到达目标的距离,以影响所选路径。
在统一代价搜索中,扩展代价最小的节点(无论启发式函数如何),而最佳优先搜索则扩展最小的(代价+启发式)节点。
f(n) = g(n)
f(n) = h(n)
注意:在上面的最佳优先搜索中,h(n)被扩展到A*中,以便始终包括g(n)。它仍然基本上只是一种启发式方法,但它是一种包括g(n)的启发式方法。
f(n) = g(n) + h(n).
在遍历树查找目标状态n时,每个函数都评估潜在的扩展节点,而不是当前节点。
统一代价搜索(UCS)扩展具有最低路径成本(即具有最低g(n))的节点,而最佳优先搜索(BFS)扩展距离目标最近的节点
UCS无法处理启发式函数,而BFS可以处理启发式函数
在UCS中,f(n)= g(n),而在BFS中,f(n)= g(n)+ h(n)。