14

我想对以下 A* 搜索示例进行澄清：

A* 搜索示例

用红色椭圆突出显示的部分是我不明白的区域；似乎{S,B} f=2+6=8已从Expand S（以上）中获取/移动/复制并用于Expand A. 似乎也{S,A,X} f=(1+4)+5=10已从Expand A.Expand B

有人可以解释为什么会这样吗？我能够很好地阅读图表并且在解释它时没有任何问题 - 这只是我不知道为什么上述路径/路线在其他地方重复的事实。

谢谢你。

4

2 回答 2

9

这是获取当前最佳项目，将其删除，然后用扩展替换它（将新项目插入列表中的适当位置）。可以这样想：

展开 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
于 2011-05-01T16:48:52.883 回答
2

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

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

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

看看那里的伪代码，你可以看到使用了开放集。所以底线 - 算法不是通过将路径或节点从一个迭代复制到另一个迭代来工作 - 它只是在同一个节点集合上工作（当然节点确实会从集合中添加和删除）。

希望这可以帮助...

于 2011-05-01T16:48:10.220 回答