穿过一系列必须边的最短路径

Question

我有一张有向图，长这样：

我想找到从起点到终点的最便宜路径，在此路径中橙色虚线表示必须经过的边。

自然的最短路径是： 起点 -> A -> B -> 终点，路径代价=5，但是我们没有经过所有必须的边。

我想要通过通用解决方案找到的路径是：起点 -> A -> B -> C -> D -> B -> 终点，路径代价=7且我们经过了所有必须的边。

大家有什么想法可以实现这种遍历边的需求吗？

- user1460739

---

所以这是最短步行路线，而不是路径，对吗？ - Juan Lopes

一个单独的遍历是否可以覆盖所有边缘？（例如，如果没有边缘DB会怎样？） - j_random_hacker

@JuanLopes，鉴于在这个例子中您要遍历1个节点2次，它就可以被称为一条路径，而不仅仅是一条路径。我认为所有的例子实际上都会遍历一些节点> 1x。 - user1460739

@j_random_hacker 不能保证一次遍历可以覆盖所有的边。我认为这是问题中最困难的部分。 - user1460739

在最一般的形式下，这个问题是NP难的。我们能对图做出任何假设吗？证明：如果你从旅行商问题的一个实例开始，你可以将每个节点分成两个节点对：一个带有入边，一个带有出边。在这些节点对之间创建一条边，并要求该边成为解的一部分。然后你就有了这个问题的一个实例，所以如果你能在多项式时间内解决它，你可能会赢得巡回奖。 - Tobber

Answer 1

让R成为所需边的集合，F=|R|。让G成为输入图形，t（分别是s）所请求路径的起始点（分别是结束点）。

---

预处理：一堆Dijkstra算法运行...

第一步是创建另一个图形。此图形将恰好具有F+2个顶点：

• 每个R中的边缘都有一个
• 要计算的路径的起点t
• 要计算的路径的终点s

要创建此图形，您需要执行以下操作：

1. 从G中删除R中的每个边缘。
2. 对于R中的每个边缘E = (b,e)：
   1. 计算从t到b的最短路径和从e到s的最短路径。如果存在，请在“新图形”中添加连接s到E的边缘，称重相关最短路径的长度。
   2. 对于R\ {E}中的每个边缘E' = (b'，e')：
      1. 计算从e到b'的最短路径。如果存在，请在新图形中从E到E'添加一条边，称量该最短路径的长度。将计算出的路径作为有效负载附加到相关边缘。
      2. 将计算出的路径作为有效负载附加到该边缘

构建此图的复杂度为O((F+2)².(E+V).log(V))其中E（分别是原始图中的边缘数（顶点））。

---

详尽搜索最佳路径

从这一点开始，我们必须在新创建的图形中找到最短的哈密顿路径。不幸的是，这项任务是一个困难的问题。我们没有比探索每种可能性更好的方法。但这并不意味着我们不能聪明地做到这一点。

我们将使用回溯执行搜索。我们可以通过维护两个集合来实现这一点：

• K（已知）：当前已经探索的顶点列表
• U（未知）：当前未知的顶点列表

在深入算法定义之前，让我们先了解一些主要思路。在新图中，我们除了探索所有可能路径的整个空间以外，别无他法。在每一步，我们都必须做出一个决定：接下来应该选择哪条边？这就导致一系列的决策，直到我们无法再移动或者到达了s。但现在我们需要回头并撤销一些决策，看看是否可以通过改变方向来做得更好。为了取消决策，我们按照以下步骤进行：

• 每次卡住（或找到一条路径）时，我们会取消最后一次决策
• 每次在某一点上做出决策时，我们记录下哪个决策，因此当我们回到这个点时，我们知道不要再做同样的决策，而是探索其他可用的决策。
• 我们可能会卡住，因为：
  • 我们找到了一条路径。
  • 我们无法再前进（没有边可供我们探索，或者我们唯一可以选择的边会使当前部分路径的长度增加太多——它的长度变得比找到的当前最佳路径的长度更长）。

最终算法可以概括为以下方式：（我提供了一种迭代实现，大家可以找到稍微更容易、更清晰一些的递归实现）

令K ← []，L[0..R+1] ← []和U ← V（其中V是工作图中每个顶点减去起始和结束顶点t和s的集合）。最后让l←i←0和best_path_length←∞和best_path←[]

当(i ≥ 0)时：

1. 当 U 不等于 [] 时
   1. c ← U.popFront()（我们取出 U 的头部）
   2. L[i].pushBack(c)
   3. 如果 i == R+1 并且 (l 等于 cur_path.back() 到 s 的距离加上 l) 小于 best_path_length：
      1. best_path_length ← l
      2. best_path ← cur_path
   4. 如果 K.tail() 和 c 之间有一条边 e，并且 weight(e) + l 小于 best_path_length：（如果 K 是空的，则在上述语句中将 K.tail() 替换为 t）
      1. K.pushBack(c)
      2. i ← i+1
      3. l ← weight(e) + l
      4. cur_path.pushBack(c)
2. 将 L[i] 连接到 U 的末尾
3. L[i] ← []
4. i ← i-1
5. cur_path.popBack()

在 while 循环的末尾（while (i ≥ 0)），best_path 将保存最佳路径（在新图中）。从那里，您只需要获取边上的负载以在原始图中重建路径。

- Rerito

---

对于关系 R 中的每条边 E = (b,e)：-- 但是最初 R 中没有边，因此这将不执行任何次数。你是指“在 G 中”吗？ - j_random_hacker

@j_random_hacker 我将R定义为必需边的集合。因此，R不会为空！ - Rerito

抱歉，我把 R 和新图形搞混了！ - j_random_hacker

感谢您的详细回复。我会采用这个方案并在编码时告诉您我的进展。 - user1460739