A*搜索算法

Question

我想就以下A*搜索例子中的问题进行澄清：

红色椭圆圈标出的部分是我不理解的地方；看起来，{S,B} f=2+6=8被从扩展S（上面）取出/移动/复制并用于扩展A。另外，{S,A,X} f=(1+4)+5=10似乎从扩展A中取出/移动/复制并用于扩展B。

请问有人能够友好地解释一下这是为什么吗？我能够很好地阅读图表，并且没有任何解释方面的困难——只是我不知道为什么前述路径/路线会在其他地方重复。

谢谢。

- Mus

Answer 1

这是将当前最佳项移除并用扩展替换它（将新项目插入到列表中适当的位置）。可以这样理解：

扩展S：

- {S,A} f = 1+5 = 6 - {S,B} f = 2+6 = 8

扩展A：

- 删除 {S,A} f = 1+5 = 6 - {S,B} f = 2+6 = 8 - {S,A,X} f = (1+4)+5 = 10 - {S,A,Y} f = (1+7)+8 = 16

扩展B：

- 删除 {S,B} f = 2+6 = 8 - {S,A,X} f = (1+4)+5 = 10 - {S,B,C} f = (2+7)+4 = 13 - {S,A,Y} f = (1+7)+8 = 16 - {S,B,D} f = (2+1)+15 = 18

- Matthew Slattery

---

先生，我是人工智能方面的新手，就这个图表而言，我有一个疑问，这里需要计算所有可能的路径。那么它怎么有用呢？在《Rich and Knight》中提到，h'不应高估h，在维基百科上写道，估计成本（h'）必须始终小于或等于到达目标的实际成本。这意味着我们必须预先计算所有可能的路径吗？是这样吗？还是我漏掉了什么。这将是非常有帮助的。 - gursahib.singh.sahni

Answer 2

路径不会重复，它们只是保留为算法尚未探索的路径。A*算法通过维护一个“开放集”来工作，该集合包含算法已知如何到达（以及成本）但尚未尝试扩展的节点。

在每次迭代中，算法选择一个节点从开放集中进行扩展（选择具有最低f函数的节点- f函数是算法已知到达该节点所需的成本（g）和算法估计从节点到目标所需的成本（h，即启发式）之和）。

http://en.wikipedia.org/wiki/A*_search_algorithm

看那里的伪代码，你会发现使用了开放集。所以底线是 - 算法不是通过将路径或节点从一次迭代复制、复制或移动到另一次迭代来工作的 - 它只是在相同的节点集合上进行工作（当然会添加和删除节点）。希望这能帮到你...

- bloodcell