我如何重新计算一个封闭的节点来告诉我的算法可以这样返回?
你不这样做是因为它不好。最佳路径永远不会包括走进死胡同,然后又走回来!根据定义,这是次优路径。A* 算法找到最优路径。
如果我确实告诉我的算法返回到它自己,是什么阻止它再次返回到它刚刚来自的更好的节点;有效地反复在两个节点之间返回。
没有什么能阻止它。这就是为什么做你所描述的事情是一个坏主意。如果你这样做的时候很痛,那就不要这样做。
我正在使用的启发式方法......
看起来很乱。
G 是从起点到目标的曼哈顿距离,H 是从当前点到目标的曼哈顿距离,F 是它们的总和。
首先,如果启发式是针对不允许对角线移动的方形网格,曼哈顿距离只是一个有效的度量。你允许对角线移动吗?如果你这样做了,那么这个启发式是错误的。请记住,启发式方法需要低估成本。如果你可以在任何地方沿对角线移动,那么曼哈顿距离就高估了成本。考虑改为使用欧几里得度量。
其次,从起点到目标的距离是一个常数,那么它是如何相关的,你为什么要把它加到任何东西上呢?看起来你说的是每条路径的成本都会增加从起点到目标的距离,这没有任何意义。
根据您的问题,我认为您不了解该算法及其工作原理。我的建议是在尝试实现它之前了解该算法的工作原理。这是英文的算法:
The closed set is an empty set of points.
The queue is an empty queue of paths, ordered by path cost.
Enqueue a path from the start to the start with zero cost.
START:
If the queue is empty, then there is no solution.
The current path is the cheapest path in the queue.
Remove that path from the queue.
If the last step on the current path is closed then
the current path is necessarily bad. (Do you see why?)
Discard it and go back to the START of the loop.
Otherwise, if the last step on the current path is the destination then
the current path is the optimal path to the destination, so we're done.
Otherwise, we have the cheapest path *to the last
point in that path*. (Do you see why?)
Therefore, every other path that could possibly go through that point is worse.
Therefore, close off that point. Add it to the closed set so that we can
automatically discard any future path that goes through that point.
For each possible direction from the last point of the current path,
make a new path that extends the current path in that direction.
The estimated cost of that new path is the known cost to get
to its end from the start, plus the estimated cost to get from
its end to the destination.
Enqueue the new path with that cost.
Go back to the START of the loop.
那有意义吗?