algorithm - 寻路的扩展 - 最少转弯的路径

Question

我用过 A* (和 Dijkstra's algorithm )在许多应用程序中，但我无法找到具有最少转弯数 的路径，而路径长度无关紧要。我使用的是上下左右网格，没有对角线。

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 (*=wall, 0=empty, S=start, E =结束)

你会发现路径 S->1->2->+ 将给出与 s->1'->2'->+ 相同的成本>。到目前为止，它们都转了一圈，与 S 的距离相同，并且在同一曼哈顿。但是从 + 开始，如果我们选择了主要的 ' 路线，我们就不必转弯了。但是如果我们走 1 2 路线，我们必须右转(+1 成本)。因此，即使我们可能以 1 2 最先到达那里，它也不是最少转弯的路径。

我已经尝试过调整，比如让多个相同的方 block 同时进入优先级队列，这样它们都有机会(如果它们的值在堆中最小)和其他“hacky”解决方案，但不断收到案例那不包括在内。有没有一种直观的方法可以做到这一点？

谢谢!

Answer 1

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