Algoritmos

URJC
 

Grado
 en
  ingeniería
  Informa>ca
 

Escuela
 técnica
 superior
  de
 ingeniería
  informá>ca
 

Diseño
 y
 análisis
  de
 algoritmos
 

Vuelta
 atrás
 


 
 
 
 
 
 
 
 
 
  Hernández
 Bermejo,
 Víctor
  Sepúlveda
 Blanco,
 Diego
 
 

CURSO
 2010-­‐2011
 Índice
 
1.
 Qué
 es
 vuelta
 atrás
 ..................................................................................................
 3
 
  Definición
 ...........................................................................................................
 3
 
  Estrategia
 de
 diseño
 de
 algoritmos
 ....................................................................
 3
  2.
 Funcionamiento
 ......................................................................................................
 4
 
  Función
 criterio
 y
 restricciones
 ..........................................................................
 4
 
  Árbol
 de
 exploración ..........................................................................................
 4
 
  Funciones
 de
 poda
 .............................................................................................
 4
 
  Nodos
 del
 árbol
 de
 exploración
 .........................................................................
 4
 
  Recorrido
 del
 árbol
 de exploración
 ....................................................................
 4
 
  Mejoras
 sobre
 la
 vuelta
 atrás
 ............................................................................
 5
  3.
 Esquemas
 de
 programación
 ....................................................................................
 6
 
  Esquema general
 ...............................................................................................
 6
 
  Marcaje
 ..............................................................................................................
 6
 
  Optimización
 ......................................................................................................
 7
  4. Ejemplos
 clásicos
 .....................................................................................................
 8
 
  Ejemplo
 de
 la
 mochila
 ........................................................................................
 8
 
  El
 problema
 de
 las
 ocho
 reinas ........................................................................
 10
 
  El
 problema
 de
 las
 seis
 ranas
 ...........................................................................
 12
  5.
 Aplicaciones
 de
 la
 técnica
 en
 problemas
 reales
 ....................................................
 13
 
  Ariadne’s
 thread ..............................................................................................
 13
 
  Optimización
 ....................................................................................................
 14
 
  Isomorfismo
 de
 grafos
 .....................................................................................
 14
 
  Bibliografía ................................................................................................................
 15
 
  Anexo
 A:
 Código
 vuelta
 atrás
 en
 Java
 para
 el
 problema
 de
 las
 seis
 ranas
 ................
 16
 
  Clase
 Charca.java
 .............................................................................................
 16
 
 ...