Método de Retroceso (backtracking)

Método de Retroceso (backtracking)

1. El Backtracking o vuelta atrás es una técnica de resolución general deproblemas mediante una búsqueda sistemática de soluciones. Elprocedimiento general se basa en la descomposición del proceso debúsqueda en tareas parciales de tanteo de soluciones (trial and error)

   • Diversas estrategias heurísticas, frecuentemente dependientes delproblema, establecen las reglas para decidir en que orden se tratan las tareasmediante las que se realiza la ramificación del árbol de búsqueda, y quéfunciones se utilizan para provocar la poda del árbol

2. La descripción natural del proceso se representa por un árbol de búsquedaen el que se muestra como cada tarea se ramifica en subtareas. El árbol debúsqueda suele crecer rápidamente por lo que se buscan herramientaseficientes para descartar algunas ramas de búsqueda produciéndose la podadel árbol

3. El problema típico es el conocido como problema de la mochila. Sedispone de una mochila en la que se soporta un peso máximo P en la que sedesean introducir objetos que le den el máximo valor. Se dispone de unacolección de n objetos de los que se conoce su peso y su valor;

   • (pi,vi); i = 1, 2, ..., n

Bilder und Dateien der Mindmap