Bien. El algoritmo dinámico funciona de la siguiente manera. Definamos el problema como tratar de determinar el orden de multiplicación M1 * M2 * M3 * … * Mn usando paréntesis para denotar el orden.
Entonces, la forma básica de ver este problema en una programación dinámica es la siguiente:
– Podemos separar esta multiplicación en dos conjuntos (M1 * M2 *… * Mj) * (M (j + 1) *… * Mn). Por lo tanto, la solución en este nivel se reduce a cómo elegir j para minimizar el costo de la multiplicación. En realidad, esto se hace usando un enfoque de fuerza bruta, no un algoritmo codicioso (lo que significaría elegir j de manera que obtengamos la solución mínima localmente en ese punto. En este caso, elegiríamos j para que M (j + 1) sea el matriz con el menor número de filas)
- ¿Cuál es la diferencia entre computer graphics y computer vision?
- ¿Cuál es la diferencia entre visión por computadora, procesamiento de imágenes digitales y computación multimedia?
- ¿Cuál es el estado actual del arte en visión biomimética por computadora?
- ¿Por qué la mayoría de las investigaciones de inteligencia artificial abandonaron la inteligencia artificial basada en la lógica en favor de enfoques estadísticos?
- ¿Es cierto que Simon Peyton Jones no tiene un doctorado, pero aún así aconseja a los estudiantes de doctorado?
-Pero, para hacer una fuerza bruta, necesitamos saber cómo parentesificar de manera óptima cada una de las cadenas de sub multiplicación. Por lo tanto, tenemos un pequeño problema a la mano. Esto va iterativamente hacia abajo hasta que tenemos solo dos matrices entre paréntesis, en cuyo punto podemos calcular los flops requeridos directamente. Esto es similar a Bellman-Ford, donde dos vértices en la ruta de menor distancia también siguen la ruta más corta entre ellos. Así que vamos iterativamente hasta obtener dos vértices donde podemos calcular la distancia usando el peso del borde.
– Ahora tenemos una gran solución recursiva a la mano donde muchas soluciones necesitan ser recalculadas,
p.ej. para A1 * … * A5 dado en el libro, tenemos estas 5 posibles soluciones
(A1 (A2 (A3 A4))),
(A1 ((A2 A3) A4)),
((A1 A2) (A3 A4)),
((A1 (A2 A3)) A4),
(((A1 A2) A3) A4).
Puede ver que el costo de A3 * A4 se requiere para el cálculo del costo total tanto en la primera como en la tercera solución. Tiene sentido almacenar el costo de A3 * A4 cuando lo calculamos por primera vez para que no sea necesario volver a calcularlo. Para cadenas de matriz más grandes, podemos almacenar el costo mínimo general directamente y recuperarlo de la memoria (tabla n ^ 2). Por lo tanto, no necesitamos bajar la recursión la segunda vez.
La esencia del programa dinámico se reduce al hecho de que la subestructura de una solución óptima es óptima en sí misma. Por lo tanto, cuando nos abrimos paso a través de soluciones brutas, podemos reutilizar los valores óptimos calculados antes para ahorrar mucho tiempo.
Espero haber respondido tu pregunta.
