Upload
omar-daza
View
160
Download
0
Embed Size (px)
Citation preview
Backtracking
ANALISIS DE ALGORITMO
OMAR MERIÑO
INTRODUCCION
El backtracking es una estrategia usada para
encontrar soluciones a problemas que tienen una solución completa, en los que el orden de los elementos no importa, y en los que existen una serie de variables a cada una de las cuales
CONCEPTO
Backtracking (o búsqueda atrás) es una técnica de programación para hacer búsqueda sistemática a través de todas las configuraciones posibles dentro de un espacio de búsqueda.
La técnica Backtracking es un método de búsqueda de soluciones exhaustiva sobre grafos dirigidos acíclicos, el cual se acelera mediante poda de ramas poco prometedoras.
Para lograr esto, los algoritmos de tipo backtracking construyen posibles solucionescandidatas de manera sistemática. En general, dado una solución candidata s :
1. Verifican si s es solución. Si lo es, hacen algo con ella (depende del problema).
2. Construyen todas las posibles extensiones de s, e invocan recursivamente al algoritmo con todas ellas.
Al diseñar un algoritmo backtraking debemos considerar los siguientes elementos:
Representación de la solución en una tupla (X1; : : : ; Xn).
Una función objetivo para determinar si la tupla a analizar es una solución.
Unas restricciones a los candidatos para rellenar la tupla:
Implícitas del problema. Valores que puede tomar cada valor Xi
Explícitas o externas al problema. Por ejemplo, problema mochila, el peso no debe superar la capacidad de la mochila.
Una función de poda para eliminar partes del árbol de Búsqueda
Organización del problema en un árbol de búsqueda
(Algoritmo genérico backtracking)
funcion BACKTRACKING_REC ( k , solucion[n])para j2Si
si ( PODA (k , j , solucion) == true ) hacersol[k]= jsi ( TEST_SOL (solucion) == true ) hacerdevolver solucionsi ( k < n )BACKTRACKING_REC(k+1,solucion[n])
Aplicaciones del Método La técnica de Backtracking es usada en
muchos ámbitos de la programación, por ejemplo, para el cálculo de expresiones regulares o para tareas de reconocimiento de texto y de sintaxis de lenguajes regulares.
También es usado incluso en la
implementación de algunos lenguajes de programación,