Рекуррентное соотношение количества «обращений» к двум взаимно рекурсивным функциям

Question

Я просматривал раздел «Динамическое программирование» книги «Введение в алгоритмы» (2-е издание) Кормена и др.ал.где я столкнулся со следующими рекуррентными отношениями в контексте планирования сборочной линии

(Примечание:Однако для ответа на этот вопрос не требуется планирование сборочной линии или динамическое программирование, это просто информация, которая поможет связать контекст).

---

$(1),(2),(3)$ три отношения, как показано.

$$ f_ {1} [j] = begin {case} e_1+a_ {1,1} & Quad text {if} j = 1 min (f_1 [j-1]+a_ {1, j}, f_2 [j-1]+t_ {2, j-1}+a_ {1, j}) & Quad text {if} j geq2 end {case} Tag 1 $$

Симметрично,

$$ f_ {2} [j] = begin {case} e_2+a_ {2,1} & Quad text {if} j = 1 min (f_2 [j-1]+a_ {2, j}, f_1 [j-1]+t_ {1, j-1}+a_ {2, j}) & Quad text {if} j geq2 end {case} Tag 2 $$

(где $e_i,a_{i,j},t_{2,j-1}$ являются константами для $i=1,2$ и $j=1,2,3,...,n$)

$$f^\star=\min(f_1[n]+x_1,f_2[n]+x_2) ag 3$$

---

В тексте делается попытка найти рекуррентное соотношение количества раз. $f_i[j]$ ($i=1,2$ и $j=1,2,3,...,n$) используется, если мы пишем взаимно рекурсивный код для $f_1[j]$ и $f_2[j]$.Позволять $r_i(j)$ обозначьте количество раз $f_i[j]$ есть ссылка.

Они говорят, что,

От $(3)$,

$$r_1(n)=r_2(n)=1. ag4$$

От $(1)$ и $(2)$,

$$r_1(j)=r_2(j)=r_1(j+1)+r_2(j+1) ag 5$$

---

Я не совсем мог понять, как складываются отношения $(4)$ и $(5)$ получаются из трех соответствующих соотношений.(прямо без всяких доказательств, неужели это так тривиально?)

Я думал, что интуитивно могу это понять, поскольку есть только одно место, где $f_1[n]$ и $f_2[n]$ называются, что в $f^\star$, так что, вероятно, в $(4)$ мы получаем требуемое соотношение.

Но поскольку я раньше не сталкивался с такой концепцией, я не совсем знаю, как действовать.Я был бы признателен, если бы кто-нибудь помог мне математическим доказательством вывода, а также интуицией.

[Примечание:Однако альтернатива математической индукции будет более полезной, поскольку это механический метод кулинарной книги, хотя и не дающий особого понимания проблемы (но если другого выхода нет, то даже математическая индукция будет оценена, если я смогу понять интуицию, лежащую в основе доказательство)].

Answer 1

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

Формулы (4) и (5) несложно понять.

Когда мы программируем рекурсивное решение с использованием формул (1), (2) и (3), левая часть каждой формулы преобразуется в сигнатуру метода ее реализации, а правая часть преобразуется в тело метода. метод.

Например, (3) преобразуется в псевдо-код Python.

def f_star(n):
    return min(f_1(n) + x_1, f_2(n) + x_2)

Так когда $f^\star$ упоминается, т. е. когда f_star называется, $f_1[n]$ и $f_2[n]$ будет ссылка, т.е. f_1(n) и f_2(n) будет вызван, где f_1(.) и f_2(.) будет объяснено ниже.Поскольку мы позвоним f_star(n) один раз, чего достаточно, чтобы получить значение $f^\star$, получаем формулу (4).

Формула (1) преобразуется в псевдо-Python-код.

def f_1(j):
    if j == 1:
        return e[1] + a[1][1]
    else:
        return min(f_1(j - 1) + a[1][j], f_2(j - 1) + t[2][j - 1] + a[1][j])

Поэтому всякий раз, когда $f_1[j]$ упоминается, т. е. когда $f_1(j)$ называется, $f_1[j-1]$ будет упоминаться ровно один, т.е. f_1(j-1) будет вызван ровно один раз.

Аналогично, всякий раз, когда $f_2[j]$ упоминается, $f_1[j-1]$ будет упомянут ровно один раз.(Можно написать функцию f_2(j) специально для себя, чтобы проверить это.)

Обратите внимание, что любая ссылка на $f_1[j-1]$ должно быть доведено либо ссылкой на $f_1[j]$ или ссылка на $f_2[j]$.Итак, у нас есть$$r_1(j-1) = r_1(j) + r_2(j).$$

Аналогично или по симметрии мы также имеем$$r_2(j-1) = r_1(j) + r_2(j).$$

Замена $j$ к $j+1$, получаем формулу (5).