algorithm - 寻路算法难度

Question

问题:

Modify the A* algorithm we optimized for fewer turns. The algorithm will now find a path from (a,b) to ANY TILE ADJACENT TO (x,y), where (x+1,y) or (x-1,y) are favored when possible.

我尝试的解决方案:

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* 算法是通用的，除了将方向变化的数量考虑在内以减少结果路径中的转弯。

Answer 1

A* 实际上是 Dijkstra's algorithm 的知情版本，因此它实际上是设计的 [with admissible heuristic函数]找到所有顶点的最短路径[来自单一来源]。

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

建立以上后，我们可以对原A*进行如下修改:

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

希望对您有所帮助!