Retrocesso (Backtracking) e Ramificação e Limitação (Branch and Bound)

Retrocesso e ramificação e limitação são paradigmas de busca sistemática que exploram o espaço de soluções candidatas como uma árvore, podando subárvores que não podem levar a uma solução válida ou ótima para tornar as buscas, de outra forma exponenciais, tratáveis na prática.

Definition

Retrocesso é uma busca em profundidade na árvore de soluções candidatas parciais que poda um ramo no momento em que o candidato parcial não pode ser completado para uma solução válida; ramificação e limitação aumenta isso com limites numéricos no objetivo para que ramos cujo melhor valor possível não possa superar o incumbente sejam descartados.

Scope

Este tópico abrange técnicas de busca exaustiva organizadas em torno de uma árvore de busca: retrocesso, que abandona candidatos parciais assim que violam uma restrição, e ramificação e limitação, que usa limites no melhor objetivo alcançável para podar subárvores na otimização. Inclui exemplos de satisfação de restrições (N-rainhas, coloração de grafos, Sudoku) e exemplos de otimização combinatória (problema do caixeiro viajante, programação inteira), e discute por que esses métodos permanecem valiosos para problemas NP-difíceis, apesar do custo exponencial no pior caso.

Core questions

• Como o espaço de soluções de um problema é modelado como uma árvore de busca de atribuições parciais?
• Quais verificações de restrição permitem que o retrocesso pode ramos inviáveis precocemente?
• Como os limites inferior e superior são calculados para podar ramos na otimização?
• Como a ordem de ramificação e limitação afeta o desempenho prático?
• Por que esses métodos são usados para problemas NP-difíceis, apesar dos piores casos exponenciais?

Key concepts

• árvore de busca
• exploração em profundidade
• propagação de restrições
• poda
• funções de limitação
• solução incumbente
• problema das N-rainhas
• relaxamento de programação inteira

Key theories

Poda da árvore de busca

Ambos os paradigmas organizam as soluções candidatas como uma árvore explorada em profundidade; a correção vem da exaustividade, enquanto a eficiência vem da poda de subárvores que comprovadamente não podem conter uma solução válida ou melhorada.

Funções de limitação em ramificação e limitação

Ramificação e limitação mantém a melhor solução encontrada até agora e um limite (por exemplo, um relaxamento LP) para o melhor valor atingível em cada subárvore; uma subárvore é descartada quando seu limite não pode melhorar o incumbente.

Clinical relevance

Ramificação e limitação é a espinha dorsal da otimização combinatória exata em pesquisa operacional, incluindo resolvedores de programação inteira e mista-inteira usados para agendamento, roteamento e planejamento. O retrocesso sustenta resolvedores de restrições, busca estilo SAT, resolvedores de quebra-cabeças e analisadores sintáticos, onde a busca sistemática com poda é o caminho prático para respostas exatas.

History

O retrocesso foi sistematizado como uma técnica geral nas décadas de 1950 e 1960, notavelmente descrito por Golomb e Baumert. A ramificação e limitação foi introduzida por Ailsa Land e Alison Doig em 1960 para programação linear inteira e desde então se tornou central para a otimização combinatória, impulsionando os modernos resolvedores de programação mista-inteira.

Key figures

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

Seminal works

• landdoig1960
• cormen2009

Frequently asked questions

Qual é a diferença entre retrocesso e ramificação e limitação?

O retrocesso é tipicamente usado para problemas de viabilidade e satisfação de restrições e poda ramos que violam restrições. A ramificação e limitação visa a otimização e, adicionalmente, poda usando limites numéricos, descartando qualquer subárvore cujo melhor objetivo possível não possa superar a melhor solução já encontrada.

Se esses métodos são exponenciais no pior caso, por que usá-los?

Para problemas NP-difíceis, nenhum algoritmo exato polinomial é conhecido, mas a poda eficaz frequentemente elimina a vasta maioria da árvore de busca em instâncias reais, de modo que os resolvedores de ramificação e limitação e retrocesso regularmente encontram soluções comprovadamente ótimas muito mais rapidamente do que seus limites de pior caso sugerem.