PROGRAMACION DINAMICA

Programación dinámica

En informática, la programación dinámica es un método para reducir el tiempo de ejecución de un algoritmo mediante la utilización de subproblemas superpuestos y subestructuras óptimas, como se describe a continuación.

El matemático Richard Bellman inventó la programación dinámica en 1953 que se utiliza para optimizar problemas complejos que pueden ser discretizados y secuencializados.

Introducción

Una subestructura óptima significa que se pueden usar soluciones óptimas de subproblemas para encontrar la solución óptima del problema en su conjunto. Por ejemplo, el camino más corto entre dos vértices de un grafo se puede encontrar calculando primero el camino más corto al objetivo desde todos los vértices adyacentes al de partida, y después usando estas soluciones para elegir el mejor camino de todos ellos. En general, se pueden resolver problemas con subestructuras óptimas siguiendo estos tres pasos:

• Dividir el problema en subproblemas más pequeños.
• Resolver estos problemas de manera óptima usando este proceso de tres pasos recursivamente.
• Usar estas soluciones óptimas para construir una solución óptima al problema original.
• Los subproblemas se resuelven a su vez dividiéndolos en subproblemas más pequeños hasta que se alcance el caso fácil, donde la solución al problema es trivial.

ALGORITMOS HEURÍSTICOS

En el campo de la optimización, hay cierta ambigüedad en la definición de lo que es un  algoritmo heurístico y no es raro ver utilizar esta palabra con significados ligeramente distintos.

En su sentido más amplio, un algoritmo heurístico será un algoritmo para un problema de optimización basado en una estrategia (idea) transparente (habitualmente sencilla) para buscar dentro del conjunto de soluciones factibles y que no presenta ninguna garantía de encontrar el óptimo.

En un sentido un poco más específico, un heurístico es un algoritmo para el que no hay ningún resultado matemático que garantice que lleva a soluciones razonablemente buenas en un tiempo razonable, pero cuya idea parece asegurar un buen comportamiento para la mayoría de los ejemplos del problema en cuestión.

Una propiedad general de los algoritmos heurísticos es que son muy robustos, en el sentido que esa estrategia transparente de búsqueda puede trasladarse fácilmente de unos problemas a otros; siendo esta una de las razones por la que los heurísticos se han vuelto tan populares en la práctica: son habitualmente fáciles de implementar y “portables” de unos problemas a otros.

Usos o ejemplos

Hay algoritmos heurísticos de optimización de muchos tipos, entre los que se encuentran:

• Algoritmos de búsqueda local, que van saltando localmente de solución en solución intentando mejorar las condiciones de optimalidad.
• Algoritmos bioinspirados, que intentan imitar patrones de comportamiento que han sido exitosos en la naturaleza y usarlos para atacar problemas de optimización. Aquí destacan los algoritmos genéticos, algoritmos de colonias de hormigas, de colmenas de abejas.
• Algoritmos de recocido simulado. Son algoritmos de optimización que tienen su base en el proceso de templado de los metales de cara a llegar a una configuración más resistente de los mismos. Está muy relacionado con el llamado algoritmo de Metropolis-Hastings.