A*搜索算法

Question

关于以下A*搜索示例,我想澄清一些事情:

用红色椭圆突出显示的部分是我不理解的区域; 似乎{S,B} f=2+6=8已从Expand S(上方)采取/移动/复制并使用Expand A.它似乎{S,A,X} f=(1+4)+5=10也被采取/移动/复制Expand A和使用Expand B.

有人可以解释为什么会这样吗？我能够很好地阅读图表并且解释它没有任何问题 - 仅仅是因为我不知道为什么上述路径/路由在其他地方被复制了.

谢谢.

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