遍历所需边列表的最短路径 [英] Shortest path that traverses a list of required edges

问题描述

我有一个有向图，如下所示：

I have a directed graph, that looks like this:

我想找到从 Start到End 的最便宜的路径，其中橙色虚线都是该路径的必需项是有效的。

I want to find the cheapest path from Start to End where the orange dotted lines are all required for the path to be valid.

自然最短的路径是：开始-> A-> B->结束，结果成本为5，但是我们没有满足了所有要求的边缘访问。

The natural shortest path would be: Start -> A -> B -> End with the resultant cost = 5, but we have not met all required edge visits.

我要查找的路径（通过一般解决方案）是开始-> A-> B-> C-> D-> B->结束，其中费用= 7，我们已经满足了所有必需的边缘访问。

The path I want to find (via a general solution) is Start -> A -> B -> C -> D -> B -> End where the cost = 7 and we have met all required edge visits.

有人对如何要求这种边缘遍历有任何想法吗？

Does anyone have any thoughts on how to require such edge traversals?

推荐答案

让 R 为所需边的集合， F = | R |。假设 G 是输入图， t （分别是 s ）是所请求路径的起点（终点）。

Let R be the set of required edges and F = |R|. Let G be the input graph, t (resp. s) the starting (resp. ending) point of the requested path.

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

The first step is to create another graph. This graph will have exactly F+2 vertices:

• R中的每个边一个


• 一个要计算的路径的起点 t


• 一个终点的<要计算路径的em> s

• One for each edge in R
• One for the starting point t of the path you want to compute
• One for the ending point s of the path you want to compute

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

To create this graph, you will have to do the following:

1. 从 G 中删除 R 中的每个边。


2. 对于 R 中的每个边 E =（ b，e ）：
   

1. Remove every edge in R from G.
2. For each edge E = (b,e) in R:

1. 计算从 t 到 b 的最短路径，以及从 e 到 s 的最短路径。如果存在，则在新图中添加一条将 s 链接到 E 的边，权衡相关最短路径的长度。


2. 对于每个边 R \ { E }中的 E' =（ b'，e'） ：
   

1. Compute the shortest path from t to b and the shortest path from e to s. If they exist, add an edge linking s to E in the "new graph", weighing the length of the related shortest path.
2. For each edge E' = (b', e') in R \ {E}:

1. 计算从 e 到 b'的最短路径。如果存在，则在新图中添加从 E 到 E’的边，权衡最短路径的长度。将计算出的路径作为有效载荷附加到相关事件边缘。


2. 将计算出的路径作为有效载荷附加到该边缘

1. Compute the shortest path from e to b'. If it exists, add an edge from E to E' in the new graph, weighing the length of that shortest path. Attach the computed paths as payload to the relevent edges.
2. Attach the computed path as a payload to that edge

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

The complexity to build this graph is O((F+2)².(E+V).log(V)) where E (resp. V) is the number of edges (resp. vertices) in the original graph.

从这一点出发，我们必须在新创建的图中找到最短的<哈密顿路径。不幸的是，这个任务是一个难题。我们没有探索所有可能的道路的更好方法。但这并不意味着我们不能巧妙地做到这一点。

From this point, we have to find the shortest Hamiltonian Path in the newly created graph. Unfortunately, this task is a hard problem. We have no better way than exploring every possible path. But that doesn't mean we can't do it cleverly.

我们将使用回溯进行搜索。我们可以通过维护两个集合来实现此目的：

We will perform the search using backtracking. We can achieve this by maintaining two sets:

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


• 当前未知顶点的列表： U （ U 对于 Uknown ）

• The list of currently explored vertices: K (K for Known)
• The list of currently unknown vertices: U (U for Uknown)

在挖掘算法定义之前，这里是主要思想。除了探索新图中可能路径的整个空间之外，我们别无选择。在每一步中，我们都必须做出决定：下一步要走哪一条边？这导致一系列决策，直到我们无法移动或到达 s 为止。但是，现在我们需要返回并取消决策，看看是否可以通过改变方向来做得更好。要取消决策，我们将像这样进行操作：

Before digging in the algorithm definition, here are the main ideas. We cannot do anything else than exploring the whole space of possible paths in the new graph. At each step, we have to make a decision: which edge do we take next? This leads to a sequence of decisions until we cannot move anymore or we reached s. But now we need to go back and cancel decisions to see if we can do better by changing a direction. To cancel decisions we proceed like this:

• 每次卡住（或找到路径）时，我们都会取消上一次做出的决定


• 每次我们在某个时候做出决定时，我们都会跟踪哪个决定，因此当回到这一点时，我们知道不要做出相同的决定，而是探索其他决定。可用。


• 我们之所以陷入困境，是因为：
  
  
  
  • 我们找到了一条路径。
  
  
  • 我们无法继续前进（没有我们可以探索的边缘，或者我们可以采取的唯一方法会使当前部分路径增加太多-它的长度变得比找到的当前最佳路径的长度高。）
  
  
  • Every time we are stuck (or found a path), we cancel the last decision we made
  • Each time we take a decision at some point, we keep track of which decision, so when we get back to this point, we know not to take that very same decision and explore the others that are available.
  • We can be stuck because:
    • We found a path.
    • We cannot move further (there is no edge we can explore or the only one we could take increases the current partial path too much -- its length becomes higher than the length of the current best path found).

    最终算法可以用这种方式总结：（我给出了一个迭代实现，可以找到一个递归实现一点点更容易和清楚）

    The final algorithm can be summed up in this fashion: (I give an iterative implementation, one can find a recursive implementation a tad easier and clearer)

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

    Let K ← [], L[0..R+1] ← [] and U ← V (where V is the set of every vertex in the working graph minus the starting and ending vertices t and s). Finally let l ← i ← 0 and best_path_length ← ∞ and best_path ← []

    而（ i ≥0）：

    
    
    1. 而 U ≠ []
       
    
    
    1. c ← U.popFront（）（我们取U头）
    
    
    2. L [i] .pushBack（c）
    
    
    3. 如果 i == R + 1 AND（<< c $ c> l ==重量（ cur_path.back（）， s ）+ l ）< 最佳路径长度：
       
    1. c ← U.popFront() (we take the head of U)
    2. L[i].pushBack(c)
    3. If i == R+1 AND (l == weight(cur_path.back(), s) + l) < best_path_length:
    
    
    1. 最佳路径长度← l
    
    
    2. 最佳路径← cur_path
    
    
    1. best_path_length ← l
    2. best_path ← cur_path

  
  
  • 如果 K.tail（）和 c 之间存在边e，并且权重（e） + l < best_path_length ：（如果 K 为空，则替换 K.tail（）和前一条语句中的 t ）
    

  • If there is an edge e between K.tail() and c, and weight(e) + l < best_path_length: (if K is empty, then replace K.tail() with t in the previous statement)
    
    
    1. K.pushBack（c）
    
    
    2. i ← i +1
    
    
    3. l ←重量（e） + l
    
    
    4. cur_path.pushBack（c）
    
    
    1. K.pushBack(c)
    2. i ← i+1
    3. l ← weight(e) + l
    4. cur_path.pushBack(c)

  
  

  
  

  • 在 U L [i] c>
  
  
  • L [i] ← []
  
  
  • i ← i -1
  
  
  • cur_path.popBack（）
  
  
  • Concatenate L[i] at the end of U
  • L[i] ← []
  • i ← i-1
  • cur_path.popBack()

  在while循环结束时（ while（i≥0）），最佳路径将拥有最佳路径（在新图中）。从那里开始，您只需要获取边缘的有效载荷即可在原始图形中重建路径。

  At the end of the while loop (while (i ≥ 0)), best_path will hold the best path (in the new graph). From there you just have to get the edges' payload to rebuild the path in the original graph.

  这篇关于遍历所需边列表的最短路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！