在访问某些顶点时在加权图中找到最短路径
Finding the shortest path in weighted graph while visiting certain vertices
我试图在无向加权图中找到从 A 到 Z 的最短路径。但是，生成的路径也应该经过一组 无序 顶点（我们只说 B、C 和 D）。
我还没有找到这个确切问题的任何答案，但我遇到了类似的问题，这些问题将问题定义为 NP-Hard（据我所知，并不是每个图都能真正解决）。
那么是否还有一种算法至少会尝试找到一条访问所有这些顶点的路径，并在用尽合理数量的选项后找不到路径时中断？
如果没有，我的替代方法是对这些必须访问的顶点进行排序。除了将路径拆分并为每个段（A->B、B->C 等）计算最佳路径之外，是否有更好的方法来查找路径？
给定一组顶点S和一个原始顶点v，您可以使用深度优先搜索对[=中的顶点进行排序22=]S从最近到最远v，也就是table的距离。
创建 table 实际上会为您提供一个仅由 S O(nm) 中的顶点组成的新图，其中 n 是图形的大小，m 是集合的大小 S.
您现在正在寻找通过这个新图的所有顶点的最短路径。因此，您的问题等同于那个较小图形上的旅行商问题。
请注意，通过 adding a dummy node between your starting and end nodes 执行旅行商算法的终点相当简单。
现在由您选择 known heuristic 以应用于较小的图表。
我试图在无向加权图中找到从 A 到 Z 的最短路径。但是，生成的路径也应该经过一组 无序 顶点（我们只说 B、C 和 D）。
我还没有找到这个确切问题的任何答案，但我遇到了类似的问题，这些问题将问题定义为 NP-Hard（据我所知，并不是每个图都能真正解决）。
那么是否还有一种算法至少会尝试找到一条访问所有这些顶点的路径，并在用尽合理数量的选项后找不到路径时中断？
如果没有，我的替代方法是对这些必须访问的顶点进行排序。除了将路径拆分并为每个段（A->B、B->C 等）计算最佳路径之外，是否有更好的方法来查找路径？
给定一组顶点S和一个原始顶点v，您可以使用深度优先搜索对[=中的顶点进行排序22=]S从最近到最远v，也就是table的距离。
创建 table 实际上会为您提供一个仅由 S O(nm) 中的顶点组成的新图，其中 n 是图形的大小，m 是集合的大小 S.
您现在正在寻找通过这个新图的所有顶点的最短路径。因此，您的问题等同于那个较小图形上的旅行商问题。
请注意，通过 adding a dummy node between your starting and end nodes 执行旅行商算法的终点相当简单。
现在由您选择 known heuristic 以应用于较小的图表。