一次星际寻路。为什么你需要重新评估一个已经在开放列表中的相邻节点，如果它对当前节点具有较低的g成本？

Question

关于恒星路径搜索算法，有一件事我是不明白的。在伪代码中；如果当前节点(正被分析的节点)的g成本小于相邻节点g成本，则重新计算相邻节点g，h a f成本，并重新分配父节点。你为什么要这么做？

如果相邻节点的gCost大于当前节点的gCost，为什么需要重新计算相邻节点的成本和父节点？我在想，你需要什么实例来做这件事？

编辑；我正在观看此视频https://www.youtube.com/watch?v=C0qCR18gXdU\

在8.19，他说:当你遇到已经分析过的块(节点)时，问题是我们应该改变块的属性吗？

Answer 1

而不是更改父对象，而是使用Pathmax函数。它说，如果一个父节点的成本((A) <= heuristic(A) +())有一个子节点，则设置子节点的成本等于父节点的成本。

确保单调性的PathMax：

单调性：每个父节点的开销都大于或等于它的子节点的开销。

A*有一个属性：，它说如果你的成本是单调增加的，那么A*找到的第一个子路径((Sub))总是最终路径的一部分。更准确地说:在单调性下，每个节点首先通过最佳路径到达。

你明白为什么了吗？

假设你有一个图:(A，B) (B，C) (A，E)，(E，D)这里的每个元组意味着它们是相连的。假设成本是单调增加的，你的算法选择(A，B)，(B，C)，在这一点上，你知道你的算法已经选择了到目前为止的最佳路径，可以到达这个节点的所有其他路径，肯定成本更高，但如果成本不是单调增加，那么情况可能是(A，E)成本大于你当前的成本，从(E，D)它是零。所以你有更好的路径。

这个算法依赖于它的启发式函数，如果它被低估了，那么它会被累积的成本修正，但是如果它被高估了，那么它可以探索额外的节点，我把为什么会发生这种情况留给你。

如果对当前节点具有较低的g成本，为什么需要重新评估已在开放列表中的相邻节点？

不要这样做，因为这只是额外的工作。

推论:如果以后以相同的成本从节点p获得相同的节点，那么只需将该节点从队列中删除即可。不要扩展它。

Answer 2

首先给你一个小贴士。在本例中，https://www.youtube.com/watch?v=C0qCR18gXdU#t=08m19s是带书签的时间链接。

我们在第一次找到指向某个节点的路径时填充该节点。但我们找到的第一条路可能不是最便宜的。我们想要最便宜的，如果我们找到第二个便宜的，我们就想要它。

想象有一条跑步的小路，旁边有一道栅栏。我们要找的地方在栅栏的另一边。

我们的算法找到的第一条路径是沿着这条路径跑下去，跳过栅栏。我们找到的第二条路径是沿着路径的一部分，穿过大门，然后到达那个地点。我们不想仅仅因为我们已经知道我们可以通过跳过栅栏就可以到达那里而放弃使用大门的想法！

现在，在你的图片中，将从一个地点移动到另一个地点的成本放在沿着跑步路径、空地、穿过大门和跳过栅栏的合理成本上。手动运行算法，你会发现你首先发现你可以跳过栅栏，然后你真的想要使用门。