Algoritmos Vuelta Atras.

Índice

1. Describir la Metodología de resolución de problemas “Vuelta Atrás”.
1.1 Aplicación y alcance.
1.2 Elementos característicos.
1.3 Esbozo del coste computacional.

2. Problema para realizar la resolución "más barata computacionalmente" y el cual se lleva a cabo mediante esta metodología. Aplicarla.
2.1 Identificación de los elementos característicos.
2.2 Demostración/Justificación de porque el problema es resoluble por esta vía.
2.3 Resumen del código y análisis del coste computacional a partir del código reducido.

3.Bibliografía.

_____________________________________________________________


1. Describir la Metodología de resolución de problemas “Vuelta Atrás”.

Los algoritmos vuelta atrás (también conocidos como Backtraking), son una estrategia de programación que permiten encontrar soluciones a problemas que tienen unas determinadas
restricciones.

La forma de trabajar de este tipo de algoritmos, es muy semejante a la realización de un recorrido en profundidad dentro de un árbol de búsqueda. Así, para encontrar el conjunto de posibles soluciones, basta con recorrer el árbol construyendo soluciones parciales a medida que se avanza hacia la solución final.

Estas soluciones parciales, limitan las regiones en las que se puede encontrar una solución completa. De esta forma, si el recorrido tiene éxito, se puede continuar buscando otras soluciones o la mejor de todas ellas, y concluir con la más óptima.

Programación Dinámica.

Índice

1. Describir la Metodología de resolución de problemas “Programación Dinámicas”.

1.1 Aplicación y alcance.

1.2 Elementos característicos.

1.2 Esbozo del coste computacional.

2. Problema para realizar la resolución "más barata computacionalmente" y el cual se lleva a cabo mediante esta metodología. Aplicarla.

2.1 Identificación de los elementos característicos.

2.2 Demostración/Justificación de porque el problema es resoluble por esta vía.

2.3 Resumen del código y análisis del coste computacional.

3. Bibliografía.

______________________________________________________________

1. Describir la Metodología de resolución de problemas “Programación Dinámicas”.

El término “Programación Dinámica fue utilizado inicialmente en 1940, para resolver problemas de optimización matemática.

La programación dinámica es un método de optimización del cálculo de problemas y es utilizada en compiladores, consiste en solucionar cierto problema dividiéndolo en subproblemas más sencillos, calculando sus resultados y almacenándolos. Estos resultados posteriormente se

utilizan para la resolución del problema final.

Almacenar resultados de subproblemas es una gran ventaja en cálculos dónde se repiten las mismas operación múltiples veces, mediante el método de la programación dinámica estas operaciones sólo se realizan una vez y se guarda la solución.

Se dice de la programación dinámica que es un método para resolver problemas que exhiben propiedades de problemas sobrepuestos y estructura óptima.