¡Gracias por visitar Tecno Academy!                     Informática, todos los niveles - Trucos - Apuntes - Diapositivas - Libros - Enlaces - Curiosidades - Descargas - Tecnologías - Opiniones - Podcasting, Byte - Internautas TV - Pizarra Virtual                   

lunes, 22 de octubre de 2007

Backtracking alias "Vuelta atrás"

En mi empeño de ver todos los esquemas algorítmicos posibles (material que le será de gran ayuda a muchos universitarios, especialmente a los alumnos que cursan Programación III de la UNED) dejo disponibles a continuación unas transparecias del socorrido método de Vuelta Atrás. Digo socorrido porque permite resolver un buen número de problemas cuya solución es susceptible de ser interpretada como una tupla de valores, donde un índice k en la tupla solución representa el nivel dentro de un árbol implícito de exploración del espacio de estados y el k-ésimo valor de la solución es el que finalmente se escoge entre los posibles para cada nivel (ramas del árbol). La flexibilidad de Vuelta Atrás radica en que la exploración en profundidad del árbol implícito permite retomar decisiones ya tomadas para cambiarlas por otras quizás más adecuadas (de ahí el nombre). Esto hace que los algoritmos de Vuelta Atrás permitan resolver de forma intuitiva problemas donde el esquema voraz es imposible de aplicar o resulta díficil de demostrar su optimalidad. Como contrapartida, suelen ser muy ineficientes (de orden exponencial) a no ser que se aplique alguna estrategia de poda que permitar reducir el árbol de búsqueda o aumentar las probabilidades de encontrar la solución en un tiempo razonable de tiempo.


Referencias:

No es mi ánimo usar material ajeno como si fuese mío. Muchas veces sucede que en medio de las prisas o el desorden uno pierde la referencia al sitio web donde descargó cierto material. En este caso, cuando ya creía perdida toda referencia, me encontré con unas notas escondidas en las profundidades de una subcarperta donde reseñaba que las primeras transparencias pertenecen al profesor Javier Campos y las segundas al profesor Ginés García Mateos. También las transparencias relativas a programación dinámica que aquí proporcioné en su momento debieron de ser extraídas de los apuntes de Javier Campos. Vaya para ellos el reconocimiento. Yo sólo las he remozado un poco dándole nuevo estilo y colores para que resalten adecuadamente. No obstante, mi espíritu es lo suficientemente solidario con la causa para ir aportando material propio con el transcurrir del tiempo. En todo caso, será material más específico; para estos temas generales no consideré oportuno reescribir lo que ya ha sido escrito por otros con tan buen hacer.

No hay comentarios: