El término Programación Dinámica fue utilizado originalmente en los 1940’s por Richard Bellman para describir el proceso de resolver problemas donde se necesita encontrar las mejores decisiones una tras otra. Para 1953, el refinó esto a su significado moderno, el cual se refiere específicamente a anidar pequeños problemas de decisión dentro de grandes decisiones, luego de esto el campo fue reconocido por la lEEE como un tópico de análisis de sistemas e ingeniería.
Es un algoritmo basado en la técnica de divide y vencerás, que permite, en promedio, ordenar n elementos en un tiempo proporcional a n log n. El método Quick Sort es actualmente el más eficiente y veloz de los método de ordenación interna. Es también conocido con el nombre del método rápido y de ordenamento por partición. También, este método es una mejora sustancial del método de intercambio directo y recibe el nombre de Quick Sort, por la velocidad con la que ordena los elementos del arreglo.
La técnica divide y conquista separa un problema en subproblemas que se parecen al problema original, de manera recursiva resuelve los subproblemas y, por último, combina las soluciones de los subproblemas para resolver el problema original. Como divide y conquista resuelve subproblemas de manera recursiva, cada subproblema debe ser más pequeño que el problema original, y debe haber un caso base para los subproblemas.
El enfoque de programación dinámica es similar a dividir y vencer al dividir el problema en subproblemas más pequeños y posibles. Pero a diferencia de dividir y conquistar, estos subproblemas no se resuelven de forma independiente. Más bien, los resultados de estos subproblemas más pequeños se recuerdan y se usan para subproblemas similares o superpuestos.
El problema de las N reinas es un problema que se basa en colocar N reinas de ajedrez en un tablero de ajedrez de medidas N × N para que no se ataquen dos reinas.
Comentarios en artículos
No comments
Nobody has submitted a comment yet.