我需要生成最短路径。第一个适合我需求的解决方案是Dijkstra的算法，因此我实现了相同的（Java）后来，我不得不修改实现以生成“最少圈数”的最短路径经过一些挠头之后，我想出了一个解决方案，尽管在现有的Dijkstra算法实现中加入了很多条件。现在我的疑问是，是否有更好的方法来解决这个问题（比如，已经存在的任何算法）？我的解决方案包括在路线计算迭代中在每个节点中存储额外的转弯信息，并在回溯路线时使用相同的信息。
最佳答案
最终，路径发现算法被设计成寻找成本最低的路径成本的定义取决于情景在一种情况下，成本可能是距离，但在另一种情况下，成本可能包括地形、坡度、通行费等。在您的情况下，建模“转弯次数最少的最短路线”的最简单方法是从距离和转弯次数中得出成本。换言之，包括车削成本。
例如，如果使用A*算法，则两个节点之间的成本计算可能包括距离成本，如果此移动需要更改方向，则包括额外成本如果一条不同的路径不需要改变方向，那么它将降低成本，算法将选择该路径。
这里唯一棘手的事情是保持前面动作的上下文以检测转弯。在A*中，通常会保留对上一个节点的引用，因此决定下一步是否需要转弯应该相当简单。
关于java - 转弯最少的最短路线，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/35168676/