我对存储第一个节点后下一步要做什么有点困惑。在 wikipedia page about A*它表示忽略已经在闭集中的邻居,但如果它不存在,则将其添加到开集中(如果不存在)并检查 g 分数。
但是在这个页面https://brilliant.org/wiki/a-star-search/ ,它表示检查“邻居的 g 值是否低于当前且位于关闭列表中”,然后替换邻居的 g 值,否则如果“当前 g 值较低且该邻居位于打开列表中”“则替换邻居具有新的、更低的 g 值”
所以我对要检查什么感到有点困惑。如果该节点已经在闭集中,我是否会忽略该节点,或者我是否还需要检查它的 g 值并用它替换邻居的值?
在 A* 中获得第一个节点后我该怎么办?
最佳答案
如果我们找到封闭集中的邻居,则意味着我们之前已经访问过它。这意味着以下两件事之一:
它的 g 分数已经很小,因此 Brilliant 上的额外条件永远不会被执行。
启发式函数 h Not Acceptable ,即它高估了实现目标的实际最小成本。在这种情况下,Brilliant 上的代码可能会找到稍短的路径,但都不能保证找到最短的路径。要使用 Not Acceptable 启发式找到最短路径,您需要“重新打开”此类节点。这将导致算法多次重新访问整个子图,这将严重损害复杂性,而这不是 Brilliant 代码所做的。
总结一下:Brilliant 版本和 Wikipedia 版本之间的区别在于处理一个小极端情况,如果为 A* 提供“正确”(可接受的)启发式函数,则这种情况永远不会发生。
So I'm sort of confused on what to check for. Do I ignore the node if it's already in the closed set or do I need to also check it's g value and replace the neighbor's with it?
我会遵循维基百科代码并完全忽略闭集中的节点。
关于algorithm - 在 A* 搜索算法中,循环打开列表时会检查什么?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/55985654/