7.7: Programación dinámica

Introducimos un enfoque muy potente para resolver una amplia gama de problemas de optimización complicados, especialmente aquellos en los que el espacio de incógnitas es muy alto, por ejemplo, es una trayectoria misma, o una secuencia compleja de acciones, que se va a optimizar. Aquí solo se da una descripción introductoria, centrándose en los problemas de ruta más corta. Una gran cantidad de aplicaciones de procedimiento y planificación se pueden lanzar como problemas de ruta más corta.

Comenzamos con el concepto esencial. Supongamos que estamos conduciendo del Punto A al Punto C, y nos preguntamos cuál es el camino más corto en millas. Si A y C representan a Los Ángeles y Boston, por ejemplo, ¡hay muchos caminos para elegir! Supongamos que de una manera u otra hemos encontrado el mejor camino, y que un Punto B se encuentra a lo largo de este camino, dicen Las Vegas. Que\(X\) sea un punto arbitrario al este de Las Vegas. Si ahora tuviéramos que resolver un nuevo problema de optimización para llegar solo de Las Vegas a Boston, este mismo punto arbitrario también\(X\) estaría a lo largo del nuevo camino óptimo.

El punto es sutil: el problema de optimización de Las Vegas a Boston es más fácil que el de Los Ángeles a Boston, y la idea es utilizar esta propiedad hacia atrás a través del tiempo para evolucionar el camino óptimo, comenzando en Boston.

Figura\(\PageIndex{1}\): visualización del problema de ejemplo inmediatamente a continuación. \(s=2\), es decir, hay dos capas de nodos (las Montañas Rocosas y el río Mississippi), y\(n=3\), es decir, hay tres nodos o ubicaciones donde es posible cruzar cada uno de estos obstáculos.

Ejemplo: Viaje Nodal. Ahora agregamos algo de estructura al experimento anterior. Considera ahora viajar del punto A (Los Ángeles) al punto D (Boston). Supongamos que solo hay tres lugares para cruzar las Montañas Rocosas\(B_1, \, B_2, \, B_3\),, y tres lugares para cruzar el río Mississippi,\(C_1, \, C_2, \, C_3\). A modo de notación, decimos que el camino de\(A\) a\(B_1\) es\(AB_1\). Supongamos que todos los caminos (y distancias) de\(A\) a los\(B\) -nodos son conocidos, como son los de\(B\) los -nodos a los\(C\) -nodos, y los\(C\) -nodos al punto terminal\(D\). Hay nueve caminos únicos desde\(A\) hasta\(D\).

Un enfoque de fuerza bruta resume la distancia total para todos los caminos posibles, y elige el más corto. En términos de cómputos, podríamos resumir que este método requiere nueve adiciones de tres números, equivalentes a dieciocho adiciones de dos números. La comparación de números es relativamente barata.

El enfoque de programación dinámica tiene dos pasos. Primero, de cada\(B\) -nodo, elija la mejor ruta a\(D\). Hay tres caminos posibles desde\(B_1\) hasta\(D\), por ejemplo, y nueve caminos en total desde el\(B\) nivel hasta\(D\). Almacenar los mejores caminos como\(B_1 D|_{opt}, \, B_2 D|_{opt}, \, B_3 D|_{opt}\). Esta operación implica nueve adiciones de dos números. Segundo, computar la distancia para cada una de las rutas posibles desde\(A\) hasta\(D\), restringidas a las rutas óptimas desde los\(B\) -nodos hacia adelante:\(A B_1 + B_1 D|_{opt}, \, A B_2 + B_2 D|_{opt},\) o\(A B_3 + B_3 D|_{opt}\). La ruta combinada con la distancia más corta es la solución total; este segundo paso involucra tres sumas de dos números, y la optimización total se realiza en doce adiciones de dos números.

No hace falta decir que este ejemplo solo da una leve ventaja al enfoque de programación dinámica sobre la fuerza bruta. Sin embargo, la brecha se ensancha enormemente a medida que se aumentan las dimensiones del espacio de solución. En general, si hay\(s\) capas de nodos (por ejemplo, ríos o cadenas montañosas), y cada uno tiene ancho\(n\) (por ejemplo, puntos de cruce de\(n\) ríos), el enfoque de fuerza bruta tomará\(s n^s\) adiciones, mientras que el procedimiento de programación dinámica implica solo\(n^2(s-1)+n)\) adiciones. En el caso de\(n=5, \, s=5\), la fuerza bruta requiere\(15625\) adiciones; ¡la programación dinámica solo necesita\(105\)!