0

A* 搜索似乎重新计算了 Arad、Sibiu 和其他重复状态的 f 值,它不应该这样做,因为这些节点已经展开并处于关闭状态。那么我在这里错过了什么?(图片来自 Russel 和 Norvig - 人工智能。

图片:在此处输入图像描述

在这种情况下,这些节点不会扩展,因为它们的 f 值大于最佳路径,如果不是这样怎么办?即,如果最近的 f 值返回到前一个节点怎么办?A*会这样做吗?

4

1 回答 1

0

大多数 A* 算法回溯,这意味着一个节点只能被访问一次。否则,反向指针链被破坏,路径无法恢复。但是,如果对角线移动比方形移动更昂贵,您可能会遇到这样一种情况,即优先级队列中较低的节点可以访问成本更低的访问节点。通常你会忽略它并将访问的节点视为不可访问 - 除非你使用奇怪而奇妙的启发式或有一个非常奇怪的图形,否则它几乎不会对路径长度产生影响。

于 2017-03-19T20:29:04.247 回答