Stack Overflow 社区！
我正在研究 3x3 网格内的寻路问题，其中每个单元格都有基于其坐标的可变成本，并且进行 90 度转弯会产生额外成本。目标是找到该网格中两点之间的最短路径，同时考虑单元成本和转弯惩罚。
以下是我正在使用的具体规则：
Cell Cost：如果(x+y)%2==0，则Cell Cost为2；否则为 1。 转弯成本：如果路径进行 90 度转弯，则转弯成本等于转弯发生的单元格的成本。
障碍：有些细胞是障碍，不能成为路径的一部分。
为了解决这个问题，我尝试使用 Dijkstra 算法。我还定义了一个函数来检测路径中的转弯。该函数跟踪当前单元格的父单元、当前单元格本身以及下一个单元格以确定是否进行转弯。
尽管如此设置，我发现该算法并不总是返回最佳路径。看来我合并转弯成本的方法可能有缺陷，或者也许有更好的方法来为 Dijkstra 算法构建这个问题。
问题：
如何准确地将90度转弯的成本纳入寻路算法中？
我可以对当前的实施进行任何改进或调整以确保它找到最佳路径吗？ 我非常感谢任何关于如何应对这一挑战的指导、建议或见解。预先感谢您的帮助！
为了纳入车削成本的概念，您可以复制所有单元（节点）。我们可以将这些集合称为两个planes，就好像我们有一个三维表示一样。两个平面都对应于一个遍历轴（南北向，相对于东西向），并且对应的平面仅具有沿各自轴的连接边。只要你向“北”走，你就停留在图表的“南北平面”上。如果你想转弯，你不能在那个平面上转弯，因为没有这样的边缘。但相反，每个单元都通过一条边连接到另一个平面上的“副本”。 那个边缘代表转弯。在抵达飞机上，您现在可以向东或向西行驶，因为那里有相应的边缘。
因此，本质上，您构建了一个新图，其节点数是节点数量的两倍，并且其边在节点上分开。创建额外的边来表示转弯。
该图不再有特殊规则：它是标准加权图，您可以对其应用标准 Dijkstra 搜索。请记住，目标现在由两个节点组成：如果达到这两个节点中的任何一个，则目标就实现了。对于起始节点也是如此：您现在实际上可以从两个节点开始，假设选择第一次水平或垂直移动不被视为“转弯”。但这也不是问题：使用 Dijkstra，您可以在循环开始时将这两个节点放入队列中。