Relazione di ricorrenza per il numero di “riferimenti” a due funzioni reciprocamente ricorsive

Question

Stavo esaminando la sezione Programmazione dinamica di Introduzione agli algoritmi (2a edizione) di Cormen et.al.dove mi sono imbattuto nelle seguenti relazioni ricorrenti nel contesto della pianificazione della catena di montaggio

(Nota:La pianificazione della catena di montaggio o la programmazione dinamica non sono però necessarie per rispondere alla domanda, è solo a scopo informativo in modo che possa aiutare a mettere in relazione il contesto).

---

$(1),(2),(3)$ ci sono tre relazioni come mostrato.

$$f_{1}[j] = \begin{casi} 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} ag 1$$

Simmetricamente,

$$f_{2}[j] = \begin{casi} 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} ag 2$$

(Dove $e_i,a_{i,j},t_{2,j-1}$ sono costanti per $i=1,2$ E $j=1,2,3,...,n$)

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

---

Il testo cerca di trovare la relazione di ricorrenza del numero di volte $f_i[j]$ ($i=1,2$ E $j=1,2,3,...,n$) viene fatto riferimento se scriviamo un codice ricorsivo reciproco per $f_1[j]$ E $f_2[j]$.Permettere $r_i(j)$ denotare il numero di volte $f_i[j]$ è referenziato.

Dicono che,

Da $(3)$,

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

Da $(1)$ E $(2)$,

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

---

Non riuscivo a capire come funzionano le relazioni $(4)$ E $(5)$ si ottengono dalle tre relazioni corrispondenti.(direttamente senza alcuna prova, è così banale?)

Pensavo di poterlo capire intuitivamente poiché c'è solo un posto dove $f_1[n]$ E $f_2[n]$ sono chiamati, che è in $f^\stella$, quindi probabilmente dentro $(4)$ otteniamo la relazione richiesta.

Ma poiché non avevo mai incontrato un concetto del genere prima, non so bene come procedere.Sarei grato se qualcuno mi guidasse con la dimostrazione matematica della derivazione e dell'intuizione.

[Nota:Tuttavia un'alternativa all'induzione matematica sarà più utile in quanto si tratta di un metodo meccanico da ricettario senza però fornire molte informazioni sul problema (ma se nel caso non ci fosse altra via d'uscita, allora anche l'induzione matematica è apprezzata se riesco a ottenere l'intuizione dietro la prova)].

Answer 1

Sembra che tu sia esausto dopo un lungo e faticoso viaggio che hai intrapreso per comprendere l'impostazione della pianificazione della catena di montaggio, il passaggio 1 sulla struttura del percorso più veloce attraverso la fabbrica e il passaggio 2 su una soluzione ricorsiva.

È semplice comprendere le formule (4) e (5).

Quando programmiamo una soluzione ricorsiva utilizzando la formula (1), (2) e (3), il lato sinistro di ciascuna formula viene trasformato nella firma del suo metodo di implementazione mentre il lato destro viene trasformato nel corpo della metodo.

Ad esempio, (3) viene trasformato in codice pseudo-Python

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

Cosi quando $f^\stella$ viene fatto riferimento, ovvero quando f_star è chiamato, $f_1[n]$ E $f_2[n]$ verrà fatto riferimento, ovvero f_1(n) E f_2(n) sarà chiamato, dove f_1(.) E f_2(.) verrà spiegato di seguito.Dal momento che chiameremo f_star(n) una volta, il che è sufficiente per ottenere il valore di $f^\stella$, otteniamo la formula (4).

La formula (1) viene trasformata in codice 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])

Quindi ogni volta $f_1[j]$ viene fatto riferimento, ovvero quando $f_1(j)$ è chiamato, $f_1[j-1]$ verrà fatto riferimento esattamente a uno, ovvero f_1(j-1) verrà chiamato esattamente una volta.

Allo stesso modo, ogni volta $f_2[j]$ viene fatto riferimento, $f_1[j-1]$ verrà fatto riferimento esattamente una volta.(Puoi scrivere la funzione f_2(j) esplicitamente te stesso per verificarlo.)

Si noti che qualsiasi riferimento a $f_1[j-1]$ deve essere accompagnato da un riferimento a $f_1[j]$ o un riferimento a $f_2[j]$.Quindi abbiamo$$r_1(j-1) = r_1(j) + r_2(j).$$

Allo stesso modo o per simmetria, abbiamo anche$$r_2(j-1) = r_1(j) + r_2(j).$$

Sostituzione $j$ di $j+1$, otteniamo la formula (5).