fisica

Estructuras de Datos y Algoritmos II

© Yeray Saíz Celorrio &
Ainhoa Uribe Leiva

Tema 6: Técnica de vuelta atrás: Backtrack

1

Estructuras de Datos y Algoritmos II

Tema 6: Técnica de vuelta atrás: Backtrack

Índice
6.1 Introducción
•
•

p3

6.1.1 Ejemplo: Problema del agente viajero
6.1.2 Esquema General del Algoritmo

6.2 Problema de la Mochila
•
•
•
•
•
•
•p6

6.2.1 Estudio del problema
6.2.2 Ensayo
6.2.3 Condiciones de aceptabilidad
6.2.4 Algoritmo de la Mochila
6.2.5 Análisis sobre el tipo de estructura para tratar el resultado
6.2.6 Análisis del orden
6.2.7 Poda de ramas más eficiente

6.3 Problema del coloreado de mapas
•
•
•
•
•

6.3.1 Estudio del problema
6.3.2 Ensayo
6.3.2 Posibilidad de extender un ensayo
6.3.4 Algoritmode los cuatro colores
6.3.5 Análisis del algoritmo

6.4 Suma de Subconjuntos
•
•
•
•

p4
p5

p6
p7
p8
p 9
p 10
p 12
p 13

p 14
p 14
p 15
p 15
p 17
p 18

p 19

6.4.1 Estudio del problema
6.4.2 Ensayo
6.4.3 Posibilidad de extender un ensayo
6.4.4 Mejora de la solución anterior
6.4.4.1 Algoritmo

p 19
p 19
p 20
p 21
p 22

6.5 Problema de la Mochila: Revisitedp 23

6.6 Bibliografía

p 25

© Yeray Saíz Celorrio &
Ainhoa Uribe Leiva

2

Estructuras de Datos y Algoritmos II

Tema 6: Técnica de vuelta atrás: Backtrack

TEMA 6: TÉCNICA DE VUELTA ATRÁS: BACKTRACK
6.1 Introducción
Los algoritmos de vuelta atrás (BACKTRACK) hacen una búsqueda
sistemática de todas las posibilidades, sin dejar ninguna por considerar.
Cuando intenta unasolución parcial (ensayo), que no lleva a una solución,
retrocede deshaciendo el último paso, e intentando una nueva variante
desde esa posición (es normalmente de naturaleza recursiva).
Esta técnica ofrece un método para resolver problemas tratando de
completar una o varias soluciones por etapas. En cada paso se intenta
extender un ensayo de todos los modos posibles, y si ninguno resultasatisfactorio se produce la vuelta atrás hasta el último punto donde
quedaban alternativas por explorar. Es una mejora de la búsqueda completa
de soluciones y una alternativa a los algoritmos voraces.
Mejoras en el esquema de BACKTRACK:
• Poda del árbol de vuelta atrás: Consiste en la eliminación de
posibilidades (poda del árbol):
o

o

o

Exclusión previa: Tras un análisis previo, puedeorganizarse la
búsqueda para que ignore situaciones infructuosas (ejemplo:
problema 8 reinas, cuando ponemos cada dama en una fila
diferente).
Fusión de ramas: Cuando la búsqueda a partir de diferentes
ramas lleve a la misma solución, podemos limitar la búsqueda
(por ejemplo en problemas con simetría como el de las 8
reinas o el del PAV).
Ramificación y acotamiento: Cuando lo que se busca esuna
solución óptima, es posible reducir el árbol de búsqueda
abandonando las ramas que se sepa con certeza que no llevan
hacia soluciones óptimas. (por ejemplo en el problema del
viajante podríamos tener una variable T que almacene el valor
más óptimo hasta el momento, y abortar un camino en el
mismo momento en que se rebase T).

• Reordenación de la búsqueda: Consiste en reorganizar lasramas del
árbol de búsqueda de manera que se analicen primero las situaciones
con mejores expectativas. Permite por tanto resolver más
rápidamente el problema.
© Yeray Saíz Celorrio &
Ainhoa Uribe Leiva

3

Estructuras de Datos y Algoritmos II

Tema 6: Técnica de vuelta atrás: Backtrack

6.1.1. Ejemplo: Problema del agente viajero (PAV):
Encontrar un recorrido de longitud mínimapara un viajante que
tiene que visitar varias ciudades y volver al punto de partida, conocida la
distancia existente entre cada dos ciudades.
El matemático irlandés William Hamilton (1805 – 1865) en el año
1857 desarrolló un juego que consistía en buscar un recorrido que diera la
vuelta al mundo. Este juego se representaba por medio de un dodecaedro,
consistía en ir visitando cada ciudad una...