寻路扩展 - 最少拐弯路径

Question

寻路扩展 - 最少拐弯路径

algorithmmethodspath-findinga-starheuristics

4

我在许多应用程序中使用A*（和Dijkstra的算法），但我卡在了寻找拐点最少的路径上，而路径长度无关紧要。我正在使用上下左右网格，没有对角线。

A * 定义成本=从起点的距离+启发式(曼哈顿)，而我尝试通过添加numTurns成本来扩展它。这个方法在处理如下情况时非常完美：

| 0 0 0 0 0 * 0 0 | 0 0 1' 2' + 0 0 E | 0 0 S 1 2 * 0 0 | 0 0 0 0 0 * 0 0 | 0 0 0 0 0 * 0 0

（*=墙，0=空，S=起点，E=终点）

您会发现路径S->1->2->+与s->1'->2'->+的成本相同。它们都已经拐了一次弯，距离S相同，并且曼哈顿距离也相同。然而，从+开始，如果我们选择使用'路线，则无需拐弯。但是，如果我们选择使用1 2路线，则必须向右转（代价为+1）。因此，即使我们可能先到达那里，使用1 2不是最少拐弯的路径。

我尝试过调整，例如允许多个相同的方格同时在优先队列中，以便它们都有机会（如果它们在堆中的值是最小的），以及其他“hacky”解决方案，但仍然存在未覆盖的情况。是否有一种直观的方法来解决这个问题呢？

谢谢！

- user2045279

你找到解决方案了吗？我也遇到了同样的问题，但还没有找到合适的解决方案。 - dimayak

1

这是一篇学术论文，提供了一个算法。 http://arxiv.org/ftp/arxiv/papers/1003/1003.3536.pdf - user4397127

2个回答

0

我认为你需要在状态中加入“方向”。当你从1->2->+到达“+”时，你面对的是“上”，而当你从1'->2'->+到达“+”时，你面对的是“右”。

然后，你可以将改变方向的成本纳入到你的“cost-to-go”中。也就是说，从一个状态到另一个状态的旅行成本。现在，当估计向右移动时，1->2->+会考虑到改变方向的成本，而1'->2'->+则不会。

当你进入A*算法的“生成子节点”阶段时，你可能只会将“cost-so-far”增加1，即移动到邻居所需的网格单元数。如果邻居与你当前位置的方向不同，你还需要再加1。

对于起点，你可以使用一些特殊的朝向，比如全向型，这样从起始位置移动到任何一个方格都不会产生成本。

- AndyG

感谢您的快速回复，我期待着您进一步的解释。我的BoardSquares上有方向指示，如果我的最后一个移动是“右”，并且我再次向右移动，numTurns保持不变。但是，如果我向左、向下或向上移动，numTurns会迭代，并且curDirection将更改为其相应的值。问题是，除非我误解了您的解决方案，否则如果1 2路径首先到达+，并且选择+，则+将被锁定（关闭列表）。从那时起，任何进一步的计算都不会知道从未到达它的1'2'路径（无论成本是否相同）。 - user2045279

所以，即使在1 2右转会产生成本，而1' 2'不会，但意识到这一点的不是+，而是+右边的方块。当我们到达那里时，我认为回头已经太晚了（除非我们允许具有不同遗传背景的相同方块进入pqueue）。再次感谢您抽出时间与我一起查看此内容！ - user2045279

从1->2->+到达的'+'状态与从1'->2'->+到达的'+'状态并不相同。当您比较两个状态时，仅比较它们的x、y坐标是不够的，您还必须比较在这些坐标处面向的方向。这样，两个'+'状态都可以被添加到列表中，但成本不同。 - AndyG

我希望我能给你点赞，但我想我需要问更多的问题。其实你的解决方案和我的一样。事实证明，它之前没有起作用是因为我以各种方式批量调用了它。你知道，这个棋盘有近100个方块，所以我至少要调用50次寻路算法。我忘记了以各种方式重置方块，我没有清除我的各种数据结构等等。因此，错误似乎来自于寻路，但实际上是由于输入有缺陷。现在它似乎正在工作（手指交叉），我正在努力完成UI。 - user2045279

@user2045279：很高兴能帮忙。我希望你在找到最终解决方案后，能够编辑你的帖子并分享出来，这样未来的人们也可以从中受益！或许有一天你也能回答其他人的问题！ - AndyG

显示剩余2条评论

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- ElKamina · Accepted Answer

创建一个新的距离矩阵。对于位置i和j，如果它们在一条直线上（没有拐弯），则设置距离(i,j)=1。对于其余的元素设置为无穷大。现在在此上运行任何最短距离算法。