首先，我要感谢任何人花时间看这个 . 我们中的许多人都熟悉Dijkstra的算法，因而熟悉A * . 我在许多应用程序中使用过A *，但对于这种特殊情况，我很难想出一个算法 . 这种情况涉及找到转弯次数最少的路径 . 实际上，我甚至不关心“最短路径”，只关心转弯最少的路径！我正在使用上下左右网格，没有对角线，这意味着有许多可能的最短路径解决方案 . 例如，在一个5x5的网格中，左下方有一个启动器，右上角有一个启动器，我们可以做一个楼梯的情况，或者一直走到右边然后一直向上（对我来说更好！） .
使用A *你使用Cost = DistanceFromStart启发式（曼哈顿），我试图通过添加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”解决方案，但我不断获得未涵盖的案例 . 有没有人知道这样做的直观方法？再一次，我会尽我所能提出问题：
给定具有上下左右移动和障碍物的网格，我如何找到从A到B的最小转弯路径 . 我不需要保证最短距离 . 该应用程序是一个连接瓷砖的游戏机器人程序，只有当它们相距不到3圈时才能消除 . 再次感谢任何可以提供帮助的人！
2 回答
创建一个新的距离矩阵 . 对于位置i和j，如果它们在一条直线上（没有转弯），则设置距离（i，j）= 1 . 其余元素设置为无穷大 . 现在运行任何最短距离算法 .
我认为你需要在你的州中加入一个“方向” . 当你从1-> 2->到达时，你正面临'向上'，当你从'1' - > 2' - >到达时，你面对'正确' .
然后，您可以将改变方向的成本纳入“成本” . 也就是说，从一个州到另一个州的旅行费用 . 现在，当估计向右移动时，进入1-> 2->将考虑改变方向的成本，而1' - > 2' - >则不会 .
当你到达A *的'生成孩子'阶段时，你可能只是将'cost-so-far'增加1，即移动到邻居所需的网格数量 . 如果邻居对你当前位置的方向是！=当前方向，你还需要加1 .
首先，您可以使用一些特殊的面向方向，如OMNIDIRECTIONAL，这样从起始位置移动到任何方格都不会产生成本 .