问题:
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.
我尝试的解决方案:
- 运行从 (a,b) 到 (x,y) 的原始 A* 算法。
- 找到路径中经过 (x-1,) 或 (x+1,)(如果有)的最后一个坐标。
- 如果在该坐标平面中有一条从 * 到 y 的垂直直线,请修改路径以遵循该直线。
视觉演示:(从 S 到 E 的路径,其中 X 不可访问)
......S .....S
. X . X
. => .
. .
E E.
但是我不确定我的解决方案在某些情况下是否有效,即:
......S .....S
. X . X
.X ??? X.
. .
E E..
谁能想出解决这个问题的方法?
注意:A* 算法是通用的,除了将方向变化的数量考虑在内以减少结果路径中的转弯。
最佳答案
A* 实际上是 Dijkstra's algorithm 的知情版本,因此它实际上是设计的 [with admissible heuristic函数]找到所有顶点的最短路径[来自单一来源]。
您可以将与 (x,y)
相邻的所有图 block 定义为目标顶点 [A* 可以巧妙地处理多个目标],您还需要修改启发式函数,以给出可接受的任何目标节点的值。这可以通过简单地修改 h'(tile) = max { h(tile) - 1 , 0}
来完成 - 但在某些情况下,您可能有更好的方法来做到这一点。
建立以上后,我们可以对原A*进行如下修改:
- 运行 A*,直到找到目标瓦片的路径 [在目标瓦片扩展之后,
如上所述]。令路径的长度为
d
。 - 现在,以当前状态继续运行
A*
,直到最小值 开放节点的f(tile)
值严格大于d
。 你是 保证找到所有可通过长度为d
的路径从源到达的图 block ,具体来说 - 您将找到所有具有长度为d 的源的路径的目标图 block
。 [假设可接受的启发式函数]。 - 从所有这些图 block 中,您可以选择“首选的”并返回一个 他们的路径。如果没有找到首选的图 block ,则返回一个路径到 任意目标图 block 。
希望对您有所帮助!
关于algorithm - 寻路算法难度,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/10157411/