La recurrencia de la relación para el número de "referencias" a dos mutuamente función recursiva

Question

Yo estaba pasando por la Programación Dinámica la sección de Introducción a los Algoritmos (2ª Edición) por Cormen et.al.cuando me llegó a través de las siguientes relaciones de recurrencia en el contexto de la línea de montaje de la programación

(Nota:Línea de montaje de programación o programación dinámica no está obligado a responder a la pregunta, sin embargo, es sólo para información de manera que le ayudará a relacionar el contexto).

---

$(1),(2),(3)$ son tres relaciones, como se muestra.

$$f_{1}[j] = \begin{casos} e_1+a_{1,1} &\quad ext{si } j=1\\ \min(f_1[j-1]+a_{1,j},f_2[j-1]+t_{2,j-1}+a_{1,j})&\quad ext{si } j\geq2\\ \end{casos} ag 1$$

Simétricamente,

$$f_{2}[j] = \begin{casos} e_2+a_{2,1} &\quad ext{si } j=1\\ \min(f_2[j-1]+a_{2,j},f_1[j-1]+t_{1,j-1}+a_{2,j})&\quad ext{si } j\geq2\\ \end{casos} ag 2$$

(donde $e_i,a_{i,j},t_{2,j-1}$ son constantes para $i=1,2$ y $j=1,2,3,...,n$)

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

---

El texto intenta encontrar la recurrencia de la relación del número de veces que $f_i[j]$ ($i=1,2$ y $j=1,2,3,...,n$) se hace referencia a si escribimos un mutuo código recurrente para $f_1[j]$ y $f_2[j]$.Vamos $r_i(j)$ indicar el número de veces que $f_i[j]$ se hace referencia.

Dicen que,

De $(3)$,

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

De $(1)$ y $(2)$,

$$r_1(j)=r_2(j)=r_1(j+1)+r_2(j+1)\etiqueta 5$$

---

Yo no podía entender cómo las relaciones de $(4)$ y $(5)$ se obtienen a partir de los tres correspondientes relaciones.(directamente sin ningún tipo de prueba, es tan trivial?)

Pensé que podría hacer de forma intuitiva que como sólo hay un lugar donde $f_1[n]$ y $f_2[n]$ se llama, que es en $f^\estrella$, así que probablemente en $(4)$ se obtiene la necesaria relación.

Pero como que no me había encontrado tal concepto antes de que yo no sé muy bien cómo proceder.Estaría agradecido si alguien me guía con la matemática de la prueba de la derivación, así como la intuición.

[Nota:Sin embargo, una alternativa a la inducción matemática será más útil como es un libro de cocina mecánica método sin dar mucha penetración en el problema, sin embargo, (pero si en caso no hay otro camino, a continuación, incluso la inducción matemática es apreciado si puedo conseguir la intuición detrás de la prueba)].

Answer 1

Parece que está agotado después de un largo y agotador viaje que usted ha tomado para comprender la configuración de la línea de montaje de la programación, el paso 1 en la estructura de la forma más rápida a través de la fábrica y el paso 2 en una solución recursiva.

Es sencillo de entender la fórmula (4) y (5).

Cuando programamos una recursividad solución usando la fórmula (1), (2) y (3), el lado izquierdo de cada fórmula se transforma a la firma de su aplicación de método, mientras que el lado derecho se transforma en el cuerpo del método.

Por ejemplo, (3) se transforma en pseudo-código Python

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

Así que, cuando $f^\estrella$ se hace referencia, es decir, cuando f_star se llama, $f_1[n]$ y $f_2[n]$ se hará referencia, es decir, f_1(n) y f_2(n) será llamado, donde f_1(.) y f_2(.) se explicarán a continuación.Ya que vamos a llamar f_star(n) una vez, que es suficiente para obtener el valor de $f^\estrella$, obtenemos la fórmula (4).

La fórmula (1) se transforma en pseudo-código 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])

Así que cada vez que $f_1[j]$ se hace referencia, es decir, cuando $f_1(j)$ se llama, $f_1[j-1]$ se hace referencia exactamente, es decir, f_1(j-1) se llama exactamente una vez.

Del mismo modo, cuando $f_2[j]$ se hace referencia, $f_1[j-1]$ se hace referencia exactamente una vez.(Puede escribir la función de f_2(j) explícitamente a sí mismo a la salida.)

Tenga en cuenta que cualquier referencia a $f_1[j-1]$ debe ser ejercida por una referencia a $f_1[j]$ o una referencia a $f_2[j]$.Así tenemos $$r_1(j-1) = r_1(j) + r_2(j).$$

De manera similar o por simetría, también tenemos $$r_2(j-1) = r_1(j) + r_2(j).$$

La sustitución de $j$ por $j+1$, obtenemos la fórmula (5).