3

问题：

修改我们针对更少转弯优化的 A* 算法。该算法现在将找到从 (a,b) 到与 (x,y) 相邻的任何 TILE 的路径，其中 (x+1,y) 或 (x-1,y) 在可能的情况下受到青睐。

我尝试的解决方案：

  1. 从 (a,b) 到 (x,y) 运行原始 A* 算法。
  2. 找到通过 (x-1, ) 或 (x+1, ) 的路径中的最后一个坐标（如果有）。
  3. 如果在该坐标平面中有一条从 * 到 y 的可访问的垂直线，则修改路径以遵循该线。

视觉演示：（从 S 到 E 的路径，其中 X 无法访问）

......S           .....S  
.     X           .    X
.          =>     .     
.                 .
E                E.

但是我不确定我的解决方案在某些情况下是否有效，即：

......S            .....S  
.     X            .    X
.X        ???     X.     
.                  .
E                E..

谁能想到这个问题的解决方案？

注意：A* 算法是通用的，除了考虑方向变化的数量以在结果路径中减少转弯。

4

2 回答 2

2

A* 实际上是Dijkstra 算法的一个知情版本，因此它实际上被设计为 [具有可接受的启发式函数] 以找到[来自单一来源] 的所有顶点的最短路径。

您可以将相邻的所有图块定义(x,y)为目标顶点[A* 可以整齐地处理多个目标]，并且您还需要修改启发式函数，为任何目标节点提供可接受的值。这可以通过简单的修改来完成h'(tile) = max { h(tile) - 1 , 0}- 但在某些情况下，您可能有更好的方法来做到这一点。

建立上述内容后，我们可以对原始 A* 进行以下修改：

  1. 运行 A*，直到找到目标图块的路径 [在目标图块扩展之后，如上所述]。设路径长度为d。
  2. 现在，继续以A*当前状态运行，直到 f(tile)开放节点的最小值严格大于d。您可以保证找到所有可以通过长度路径从源到达的图块，d特别是 - 您将找到所有具有从长度源路径的目标图块d。[假设可接受的启发式函数]。
  3. 从所有这些图块中，您可以选择“首选图块”并返回它们的路径。如果未找到首选图块，则返回任意目标图块的路径。

我希望这会有所帮助！

于 2012-04-14T21:45:53.663 回答
0

修改您的启发式函数以稍微提高点(x+1,y)和(x-1,y). 然后，如果您距离完成路径还有 2 步，则将打破平局，以支持这 2 点。

于 2012-04-15T22:17:56.897 回答