В Направленном ациклическом графе, найти вес пути - это сумма весов направленных ребер, составляющих путь

Question

Вам дан ориентированный ациклический граф G = (V, E). С каждым направленным ребром e ∈ E связан вес w_e. Для двух вершин s, t ∈ V, таких что s не имеет входящего ребра, а t не имеет исходящего ребра, нас интересует путь, ориентированный на максимальный вес, который начинается в s и заканчивается в t. Вес пути - это сумма весов направленных ребер, составляющих путь. (Ориентированный граф является ациклическим, если в нем нет направленных циклов.)

Как мне решить эту проблему с помощью методов динамического программирования? Я застрял на некоторое время, любые советы приветствуются: D

Answer 1

Ключевым моментом здесь является понимание того, что «динамическое программирование» просто означает, что для некоторой функции f (x) любое повторное выполнение f для некоторого отдельного ввода x приводит либо к другому результату, либо к пути выполнения. Из этого определения мы можем считать кэширование экземпляром динамического программирования.

Итак, начнем с реализации без динамического программирования. С помощью обратного отслеживания мы можем выполнить ПЕРВЫЙ ГЛУБИННЫЙ (это будет важно позже) набор обходов, начиная с 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), вы в конечном итоге выполняете findMaxPath (n) следующие времена для каждого n

• findMaxPath (s) 1
• findMaxPath (a) 1
• findMaxPath (b) 1
• findMaxPath (c) 1
• findMaxPath (d) 3
• findMaxPath (e) 3
• findMaxPath (f) 3
• findMaxPath (г) 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, что значительно ускоряет время выполнения