A principal diferença entre backtracking e branch and bound é que o backtracking é um algoritmo para capturar algumas ou todas as soluções para determinados problemas computacionais, especialmente para problemas de satisfação de restrição, enquanto branch and bound é um algoritmo para encontrar a solução ideal para muitos problemas de otimização, especialmente em otimização discreta e combinatória.

Um algoritmo é uma sequência metódica de etapas para resolver um problema específico. Existem vários algoritmos, e dois deles são backtracking e branch and bound.

Retrocedendo, Ramificação e Limite

O que é retrocesso

Backtracking é um algoritmo que resolve o problema de maneira recursiva. É uma forma sistemática de tentar diferentes sequências de decisões para encontrar a decisão correta. Ele descobre a solução pesquisando metodicamente o espaço de solução do problema fornecido.

Todas as soluções para retrocesso precisam satisfazer um conjunto complexo de restrições explícitas e implícitas. A restrição explícita limita cada elemento do vetor a ser selecionado do conjunto fornecido. Além disso, a restrição implícita encontra as tuplas no espaço de solução que podem satisfazer a função de critério.

O que é Branch and Bound

Branch and bound é mais adequado para situações em que não podemos aplicar o método guloso e a programação dinâmica. Normalmente, esse algoritmo é lento, pois requer complexidades de tempo exponenciais durante o pior caso, mas às vezes funciona com eficiência razoável. No entanto, este método ajuda a determinar a otimização global em problemas não convexos.

Além disso, para resolver um problema, esse método divide o subproblema fornecido em pelo menos dois novos subproblemas restritos.

Diferença entre retrocesso e ramificação e limite

Definição

Backtracking é um algoritmo para encontrar todas as soluções para alguns problemas computacionais, notavelmente problemas de satisfação de restrição que constrói de forma incremental candidatos para as soluções. Branch and bound é um algoritmo para problemas de otimização discreta e combinatória e otimização matemática. Portanto, esta é a principal diferença entre retrocesso e ramificação e limite.

Processo

Além disso, o retrocesso encontra a solução para o problema geral, encontrando uma solução para o primeiro subproblema e, recursivamente, resolvendo outros subproblemas com base na solução do primeiro problema. No entanto, branch and bound resolve um determinado problema dividindo-o em pelo menos dois novos subproblemas restritos. Portanto, esta é outra diferença entre retrocesso e ramificação e limite.

Eficiência

Conclusão

Backtracking é um algoritmo para capturar algumas ou todas as soluções para determinados problemas computacionais, especialmente para problemas de satisfação de restrição. Branch and Bound, por outro lado, é um algoritmo para encontrar soluções ótimas para muitos problemas de otimização, especialmente em otimização discreta e combinatória. Essa é a principal diferença entre Backtracking e Branch and Bound.

Referência:

1. “DAA Algorithm Design Techniques - Javatpoint.” Www.javatpoint.com, disponível aqui.2. “Introdução ao Backtracking - Javatpoint.” Www.javatpoint.com, disponível aqui.3. “Retrocedendo.” Wikipedia, Wikimedia Foundation, 7 de dezembro de 2018, disponível aqui.4. “Branch and Bound.” Wikipedia, Wikimedia Foundation, 8 de outubro de 2018, disponível aqui.5. “O que está retrocedendo? - Definição da Techopedia. ” Techopedia.com, disponível aqui.

Cortesia de imagem:

1. “Algoritmos vs. Linguagens de Programação ”Por Lubaochuan - Trabalho do próprio (CC BY-SA 4.0) via Commons Wikimedia