algorithm - A* 搜索算法

Question

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

用红色省略号突出显示的部分是我不理解的地方； {S,B} f=2+6=8 似乎已从 Expand S(上文)中获取/移动/复制并用于 Expand A 。还显示 {S,A,X} f=(1+4)+5=10 已从 Expand A 中获取/移动/复制并用于 展开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