转弯最少的最短路线
Shortest route with fewest turns
我需要生成最短路线。第一个满足我要求的解决方案是 Dijkstra 的算法，因此我实现了相同的 (Java)。后来只好修改实现生成最短路线"with least number of turns"。经过一番摸索之后，我想出了一个解决方案，尽管在现有的 Dijkstra 算法实现中添加了很多条件。现在我的问题是，有没有更好的方法来解决这个问题（比如，任何现有的算法已经这样做了）？我的解决方案包括在路线计算迭代中的每个节点中存储额外的转弯信息，并在回溯路线时使用相同的信息。
最终路径查找算法旨在找到成本最低的路径。成本的定义取决于场景。在一种情况下，成本可能是距离，但在其他情况下，它可能包括地形、坡度、通行费等。在您的情况下，建模 'shortest route with least number of turns' 的最简单方法是从距离和转弯次数中得出成本。换句话说，包括转弯成本。
例如，如果您使用 A* 算法，则两个节点之间的成本计算可能包括距离成本和额外成本（如果此移动需要改变方向）。如果不同的路径不需要改变方向，那么它的成本会更低，算法会选择该路径。
这里唯一棘手的事情是保留先前移动的上下文以检测转弯。在 A* 中，您通常会保留对前一个节点的引用，因此决定下一步是否需要转弯应该相当简单。
您不需要对 Dijkstra 进行任何回溯或实质性调整。只需为每个节点跟踪（如您所做的那样）当前到该节点的最短路径上的最少转弯次数。每当你放松边缘时，如果生成的路径与当前最短路线一样短，你会选择转弯最少的那条。
编辑：正如评论中指出的那样，这种方法忽略了这样一个事实，即所选路线的传入边缘的方向会影响后续路径的转弯数。这将通过在每个节点中存储最短距离+转弯 每个传入边 或 每个唯一传入角度 来解决（无论你如何测量） .
或者，为了减少对 Dijkstra 的修改，您可以预先修改图表：将每个节点拆分为每个传入边的一个节点（以便每个生成的节点只有一个原始节点的传入边） ，但复制所有传出边，以便每个结果节点都具有原始节点的所有传出边（每个传出边都必须指向边另一端节点的适当副本）。您可能会看到一些生成的节点有多个传入边，但在这种情况下，这些边另一端的节点都是同一原始节点的副本，因此代表 "same" 原始边 - 因此，每个传出边都可以明确地标记为该边是否表示该节点的转出（相对于节点的传入边）。请注意，原始图中的最佳路径将仍然存在于新图中（并且不会引入更好的路径）。现在，只需修改 Dijkstra 即可跟踪与每个节点的最短路径相关联的转弯数。每当从 u 到 v 的边松弛并且候选路径与您之前为 找到的最短路径一样短时v，比较u的圈数加上边的圈数（0或1取决于边是否构成圈）与v的回合计数，并将其用作决胜局。
我不知道，为什么没有其他人这么说，为什么有一个公认的答案。
您要解决的问题（即生成转弯次数最少的最短路径）是权重约束最短路径问题 的一个示例。
因此它是 NP-Complete，无法有效解决。
您可以找到讨论解决此问题的论文，例如http://web.stanford.edu/~shushman/math15_report.pdf
这是一个简单的启发式方法。正如其他人所指出的，启发式是 AStar 中的游戏。
if (Cost > CanMaxMove) Heuristic += 1000;
// for cost per grid pt typically 10 to 30
// Cost = PtCost + CostSoFar
// higher is worse (more costly)
您只需像往常一样在 AStar 中找到最佳路径，但会出现不合时宜的大幅度移动。正如所指出的，这是一个非常困难的问题，但在满足以下条件的情况下很容易解决：
Every turn a new path can and will be searched anyway: this is easily
believable, because until next turn circumstance can easily change. If
not, those are not really turns as we know them.
如果您不介意这种情况，只需执行上述代码段即可。对于所有“离开这个回合”的移动，启发式必须被相同的值打折并且不顺利（例如 Heuristic += (Cost - CanMove) * 100），即“这个回合”和“不是这个回合”之间必须有很大的差异。
我需要生成最短路线。第一个满足我要求的解决方案是 Dijkstra 的算法，因此我实现了相同的 (Java)。后来只好修改实现生成最短路线"with least number of turns"。经过一番摸索之后，我想出了一个解决方案，尽管在现有的 Dijkstra 算法实现中添加了很多条件。现在我的问题是，有没有更好的方法来解决这个问题（比如，任何现有的算法已经这样做了）？我的解决方案包括在路线计算迭代中的每个节点中存储额外的转弯信息，并在回溯路线时使用相同的信息。
最终路径查找算法旨在找到成本最低的路径。成本的定义取决于场景。在一种情况下，成本可能是距离，但在其他情况下，它可能包括地形、坡度、通行费等。在您的情况下，建模 'shortest route with least number of turns' 的最简单方法是从距离和转弯次数中得出成本。换句话说，包括转弯成本。
例如，如果您使用 A* 算法，则两个节点之间的成本计算可能包括距离成本和额外成本（如果此移动需要改变方向）。如果不同的路径不需要改变方向，那么它的成本会更低，算法会选择该路径。
这里唯一棘手的事情是保留先前移动的上下文以检测转弯。在 A* 中，您通常会保留对前一个节点的引用，因此决定下一步是否需要转弯应该相当简单。
您不需要对 Dijkstra 进行任何回溯或实质性调整。只需为每个节点跟踪（如您所做的那样）当前到该节点的最短路径上的最少转弯次数。每当你放松边缘时，如果生成的路径与当前最短路线一样短，你会选择转弯最少的那条。
编辑：正如评论中指出的那样，这种方法忽略了这样一个事实，即所选路线的传入边缘的方向会影响后续路径的转弯数。这将通过在每个节点中存储最短距离+转弯 每个传入边 或 每个唯一传入角度 来解决（无论你如何测量） .
或者，为了减少对 Dijkstra 的修改，您可以预先修改图表：将每个节点拆分为每个传入边的一个节点（以便每个生成的节点只有一个原始节点的传入边） ，但复制所有传出边，以便每个结果节点都具有原始节点的所有传出边（每个传出边都必须指向边另一端节点的适当副本）。您可能会看到一些生成的节点有多个传入边，但在这种情况下，这些边另一端的节点都是同一原始节点的副本，因此代表 "same" 原始边 - 因此，每个传出边都可以明确地标记为该边是否表示该节点的转出（相对于节点的传入边）。请注意，原始图中的最佳路径将仍然存在于新图中（并且不会引入更好的路径）。现在，只需修改 Dijkstra 即可跟踪与每个节点的最短路径相关联的转弯数。每当从 u 到 v 的边松弛并且候选路径与您之前为 找到的最短路径一样短时v，比较u的圈数加上边的圈数（0或1取决于边是否构成圈）与v的回合计数，并将其用作决胜局。
我不知道，为什么没有其他人这么说，为什么有一个公认的答案。
您要解决的问题（即生成转弯次数最少的最短路径）是权重约束最短路径问题 的一个示例。 因此它是 NP-Complete，无法有效解决。
您可以找到讨论解决此问题的论文，例如http://web.stanford.edu/~shushman/math15_report.pdf
这是一个简单的启发式方法。正如其他人所指出的，启发式是 AStar 中的游戏。
if (Cost > CanMaxMove) Heuristic += 1000;
// for cost per grid pt typically 10 to 30
// Cost = PtCost + CostSoFar
// higher is worse (more costly)
您只需像往常一样在 AStar 中找到最佳路径，但会出现不合时宜的大幅度移动。正如所指出的，这是一个非常困难的问题，但在满足以下条件的情况下很容易解决：
Every turn a new path can and will be searched anyway: this is easily believable, because until next turn circumstance can easily change. If not, those are not really turns as we know them.
如果您不介意这种情况，只需执行上述代码段即可。对于所有“离开这个回合”的移动，启发式必须被相同的值打折并且不顺利（例如 Heuristic += (Cost - CanMove) * 100），即“这个回合”和“不是这个回合”之间必须有很大的差异。