Diferencia entre la técnica Backtracking y Branch-N-Bound

Los algoritmos son la secuencia metódica de pasos que se definen para resolver problemas complejos. En este artículo, veremos la diferencia entre dos algoritmos de este tipo, que son el retroceso y la técnica de ramificación y límite. 

Antes de entrar en las diferencias, primero comprendamos cada uno de estos algoritmos. 

Backtracking: Backtracking es un algoritmo general para encontrar todas las soluciones a algunos problemas computacionales, en particular problemas de satisfacción de restricciones, que construye de manera incremental posibles candidatos a las soluciones y abandona un candidato tan pronto como determina que el candidato no puede completarse para finalmente convertirse en un solución válida. Es una técnica algorítmica para resolver problemas recursivamente al tratar de construir una solución de forma incremental, una pieza a la vez, eliminando aquellas soluciones que no satisfacen las restricciones del problema en cualquier punto del tiempo (por tiempo, aquí, se hace referencia a el tiempo transcurrido hasta llegar a cualquier nivel del árbol de búsqueda). 

Branch and Bound: Branch and Bound es un paradigma de diseño de algoritmos para problemas de optimización discreta y combinatoria, así como optimización matemática. Un algoritmo de ramificación y acotación consiste en una enumeración sistemática de soluciones candidatas. Es decir, se piensa que el conjunto de soluciones candidatas forma un árbol enraizado con el conjunto completo en la raíz. El algoritmo explora las ramas de este árbol, que representan los subconjuntos del conjunto de soluciones. Antes de enumerar las soluciones candidatas de una rama, la rama se compara con los límites estimados superior e inferior de la solución óptima y se descarta si no puede producir una solución mejor que la mejor encontrada hasta ahora por el algoritmo. 

La siguiente tabla explica la diferencia entre ambos algoritmos: 

Parámetro	retrocediendo	Rama y atado
Acercarse	El retroceso se utiliza para encontrar todas las posibles soluciones disponibles para un problema. Cuando se da cuenta de que ha hecho una mala elección, deshace la última elección respaldándola. Busca en el árbol de espacio de estados hasta que encuentra una solución para el problema.	Branch-and-Bound se utiliza para resolver problemas de optimización. Cuando se da cuenta de que ya tiene una mejor solución óptima a la que conduce la pre-solución, abandona esa pre-solución. Busca completamente el árbol de espacio de estado para obtener una solución óptima.
El recorrido	El retroceso atraviesa el árbol de espacio de estado de la manera DFS (búsqueda primero en profundidad) .	Recorra el árbol de cualquier forma, DFS o BFS .
Función	El retroceso implica la función de viabilidad.	Branch-and-Bound implica una función de delimitación.
Problemas	El retroceso se utiliza para resolver problemas de decisión.	Branch-and-Bound se utiliza para resolver problemas de optimización.
buscando	En backtracking, se busca en el árbol de espacio de estado hasta que se obtiene la solución.	En Branch-and-Bound, la solución óptima puede estar presente en cualquier parte del árbol de espacio de estado, por lo que es necesario buscar el árbol por completo.
Eficiencia	El retroceso es más eficiente.	Branch-and-Bound es menos eficiente.
Aplicaciones	Útil para resolver el problema N-Queen , Suma de subconjunto .	Útil para resolver el problema de la mochila , el problema del vendedor ambulante .
Resolver	El retroceso puede resolver casi cualquier problema. (ajedrez, sudoku, etc.).	Branch-and-Bound no puede resolver casi ningún problema.