Sabemos que la resolución del problema de optimización como $$\max_{y_1, \dots,y_n} \sum_{i=1}^{n-1} f_{i,i+1}(y_i,y_{i+1})$$ $$y_i \in \mathbb{N}_0$$ es fácil y puede hacerse mediante programación dinámica (algoritmo de Viterbi). Véase la siguiente figura para inspirarse:
La pregunta es: ¿cómo resolver el siguiente problema de forma eficiente?
$$\max_{y_1 + \dots + y_n=c} \sum_{i=1}^{n-1} f_{i,i+1}(y_i,y_{i+1})$$ $$y_i \in \mathbb{N}_0 \\ c \in \mathbb{N}_0$$
Tengo dos soluciones. La primera es la programación lineal entera (ILP) que se sabe que es NPC en general. La segunda es un algoritmo de Programación Dinámica (PD) polinómica.
La idea de ILP es la siguiente:
$$ \max \sum_{(u, v) \in E} x_{uv} l_{uv} \\ \text{subject to} \\ \sum_{(u, v) \in E} x_{uv} = \sum_{(v, w) \in E} x_{vw} \quad \forall v \in V \setminus \{s,t\} \\ \sum_{(u, t) \in E} = 1 \\ \sum_{(u, v) \in E} x_{uv} c_{uv} = C \\ \text{variables} \\ x_{uv} \in \{0, 1\} \quad \forall (u, v) \in E \\ \text{parameters} \\ C \in \mathbb{N}_0 \\ l_{uv} \in \mathbb{R} \quad \forall (u, v) \in E \\ c_{uv} \in \mathbb{N}_0 \quad \forall (u, v) \in E $$
donde $t$ es el nodo sumidero, $C$ es el coste total de $_1+\dots+_=C$ , $l_{uv}$ es la longitud entre cada dos nodos $u$ y $v$ (lo mismo que $_{,+1}(_,_{+1})$ en la pregunta). $c_{uv}$ mapas a $y_i$ .
En otras palabras, se trata de la formulación ILP del camino más largo con una restricción adicional $\sum_{(u, v) \in E} x_{uv} c_{uv} = C$ . Si alguien está interesado en una solución eficiente de DP, que me escriba un mensaje privado.
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
