Obsérvese primero que el procedimiento poco inteligente de elegir la ruta más barata en cada etapa sucesiva no conduce a una decisión óptima global. Al seguir esta estrategia se obtiene la ruta A → B → F → I → J, con un costo total de 13. Pero un pequeño sacrificio en una etapa puede permitir mayores ahorros más adelante. Por ejemplo, A→ D→ F es en total más barato que A →B→ F.
Un enfoque posible para resolver este problema es el de prueba y error. Sin embargo, el número de rutas posibles es grande (18) y el cálculo del costo total para cada ruta no es una tarea atractiva.
Por fortuna, la programación dinámica proporciona una solución con mucho menos esfuerzo que la enumeración exhaustiva. (El ahorro computacional es enorme cuando se trata de versiones más grandes de este problema). La programación dinámica comienza con una pequeña porción del problema original y encuentra la solución óptima actual a partir de la que le precede, hasta resolver el problema original completo.
No hay comentarios.:
Publicar un comentario