Wiederholungsbeziehung für die Anzahl der „Referenzen“ auf zwei gegenseitig rekursive Funktionen

Question

Ich habe den Abschnitt „Dynamische Programmierung“ in „Einführung in Algorithmen“ (2. Auflage) von Cormen et al. durchgelesen.al.wo ich im Zusammenhang mit der Fließbandplanung auf die folgenden Wiederholungsbeziehungen gestoßen bin

(Notiz:Für die Beantwortung der Frage ist jedoch keine Fließbandplanung oder dynamische Programmierung erforderlich, sie dient lediglich der Information und soll dabei helfen, den Kontext in Beziehung zu setzen.

---

$(1),(2),(3)$ sind drei Beziehungen wie gezeigt.

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

Symmetrisch,

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

(Wo $e_i,a_{i,j},t_{2,j-1}$ sind Konstanten für $i=1,2$ Und $j=1,2,3,...,n$)

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

---

Der Text versucht, die Wiederholungsbeziehung der Häufigkeit zu finden $f_i[j]$ ($i=1,2$ Und $j=1,2,3,...,n$) wird referenziert, wenn wir einen gegenseitigen rekursiven Code für schreiben $f_1[j]$ Und $f_2[j]$.Lassen $r_i(j)$ bezeichnen die Häufigkeit $f_i[j]$ wird referenziert.

Sie sagen, dass,

Aus $(3)$,

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

Aus $(1)$ Und $(2)$,

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

---

Ich konnte nicht ganz verstehen, wie die Beziehungen von $(4)$ Und $(5)$ ergeben sich aus den drei entsprechenden Beziehungen.(Direkt ohne Beweis, ist das so trivial?)

Ich dachte, ich könnte das intuitiv erkennen, da es nur einen Ort gibt, an dem $f_1[n]$ Und $f_2[n]$ genannt werden, was in ist $f^\star$, also wahrscheinlich in $(4)$ Wir erhalten die erforderliche Beziehung.

Aber da ich noch nie auf ein solches Konzept gestoßen bin, weiß ich nicht so recht, wie ich vorgehen soll.Ich wäre dankbar, wenn mich jemand beim mathematischen Beweis der Ableitung sowie der Intuition unterstützen würde.

[Notiz:Allerdings dürfte eine Alternative zur mathematischen Induktion hilfreicher sein, da es sich um eine mechanische Kochbuchmethode handelt, die allerdings keinen großen Einblick in das Problem gibt (wenn es aber keinen anderen Ausweg gibt, dann ist sogar die mathematische Induktion willkommen, wenn ich die Intuition dahinter habe). der Beweis)].

Answer 1

Es sieht so aus, als ob Sie erschöpft sind nach einer langen und ermüdenden Reise, die Sie unternommen haben, um den Aufbau der Montagelinienplanung, Schritt 1 über die Struktur des schnellsten Weges durch die Fabrik und Schritt 2 über eine rekursive Lösung zu verstehen.

Die Formeln (4) und (5) sind leicht zu verstehen.

Wenn wir eine Rekursionslösung unter Verwendung der Formeln (1), (2) und (3) programmieren, wird die linke Seite jeder Formel in die Signatur ihrer implementierenden Methode umgewandelt, während die rechte Seite in den Körper der Formel umgewandelt wird Methode.

Beispielsweise wird (3) in Pseudo-Python-Code umgewandelt

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

Also, wann $f^\star$ referenziert wird, d. h. wann f_star wird genannt, $f_1[n]$ Und $f_2[n]$ wird referenziert, d.h. f_1(n) Und f_2(n) wird aufgerufen, wo f_1(.) Und f_2(.) wird weiter unten erläutert.Da werden wir anrufen f_star(n) einmal, was ausreicht, um den Wert zu ermitteln $f^\star$, wir erhalten Formel (4).

Formel (1) wird in Pseudo-Python-Code umgewandelt

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])

Also wann immer $f_1[j]$ referenziert wird, d. h. wann $f_1(j)$ wird genannt, $f_1[j-1]$ wird genau einmal referenziert, d.h. f_1(j-1) wird genau einmal aufgerufen.

Ebenso, wann immer $f_2[j]$ referenziert wird, $f_1[j-1]$ wird genau einmal referenziert.(Sie können die Funktion schreiben f_2(j) explizit selbst, um es auszuprobieren.)

Beachten Sie, dass jeder Verweis auf $f_1[j-1]$ muss entweder durch einen Verweis auf gebracht werden $f_1[j]$ oder ein Verweis auf $f_2[j]$.Also haben wir$$r_1(j-1) = r_1(j) + r_2(j).$$

In ähnlicher Weise oder aufgrund der Symmetrie gilt auch$$r_2(j-1) = r_1(j) + r_2(j).$$

Ersetzen $j$ von $j+1$, wir erhalten Formel (5).