Блог

Я читаю о динамическом программировании в книге Кормена и т. Д. По алгоритмам. ниже приведен текст из книги

Предположим, у нас есть автомобильный завод с двумя линиями assesmly, называемыми строкой 1 и строкой 2. Мы должны определить самое быстрое время, чтобы полностью собрать шасси.

Конечная цель — определить максимально быстрое время прохождения шасси через завод, которое мы обозначаем через Fn. Шасси должно пройти весь путь через станцию «n» либо на линии 1, либо на линии 2, а затем до выхода с завода. Поскольку более быстрый из этих способов является самым быстрым способом на всей фабрике, мы имеем

 Fn = min(f1[n]   x1, f2[n] x2) ---------------- Eq1

Above x1 and x2 final additional time for comming out from line 1 and line 2
  

У меня есть следующие рекуррентные уравнения. Рассмотрим следующие Eq2.

 f1[j]  = e1   a1,1                                    if j = 1
             min(f1[j-1]   a1,j, f2[j-1]   t2,j-1   a1,j  if j >= 2

f2[j]  = e2   a2,1                                    if j = 1
             min(f2[j-1]   a2,j, f1[j-1]   t1,j-1   a2,j  if j >= 2
  

Пусть Ri(j) — количество ссылок, сделанных на fi[j] в рекурсивном алгоритме.

Из уравнения R1 (n) = R2 (n) = 1

Из уравнения 2 выше мы имеем

 R1(j) = R2(j) = R1(j 1)   R2(j 1)  for j = 1, 2, ...n-1
  

Мой вопрос в том, как автор пришел с R (n) = 1, потому что обычно у нас базовый вариант равен 0, а не n, вот тогда как мы будем писать рекурсивные функции в коде
, например, в коде C?

Другой вопрос в том, как автор придумал R1 (j) и R2 (j)?

Спасибо за всю помощь.

Если вы решите проблему рекурсивным способом, что бы вы сделали? Вы бы начали вычислять F(n) . F (n) будет рекурсивно вызывать f1 (n-1) и f2 (n-1), пока не дойдут до листьев (f1 (0), f2 (0)), верно?

Итак, вот почему количество ссылок на F(n) в рекурсивном решении равно 1, потому что вам нужно будет вычислить f1(n) и f2 (n) только один раз. Это не относится к f1(n-1), на который ссылаются при вычислении f1 (n) и при вычислении f2 (n).

Теперь, как он придумал R1 (j) = R2 (j) = R1 (j 1) R2 (j 1)? ну, вычисляя это рекурсивным способом, каждый раз, когда вам нужно f1 (i), вы должны вычислить f1 (j), f2 (j) для каждого j в интервале [0, i) — иначе для каждого j, меньшего, чем i . Другими словами, значение f1,2(i) зависит от значения f1,2(0 ..i-1), поэтому каждый раз, когда вы вычисляете f_(i), вы вычисляете КАЖДОЕ f1,2(1 ..i-1) — (потому что это зависит отих значение).

По этой причине количество раз, когда вы вычисляете f_(i), зависит от того, сколько f1,2 есть «над ним».

Надеюсь, это понятно.