什么是一致代价搜索和最佳优先搜索方法的区别？

Question

什么是一致代价搜索和最佳优先搜索方法的区别？

searchartificial-intelligencedifferencebest-first-searchuniform-cost-search

18

这两种方法都有一个数据结构来保存要扩展的节点及其成本。这两种方法首先扩展成本最佳的节点。那么它们之间有什么区别呢？

有人告诉我，均一成本搜索是一种盲目的方法，而最佳优先搜索则不是，这让我更加困惑了（它们都具有有关节点成本的信息吗？）。

- T.Poe

5个回答

11

这里有一个小误解。统一代价搜索、最佳优先搜索和A* 搜索算法都是不同的算法。统一代价 是一种无信息搜索算法，而 最佳优先 和A* 搜索算法是启发式搜索算法。启发式意味着它使用启发函数来决定扩展节点。最佳优先搜索和 A* 之间的区别在于，最佳优先搜索使用f(n)=h(n) 进行扩展，而 A* 使用f（n）=g(n)+h(n) 来选择扩展节点。h(n) 是启发式函数，g(n) 是从起始节点到节点n的实际成本。这里可以看到更详细的内容。

- fatihgonen

5

对被接受的答案进行轻微更正

最佳优先搜索并不估计当前状态距离目标有多近，而是估计从当前状态开始，每个下一状态到达目标的距离，以影响所选路径。

在统一代价搜索中，扩展代价最小的节点（无论启发式函数如何），而最佳优先搜索则扩展最小的（代价+启发式）节点。

f(n) 是用于评估潜在节点扩展的代价函数
g(n) 是移动到节点n的代价
h(n) 是预计从n到最终目标状态所需的代价

统一代价搜索中使用的f(n)

f(n) = g(n)

最佳优先搜索中使用的f(n)函数（A*算法是最佳优先搜索的一个例子）

f(n) = h(n)

A*搜索中使用的f(n)。

注意：在上面的最佳优先搜索中，h(n)被扩展到A*中，以便始终包括g(n)。它仍然基本上只是一种启发式方法，但它是一种包括g(n)的启发式方法。

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

在遍历树查找目标状态n时，每个函数都评估潜在的扩展节点，而不是当前节点。

- boylec1986

7

不用，A*算法使用 f(n) = g(n) + h(n)。 - logi-kal

@boylec1986，你提供了维基百科的链接。你自己有没有读过它？当然，星形搜索是最佳优先搜索的一种特殊情况。但BFS和A是不同的。BFS的标准是使用f(n)并展开具有最低f(n)的节点。在简单的BFS中，它只是f(n)=h(n)。A也使用f(n)，这就是为什么它是BFS的一种特殊情况。但它的f(n)=g(n)+h(n)。 - Francis

谢谢Francis，我花了一些时间才理解你的意思。我已经编辑了我的答案。 - boylec1986

1

均匀代价搜索会选择距离最近的未访问节点，计算通过它到达每个未访问邻居的距离，并在距离更短时更新邻居的距离。

最佳优先搜索是一种基于启发式的算法，试图预测路径末端（即路径中的最后一个节点）与目标节点有多接近，以便首先扩展被判断为更接近解决方案的路径。

- Jianqiang Chen

你说“最短距离”，这里的“距离”是指什么？是指到某处的最短距离还是从某处的最短距离？ - nbro

1

以下是它们的不同之处：

统一代价搜索（UCS）扩展具有最低路径成本（即具有最低g（n））的节点，而最佳优先搜索（BFS）扩展距离目标最近的节点
UCS无法处理启发式函数，而BFS可以处理启发式函数
在UCS中，f（n）= g（n），而在BFS中，f（n）= g（n）+ h（n）。

- rashedcs

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Ivan Sivak · Accepted Answer

区别在于启发式函数。

一致代价搜索是无信息搜索：它不使用任何领域知识。它扩展成本最小的节点，并且在每个方向上都这样做，因为没有提供有关目标的信息。它可以被视为一个函数f(n) = g(n)，其中g(n)是路径成本（“路径成本”本身是将数值成本分配给路径的函数，与性能度量相关，例如公里数或移动次数等）。它只是到达节点n的成本。

最佳优先搜索是启发式搜索：它使用启发式函数来估计当前状态与目标的接近程度（我们是否正在接近目标？）。因此，我们的成本函数f(n) = g(n)与从n到目标的成本h(n)（估计该成本的启发式函数）相结合，给出f(n) = g(n) + h(n)。最佳优先搜索算法的一个例子是A*算法。

是的，两种方法都有一个扩展节点列表，但最佳优先搜索将尝试最小化已扩展节点的数量（路径成本+启发式函数）。