Backtracking y Branch and Bound

El backtracking y el branch and bound son paradigmas de búsqueda sistemática que exploran el espacio de soluciones candidatas como un árbol, podando subárboles que no pueden conducir a una solución válida u óptima para hacer que las búsquedas, de otro modo exponenciales, sean tratables en la práctica.

Definition

El backtracking es una búsqueda en profundidad del árbol de soluciones candidatas parciales que poda una rama en el momento en que el candidato parcial no puede completarse a una solución válida; el branch and bound aumenta esto con límites numéricos en el objetivo para que las ramas cuyo mejor valor posible no pueda superar al actual sean descartadas.

Scope

Este tema cubre las técnicas de búsqueda exhaustiva organizadas en torno a un árbol de búsqueda: backtracking, que abandona los candidatos parciales tan pronto como violan una restricción, y branch and bound, que utiliza límites en el mejor objetivo alcanzable para podar subárboles en la optimización. Incluye ejemplos de satisfacción de restricciones (N-reinas, coloración de grafos, Sudoku) y ejemplos de optimización combinatoria (problema del viajante, programación entera), y discute por qué estos métodos siguen siendo valiosos para problemas NP-difíciles a pesar del costo exponencial en el peor de los casos.

Core questions

• ¿Cómo se modela el espacio de soluciones de un problema como un árbol de búsqueda de asignaciones parciales?
• ¿Qué comprobaciones de restricciones permiten que el backtracking pode ramas inviables tempranamente?
• ¿Cómo se calculan los límites inferiores y superiores para podar ramas en la optimización?
• ¿Cómo afectan el orden de ramificación y acotación al rendimiento práctico?
• ¿Por qué se utilizan estos métodos para problemas NP-difíciles a pesar de los peores casos exponenciales?

Key concepts

• árbol de búsqueda
• exploración en profundidad
• propagación de restricciones
• poda
• funciones de acotación
• solución actual
• problema de las N-reinas
• relajación de programación entera

Key theories

Poda del árbol de búsqueda

Ambos paradigmas organizan las soluciones candidatas como un árbol explorado en profundidad; la corrección proviene de la exhaustividad, mientras que la eficiencia proviene de podar subárboles que demostrablemente no pueden contener una solución válida o mejorada.

Funciones de acotación en branch and bound

El branch and bound mantiene la mejor solución encontrada hasta el momento y un límite (por ejemplo, una relajación LP) sobre el mejor valor alcanzable en cada subárbol; un subárbol se descarta cuando su límite no puede mejorar el actual.

Clinical relevance

El branch and bound es la columna vertebral de la optimización combinatoria exacta en la investigación de operaciones, incluyendo los solucionadores de programación entera y entera mixta utilizados para la programación, el enrutamiento y la planificación. El backtracking subyace a los solucionadores de restricciones, la búsqueda de tipo SAT, los solucionadores de rompecabezas y los analizadores sintácticos, donde la búsqueda sistemática con poda es la ruta práctica para obtener respuestas exactas.

History

El backtracking fue sistematizado como una técnica general en las décadas de 1950 y 1960, notablemente descrito por Golomb y Baumert. El branch and bound fue introducido por Ailsa Land y Alison Doig en 1960 para la programación lineal entera y desde entonces se ha vuelto central para la optimización combinatoria, impulsando los modernos solucionadores de programación entera mixta.

Key figures

• Ailsa Land
• Alison Doig
• Solomon Golomb
• Robert Bixby

Seminal works

• landdoig1960
• cormen2009

Frequently asked questions

¿Cuál es la diferencia entre backtracking y branch and bound?

El backtracking se utiliza típicamente para problemas de factibilidad y satisfacción de restricciones y poda ramas que violan las restricciones. El branch and bound se enfoca en la optimización y, además, poda utilizando límites numéricos, descartando cualquier subárbol cuyo mejor objetivo posible no pueda superar la mejor solución ya encontrada.

Si estos métodos son exponenciales en el peor de los casos, ¿por qué utilizarlos?

Para los problemas NP-difíciles no se conoce ningún algoritmo exacto polinomial, pero la poda efectiva a menudo elimina la gran mayoría del árbol de búsqueda en instancias reales, por lo que los solucionadores de branch-and-bound y backtracking encuentran regularmente soluciones óptimas demostrables mucho más rápido de lo que sugieren sus límites en el peor de los casos.