2つの相互再帰的関数への「参照」の数の再発関係

Question

私はCormenらによるアルゴリズムの紹介（第2版）の動的計画課を経験していました。 al。アセンブリラインスケジューリングのコンテキストでは、次の再発関係に遭遇しました

（アセンブリラインのスケジューリングや動的プログラミングは、質問に答えるために必要とされていませんが、それはコンテキストを関連付けるのを助けるための情報だけです）。

---

$（1）、（2）、（3）$ は示されているような3つの関係です。

$$ f_ {1} [j]=begin {ケース} E_1 + A_ {1,1}＆\ quad \ text {if} j= 1 \\ \ min（f_1 [j-1] + a_ {1、{1、j}、f_2 [j-1] + t_ {2、j-1} + a_ {1、j}）＆\ quad \ text {if} j} GEQ2 \\ \ end {ケース} \タグ1 $$

対称的に、

$$ f_ {2} [j]=begin {ケース} E_2 + A_ {2,1}＆\ quad \ text {if} j= 1 \\ \ min（f_2 [j-1] + a_ {2、{2、j}、F_1 [J-1] + T_ {1、j-1} + a_ {2、j}）＆\ quad \ text {if} j \ GEQ2 \\ \ end {ケース} \タグ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）\タグ3 $$

---

テキストは、 $ f_i [j] $ の回数の繰り返し関係を見つけようとします（ $ i= 1,2 $ と $ j= 1,2,3、...、n $ ）は、<のために相互の再帰コードを書き込むと参照されます。 SPAN CLASS="math-container"> $ f_1 [j] $ と $ f_2 [j] $ 。 $ r_i（j）$ は、 $ f_i [j] $ の数を表します。< / P>

彼らはそれを言う、

$（3）$ 、

$$ r_1（n）= r_2（n）= 1。\ tag4 $$

$（1）$ 、 $（2）$ 、

$$ r_1（j）= r_2（j）= r_1（j + 1）+ r_2（j + 1）\ tag 5 $$

---

私は $（4）$ と $の関係を全く理解できませんでした。 5）3つの対応関係から$ が得られます。 （証明なしで直接それはとても些細なことですか？）

$ f_1 [n] $ と $ f_2が1つしかないので直感的に考えました[n] $ が呼び出されます。これは $ f ^ \ star $ です。そのため、 $ 4）$ 必要な関係を得ます。

しかし、私がそのような概念に遭遇しなかったので、その前にその進行方法がわからない。誰かがその直感と同様に派生の数学的証明と私を案内するならば、私は感謝するでしょう。

しかしながら、問題についての洞察を大きく洞察することなく機械的な料理式の方法であるので、数学的な誘導の代替物はより有益でなければならない（しかし、他の方法がない場合は数学的誘導さえも感謝されています。私は証明の背後にある直感を得ることができます）]

Answer 1

あなたが組立ラインスケジューリングの設定を理解するためにあなたが取った長くて疲れた旅の後に使い果たされているように見えます、工場を通る最速の方法とステップ2の再帰的なステップ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_1(n)とf_2(n)が呼び出されます。 $ f ^ \ star $ の値を取得するのに十分なf_1(.)を呼び出すので、式（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])

.

so $ f_1 [j] $ は常に参照されます。つまり、 $ f_1（j）$ $ f_1 [j-1] $ は正確に参照されます。つまり、f_2(.)は正確に1回呼び出されます。

同様に、 $ f_2 [j] $ が参照されているときは、 $ f_1 [j-1] $ 一度だけ参照されます。 （あなたはそれをチェックアウトするためにあなた自身の関数f_star(n)を明示的に書くことができます。）

$ 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）を取得します。< / P>