Relation de récurrence pour le nombre de « références » à deux fonctions mutuellement récursives

Question

Je parcourais la section Programmation dynamique d'Introduction aux algorithmes (2e édition) de Cormen et.Al.où je suis tombé sur les relations de récurrence suivantes dans le contexte de l'ordonnancement des chaînes d'assemblage

(Note:La planification de la chaîne d'assemblage ou la programmation dynamique ne sont cependant pas nécessaires pour répondre à la question, c'est juste à titre d'information afin d'aider à relier le contexte).

---

$(1),(2),(3)$ sont trois relations comme indiqué.

$$ f_ {1} [j] = begin {cas} 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 {cas} tag 1 $$

Symétriquement,

$$ f_ {2} [j] = begin {cas} 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 {cas} tag 2 $$

(où $e_i,a_{i,j},t_{2,j-1}$ sont des constantes pour $i=1,2$ et $j=1,2,3,...,n$)

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

---

Le texte tente de trouver la relation de récurrence du nombre de fois $f_i[j]$ ($i=1,2$ et $j=1,2,3,...,n$) est référencé si l’on écrit un code récursif mutuel pour $f_1[j]$ et $f_2[j]$.Laisser $r_i(j)$ désigne le nombre de fois $f_i[j]$ est référencé.

Ils disent ça,

Depuis $(3)$,

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

Depuis $(1)$ et $(2)$,

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

---

Je ne comprenais pas vraiment comment les relations de $(4)$ et $(5)$ sont obtenus à partir des trois relations correspondantes.(directement sans aucune preuve, est-ce si trivial ?)

Je pensais pouvoir comprendre intuitivement que comme il n'y a qu'un seul endroit où $f_1[n]$ et $f_2[n]$ sont appelés, ce qui est dans $f^\étoile$, donc probablement dans $(4)$ nous obtenons la relation requise.

Mais comme je n’avais jamais rencontré un tel concept auparavant, je ne sais pas trop comment procéder.Je serais reconnaissant si quelqu'un me guide avec la preuve mathématique de la dérivation ainsi que de l'intuition.

[Note:Cependant, une alternative à l'induction mathématique sera plus utile car il s'agit d'une méthode de livre de recettes mécanique sans donner beaucoup d'informations sur le problème (mais s'il n'y a pas d'autre issue, alors même l'induction mathématique est appréciée si je peux obtenir l'intuition derrière la preuve)].

Answer 1

Il semble que vous soyez épuisé après un long et fatigant voyage que vous avez entrepris pour comprendre la configuration de la planification de la chaîne de montage, l'étape 1 sur la structure du chemin le plus rapide à travers l'usine et l'étape 2 sur une solution récursive.

Il est simple de comprendre les formules (4) et (5).

Lorsque nous programmons une solution récursive en utilisant les formules (1), (2) et (3), le côté gauche de chaque formule est transformé en signature de sa méthode d'implémentation tandis que le côté droit est transformé en corps du méthode.

Par exemple, (3) est transformé en code pseudo-Python

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

Donc quand $f^\étoile$ est référencé, c'est-à-dire lorsque f_star est appelé, $f_1[n]$ et $f_2[n]$ sera référencé, c'est-à-dire f_1(n) et f_2(n) sera appelé, où f_1(.) et f_2(.) sera expliqué ci-dessous.Puisque nous appellerons f_star(n) une fois, ce qui est suffisant pour obtenir la valeur de $f^\étoile$, on obtient la formule (4).

La formule (1) est transformée en code pseudo-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])

Alors chaque fois $f_1[j]$ est référencé, c'est-à-dire lorsque $f_1(j)$ est appelé, $f_1[j-1]$ sera référencé exactement un, c'est-à-dire, f_1(j-1) sera appelé exactement une fois.

De même, chaque fois $f_2[j]$ est référencé, $f_1[j-1]$ sera référencé une seule fois.(Vous pouvez écrire la fonction f_2(j) explicitement vous-même pour le vérifier.)

Notez que toute référence à $f_1[j-1]$ doit être apporté soit par une référence à $f_1[j]$ ou une référence à $f_2[j]$.Donc nous avons$$r_1(j-1) = r_1(j) + r_2(j).$$

De même ou par symétrie, on a aussi$$r_2(j-1) = r_1(j) + r_2(j).$$

Remplacement $j$ par $j+1$, on obtient la formule (5).