4

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

A* 定义，我试图通过增加成本来扩展它。在我遇到这样的情况之前，这非常有效：Cost = DistanceFromStart + Heuristic(Manhattan)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”解决方案，但不断收到不t 覆盖。有没有直观的方法来做到这一点？

谢谢！

4

2 回答 2

3

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

于 2013-02-06T03:12:00.267 回答
0

我认为您需要将“方向”纳入您的状态。当您从 1->2->+ 到达“+”时，您面向“向上”，当您从 1'->2'->+ 到达“+”时，您面向“右”。

然后，您可以将改变方向的成本纳入您的“执行成本”。也就是说，从一个州到另一个州的旅行费用。现在，在估计向右移动时，走 1->2->+ 将考虑改变方向的成本，而 1'->2'->+ 则不会。

当您进入 A* 的“生成孩子”阶段时，您可能只会将“迄今为止的成本”增加 1，即移动到邻居所需的网格单元数。如果邻居到您当前位置的方向是 != 到您当前方向，您还需要加 1。

首先，您可以使用一些特殊的朝向，例如 OMNIDIRECTIONAL，这样从起始位置移动到任何方格都不会产生成本。

于 2013-02-06T03:11:56.450 回答