路径规划算法难度

Question

问题:

修改我们优化过的A *算法，使其少转弯。 该算法现在将查找从（a，b）到任何与（x，y）相邻的TILE的路径，其中在可能的情况下偏爱（x + 1，y）或（x-1，y）。

我的尝试解决方案:

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

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

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

然而，我不确定我的解决方案是否在某些情况下有效，例如：

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

你有没有想过解决这个问题的方法？

注意：A*算法是通用的，除了考虑方向改变的数量以更喜欢结果路径上的转弯较少。

- whats canasta

---

“尽可能优先”是什么意思？这是否意味着，如果到（x+1，y）和（x，y+1）有相等长度的路径，则必须找到通往（x+1，y）的路径？还是意味着，即使更长，也必须找到通往（x+1，y）的路径？此外，“相邻”是什么意思？（x+1，y+1）是相邻的吗？ - btilly

尽可能选择最短路径时优先考虑。相邻不包括对角线。 - whats canasta

我的朋友建议：1. 查找返回路径是否最后经过x+1或x-1平面。2. 从起点运行A*到(x+1,y)或(x-1,y)（哪一侧更近就选哪一侧）。如果结果路径更短，则返回该路径。根据我目前的测试，这似乎给出了正确的解决方案，但基本上需要两次运行算法。不知道是否有更优雅的方法。 - whats canasta

Answer 1

A*算法实际上是Dijkstra算法的一个启发式版本，因此它被设计成使用可接受的启发式函数来查找从单个源点到所有顶点的最短路径。

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

在确定了上述内容之后，我们可以得出对原始A*算法的以下修改：

1. 运行A*，直到找到一条通往目标瓦片的路径[在上述目标瓦片扩展后]。让路径长度为d。
2. 现在，继续使用当前状态运行A*，直到开放节点的最小f(瓦片)值严格大于d。您保证会找到所有从源头可达的路径长度为d的瓦片，特别地 - 您将找到所有源头到目标瓦片的路径长度为d的目标瓦片。【假设启发式函数是可接受的】。
3. 从所有这些瓦片中，您可以选择“首选项”，并返回到它们的路径。如果没有找到首选瓷砖，则返回到任意目标瓷砖的路径。

希望能对您有所帮助！

- amit

---

谢谢您的建议，我需要仔细思考一下，看看能否让它起作用。 - whats canasta

Answer 2

修改你的启发函数，稍微提升点(x+1,y)和点(x-1,y)的分数。然后，如果你离完成路径只有2步，优先选择这两个点来打破平局。

- btilly