BackTracking

Sumário
Backtracking 1
Conceitos sobre a técnica de Backtracking 1
Características do Backtracking 1
Funcionamento do Backtracking 2
Exemplo de Busca em Profundidade 2
Exemplo do Problema da Mochila 3
Conclusão 4
Referências 5

Backtracking

Conceitos Sobre a Técnica de Backtracking

Significado: Volta de Rastreamento;
É um algoritmo baseado em estrutura de dados, tem como meta resolver o problema do menor intervalo de tempo, não levando em consideração o esforço para alcançar a solução;
Usa Recursividade

Características do Backtracking

Executa podas quando não é possível encontrar uma solução pelo caminho escolhido.
Faz a busca em profundidade.
O número de escolhas cresce pelo menos exponencialmente com o tamanho da instância.
Passos em direção à solução final são tentados e registrados.
Algoritmos tentativa e erro.

Funcionamento do Backtracking

Exemplo do Funcionamento

Exemplo de Busca em Profundidade

Exemplo: Problema da Mochila

Entrada:
Capacidade da mochila, K; n itens com pesos (pi) e valores (vi); o objetivo é obter um conjunto S de itens tais que:
A soma dos pesos dos itens em S seja menor ou igual a K;
A soma dos valores dos itens em S seja a maior possível.

Gerar todas as possíveis combinações
Com n itens, existem 2n soluções
Checar se cada solução satisfaz limite peso
Salvar a condição que melhor representa a solução
Pode ser representada como uma árvore

Se alcançamos um ponto em que a solução não é mais viável, não precisamos continuar explorando a solução.
Podemos “voltar atrás” (backtrack) a partir deste ponto.
No exemplo backtracking se torna bastante útil:
Na medida em que o número de itens cresce.
Na medida em que a capacidade da mochila diminui.

Pode-se voltar atrás também quando se sabe que a melhor solução da subárvore é pior do que a melhor solução já encontrada.
Fundamento utilizado por muitos algoritmos
Exemplo típico: Branch and Bound

CONCLUSÃO
Concluímos