Relação de recorrência para o número de “referências” a duas funções mutuamente recursivas

Question

Eu estava lendo a seção Programação Dinâmica de Introdução aos Algoritmos (2ª Edição) de Cormen et.al.onde me deparei com as seguintes relações de recorrência no contexto da programação da linha de montagem

(Observação:Porém, a programação da linha de montagem ou a programação dinâmica não é necessária para responder à pergunta, é apenas para fins informativos, para ajudar a relacionar o contexto).

---

$(1),(2),(3)$ são três relações como mostrado.

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

Simetricamente,

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

(onde $e_i,a_{i,j},t_{2,j-1}$ são constantes para $eu=1,2$ e $j=1,2,3,...,n$)

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

---

O texto tenta encontrar a relação de recorrência do número de vezes $f_i[j]$ ($eu=1,2$ e $j=1,2,3,...,n$) é referenciado se escrevermos um código recursivo mútuo para $f_1[j]$ e $f_2[j]$.Deixar $r_i(j)$ denota o número de vezes $f_i[j]$ é referenciado.

Eles disseram aquilo,

De $(3)$,

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

De $(1)$ e $(2)$,

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

---

Eu não conseguia entender muito bem como as relações de $(4)$ e $(5)$ são obtidos a partir das três relações correspondentes.(diretamente sem qualquer prova, é tão trivial?)

Pensei que poderia perceber intuitivamente que, como só existe um lugar onde $f_1[n]$ e $f_2[n]$ são chamados, o que está em $f^\estrela$, então provavelmente em $(4)$ obtemos a relação necessária.

Mas como nunca havia encontrado tal conceito antes, não sei bem como proceder.Ficaria grato se alguém me orientasse com a prova matemática da derivação, bem como com a intuição.

[Observação:No entanto, uma alternativa à indução matemática será mais útil, pois é um método de livro de receitas mecânico, sem fornecer muitos insights sobre o problema (mas se não houver outra saída, então até mesmo a indução matemática será apreciada se eu conseguir a intuição por trás a prova)].

Answer 1

Parece que você está exausto depois de uma longa e cansativa jornada para compreender a configuração da programação da linha de montagem, a etapa 1 na estrutura do caminho mais rápido pela fábrica e a etapa 2 em uma solução recursiva.

É fácil entender as fórmulas (4) e (5).

Quando programamos uma solução de recursão usando as fórmulas (1), (2) e (3), o lado esquerdo de cada fórmula é transformado na assinatura do seu método de implementação enquanto o lado direito é transformado no corpo da fórmula. método.

Por exemplo, (3) é transformado em código pseudo-Python

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

Então quando $f^\estrela$ é referenciado, ou seja, quando f_star é chamado, $f_1[n]$ e $f_2[n]$ será referenciado, ou seja, f_1(n) e f_2(n) será chamado, onde f_1(.) e f_2(.) será explicado abaixo.Já que vamos ligar f_star(n) uma vez, o que é suficiente para obter o valor de $f^\estrela$, obtemos a fórmula (4).

A fórmula (1) é transformada em código 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])

Então sempre que $f_1[j]$ é referenciado, ou seja, quando $f_1(j)$ é chamado, $f_1[j-1]$ será referenciado exatamente um, ou seja, f_1(j-1) será chamado exatamente uma vez.

Da mesma forma, sempre que $f_2[j]$ é referenciado, $f_1[j-1]$ será referenciado exatamente uma vez.(Você pode escrever a função f_2(j) explicitamente você mesmo para verificar.)

Observe que qualquer referência a $f_1[j-1]$ deve ser trazida por uma referência a $f_1[j]$ ou uma referência a $f_2[j]$.Então nós temos$$r_1(j-1) = r_1(j) + r_2(j).$$

Da mesma forma ou por simetria, também temos$$r_2(j-1) = r_1(j) + r_2(j).$$

Substituindo $j$ por $j+1$, obtemos a fórmula (5).