是否可以修改A *以返回最短路径 with the least number of turns ？
一个复杂因素：节点不能再仅仅通过它们的位置来区分，因为它们的父节点与确定未来转弯相关，因此它们也必须具有与它们相关联的方向 .
但我遇到的主要问题是如何将轮数转换为部分路径成本（g） . 如果我乘以乘以（t）的匝数，奇怪的事情就会发生：在接近末端的N转弯的较长路径优于较短的路径，在开始附近有N圈 .
我正在考虑的另一个不太理想的解决方案是：在计算最短路径后，我可以运行第二次A *迭代（使用不同的路径成本公式），此时间限制在最短路径的x / y范围内，并返回转弯最少的路径 . 还有其他想法吗？
2 回答
搜索的当前“状态”实际上由两个部分表示：您所在的节点以及您所面对的方向 . 你想要的是将每个状态分成不同的节点 .
因此，对于初始图中的每个节点，将其拆分为E个单独的节点，其中E是传入边的数量 . 这些新节点中的每一个都代表旧节点，但面向不同的方向 . 这些新节点的传出边缘将与旧的传出边缘相同，但权重不同 . 如果旧的重量是
w，那么......如果边缘不代表转弯，也可以设置新的重量
w如果边缘确实表示转弯，请设置新的重量
w + ε，其中ε是一个明显小于最小重量的数字 .然后只做一个正常的A *搜索 . 由于没有任何权重减少，您的启发式方法仍然是admissible，因此您仍然可以使用相同的启发式方法 .
如果你真的想最小化转弯次数（而不是在转弯和路径长度之间找到一个很好的权衡），那么为什么不通过为无障碍直线连接的每对节点添加边缘来转换问题空间;这些是你可以在没有转弯的情况下旅行的对 . 每个节点有O（n）个这样的边，所以新的图就边缘而言是O（n3） . 这使得A *解决方案在时间方面与O（n3）一样多 .
对于A *，曼哈顿距离可能是一个很好的启发式算法 .