两个相互递归函数的"引用"数量的重复关系

Question

我正在通过Cormen et的Introduction To Algorithms（第2版）的动态编程部分。艾尔在装配线调度的背景下，我遇到了以下重复关系

（注:装配线调度或动态编程不需要回答这个问题，但它只是为了提供信息，以便它将有助于联系上下文）。

---

$(1),(2),(3)$ 是如图所示的三种关系。

$ $f_{1}[j]=\开始{案例} e_1+a_{1,1}&\quad ext{if}j=1\\ \min(f_1[j-1]+a_{1,j},f_2[j-1]+t_{2,j-1}+a_{1,j})&\quad ext{if}j\geq2\\ \end{cases}\标签1$ $

对称地,

$ $f_{2}[j]=\开始{案例} e_2+a_{2,1}&\quad ext{if}j=1\\ \min(f_2[j-1]+a_{2,j},f_1[j-1]+t_{1,j-1}+a_{2,j})&\quad ext{if}j\geq2\\ \end{cases}\标签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) ag3$ $

---

文本试图找到次数的重复关系 $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。\标签4$ $

从 $(1)$ 和 $(2)$,

$ $r_1(j)=r_2(j)=r_1(j+1)+r_2(j+1) ag5$ $

---

我不太明白 $(4)$ 和 $(5)$ 从三个对应关系中获得。（直接没有任何证据，就这么微不足道吗？)

我以为我能凭直觉看出来，因为只有一个地方 $f_1[n]$ 和 $f_2[n]$ 被称为，这是在 $f^\星$, ，所以可能在 $(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^\星$ 被引用，即，当 f_star 被称为, $f_1[n]$ 和 $f_2[n]$ 将被引用，即, f_1(n) 和 f_2(n) 将被调用，在哪里 f_1(.) 和 f_2(.) 将在下面解释。既然我们会打电话 f_star(n) 一次，这足以得到的价值 $f^\星$, ，我们得到公式（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）。