1

我目前正在使用 A* 寻路算法来计算无限网格上的路径（使用 Gridworld 中的 UnboundedGrid，AP CS 案例研究，如果对任何人有帮助的话）。一切都很好，除了因为末端节点完全被墙包围而没有有效路径的情况。正如预期的那样，算法继续无限搜索，永远找不到结束节点。

一个可能的解决方案是在整个寻路区域周围放置不可见的（如用户看不到但算法看到的）墙，确保开始节点、结束节点和所有墙节点都在这些范围内墙壁，有2-3个空格填充左右。就像是：

_________________________________
|                               |
|              S  |             |
|            _____|   _____     |
|                     | E |     |
|                     |___|     |
|_______________________________|

...想法是最终所有节点都将添加到封闭列表中，开放列表将变为空，此时我将知道不存在有效路径。

这似乎是解决问题的合理方法吗？有什么方法可能会出错吗？我知道另一种解决方案是同时从末端向后寻路，但这似乎可能很昂贵，特别是在末端节点没有那么紧密封闭的情况下。

4

4 回答 4

2

你不知道最终节点在哪里吗？如果这样做，请在执行算法之前检查它是否被包围。

于 2010-12-29T08:20:18.040 回答
1

另请参阅我对您的问题的评论。打字后，我想出了一个不错的解决方案。这是针对您不知道您的终端节点并且无法对您的终端节点的位置做任何事情的情况，如上所述。

你也可以是这样的：“我在我的领域找到了一个封闭的盒子，并且在x次之后没有路径，所以以y%的概率我可以说没有路径，并更新y%以随着时间的推移而增加，但从来没有达到 100%。

可能是一个很好的解决方案，它位于搜索区域的边界并且什么都不做。

于 2010-12-29T08:34:51.703 回答
0

我遇到了类似的问题，这就是我所做的：

  1. 运行n次迭代的算法，从 A 开始搜索 B。
  2. 运行n次迭代的算法，从 B 开始搜索 A。

如果任一运行确定其中一个或另一个位于完全隔离的区域（不再有开放节点），则搜索失败。否则，搜索将正常进行。

当然，这里的诀窍是为n提出一个好的值。我通过增加n进行了多次传递并缓存了结果（我的图表没有改变很多）。

于 2012-01-31T14:07:25.863 回答
0

您正在使用 A*，因此您应该能够对地形节点进行加权。将高得离谱的成本放在墙节点上。它必须大于任何可能路径的总成本。如果路径的最终成本大于边界成本，那么你必须通过一堵墙才能找到路径，所以它是无效的。A* 算法围绕高成本节点进行路由，因此除非必须，否则它不会穿过墙壁。

于 2012-01-31T14:23:21.023 回答