algorithm - 在有向无环图中，找到路径的权重是包含路径的有向边的权重之和

Question

给定一个有向无环图 G = (V,E)。每个有向边 e ∈ E 都有与之关联的权重 w_e。给定两个顶点 s,t ∈ V，使得 s 没有入边且 t 没有出边，我们感兴趣的是从 s 开始到 t 结束的最大权重有向路径。路径的权重是包含路径的有向边的权重之和。 (如果其中没有有向循环，则有向图是无环的。)

如何使用动态规划技术解决它？我已经被困了一段时间，感谢任何提示:D

Answer 1

这里的关键是理解“动态规划”只是意味着对于某些函数 f(x)，对于某些不同的输入 x 重复执行 f 会导致不同的结果或执行路径。根据这个定义，我们可以将缓存视为动态规划的一个实例。

那么让我们从没有动态规划的实现开始。使用回溯，我们可以执行从 s 开始到 t 结束的深度优先(这在后面很重要)遍历集。

let P(a,b) be a path from a->b
let w(p) be the total weight of some path p
let K be the exhaustive set of P(s,t) // a.k.a every path that exists

// Returns Max(p) p  ∈ K
function findMaxPath(G)
    return findMaxPath(s)

// Returns Max(P(n, t))
function findMaxPath(n)
   if (n === t)
      return an empty path // we are already at the target
   declare p = null
   for each e of n // every outgoing edge
     let q = G(n, e)
     let l = findMaxPath(q) // get the maximum path from the neighbor indice to t
     if (l == null) continue
     l = e + l // prepend the outgoing end to the max path of the child node
     if (w(l) > w(p)) p = l // this is most expensive outgoing end that eventually reaches t
   return p // return null if we can't reach t

这个解决方案的问题是它真的很慢。特别是，您最终会重新计算很多路径。拿下图:

在从 P(s, t) 计算路径的过程中，您最终会为每个 n 执行以下次数的 findMaxPath(n)

• 找到最大路径 1
• 找到最大路径(a) 1
• 找到最大路径(b) 1
• 找到最大路径(c) 1
• 找到最大路径(d) 3
• 找到最大路径(e) 3
• 找到最大路径(f) 3
• 找到最大路径(g) 3
• findMaxPath(h) 9(哇!)

在这个例子中，findMaxPath(h) 必须计算 9 次，这个数字在更复杂的拓扑中会急剧增加(这个是相当微不足道的)。因此，为了增加执行时间，我们可以跟踪对 findMaxPath(n) 调用的“缓存”。这是“动态的”，因为函数的执行路径随着时间的推移而变化，具有相同的变量输入。

let P(a,b) be a path from a->b
let w(p) be the total weight of some path p
let K(n) be the exhaustive set of P(n,t) // a.k.a every path that exists
let C be a cache of Max(w(p)) p ∈ K(n)
// Returns Max(w(p)) p ∈ K(s)
function findMaxPath(G)
    return findMaxPath(s)

// Returns Max(P(n, t))
function findMaxPath(n)
   if exists C[n]
     return C[n] // we already know the most expensive path from n->t
   if (n === t)
      return an empty path // we are already at the target
   declare p = null
   for each e of n // every outgoing edge
     let q = G(n, e)
     let l = findMaxPath(q) // get the maximum path from the neighbor indice to t
     if (l == null) continue
     l = e + l // prepend the outgoing end to the max path of the child node
     if (w(l) > w(p)) p = l // this is most expensive outgoing end that eventually reaches t
   C[n] = p
   return p // return null if we can't reach t

这为我们提供了 16/25 的总缓存“命中率”，使运行时间大大加快