A COMPLEXIDADE E PROJETOS DE ALGORITIMOS

UNIVERSIDADE FEDERAL DE LAVRAS

CIÊNCIA DA COMPUTAÇÃO

COMPLEXIDADE E PROJETOS DE ALGORITIMOS

Branch-and-Bound e Backtracking

LAVRAS

2020

Sumário

1.        Introdução        3

2.        Backtracking        4

3.        Branch and bound        9

4.        Diferenças        12

5.        Conclusão        13

6.        Referencias        14

1. Introdução

A força bruta pode ser eficiente na resolução de problemas simples na área de computação, devido ao grande poder já presente nos computadores atuais. Contudo, existem casos em que a complexidade da situação exige técnicas mais sofisticadas, sendo uma delas o backtracking e o branch and bound. Estas técnicas de algoritmo são generalizadas podendo ser facilmente modificada para um problema específico.

Com isso será abordado as principais características destes algoritmos e exemplos do funcionamento, além de analisar a diferença entre eles.

1. Backtracking

Backtracking é um método para percorrer todas as possíveis configurações em um problema qualquer. Ele consiste em um algoritmo genérico que pode ser modificado para cada tipo de aplicação.

Pode se dizer que backtracking seja um algoritmo de tentativa e erro, pois é justamente isto que ele faz, porém de maneira otimizada e exponencial. O problema genérico que ele tenta solucionar é descobrir a melhor sequência de decisão para resolver um problema cujo faltam informações para tomar as decisões corretas de primeira tentativa. Para exemplificar de forma genérica pode se pensar na seguinte situação.

Suponha que você tenha que tomar uma série de decisões dentre de várias possibilidades para resolver um problema. No entanto, você não tem informação suficiente para saber o que escolher, cada decisão irá encadear um novo conjunto de decisões e alguma das sequências de escolha pode ser a solução para seu problema. Logo, o objetivo é tentar diversas sequências de decisões até encontrar uma que funcione e resolva o problema.

[pic 1] 

Agora pensando em um algoritmo, deve se escolher uma sequência de decisão plausível, executar as operações desta sequência, se não resolver o problema deve se repetir o processo com outra sequência até que o problema seja resolvido ou se evidencie a insolubilidade do problema. Nesta descrição é possível observar que o método principal do algoritmo depende da recursividade.

A recursividade pode ser usada para resolver problemas cuja solução é do tipo tentar todas as alternativas possíveis, que é justamente o método que se utiliza no backtracking. Este processo de tentativa cria gradualmente uma árvore de subtarefas que será percorrida de nó a nó. Assim a cada passo em direção a solução final é registrada em uma estrutura de dados, e caso esses passos não resolva o problema, eles podem ser retirados e apagados da estrutura de dados.

A busca na árvore pode ser exaustiva, por isso é necessário usar algoritmos aproximados ou heurísticas que sejam rápidos, melhorando a eficiência do algoritmo ao todo. A seguir será mostrado as principais características do algoritmo e sua aplicabilidade, tomando o problema “Passeio do cavalo” como exemplo.

1. Características

        Pode se separar as principais características do backtracking a fim de posteriormente realizar comparações com outros algoritmos. Neste caso nos próximos tópicos será explorado a diferença entre o backtracking e branch-and-bound.

        Iniciando com as definições básicas sabe se que o backtracking é um algoritmo de tentativas e erro, logo ele não segue regra fixa de computação. Tendo isso definido pode se dizer que o backtracking:

• Toma passos em direção a solução final são tentados e registrados;
• Caso esses passos tomados não levem a solução final, eles podem ser retirados e apagados do registro;
• Quando a pesquisa na árvore de soluções cresce rapidamente é necessário usar algoritmos aproximados ou heurísticas que não garantem a solução ótima mas são rápidos;
• O número de escolhas cresce pelo menos exponencialmente com o tamanho da instância;
• Constrói a solução, um componente por vez, tentando terminar o processo mais rápido possível identificar que uma solução não poderá ser feita obtida em razão das escolhas feitas;
• Esta técnica torna possível a resolução de muitos problemas NP-difícil com instâncias grandes em um tempo aceitável;
• Elimina um nó se for garantido que ele não levará a obtenção de uma solução para o problema;
• Faz busca em profundidade.

        Backtracking garante o acerto por enumerar todas as possibilidades sem visitar nunca o mesmo estado tornando-o eficiente. A recursividade promove a elegância e a fácil implementação desse algoritmo, pois o vetor com novos candidatos é alocado de forma recursiva.

1. Passeio do Cavalo

        O problema do cavalo ou passeio do cavalo é um problema matemático que envolve o movimento da peça do cavalo no tabuleiro de xadrez. Seguindo as regras do jogo de xadrez, a peça do cavalo é posto em uma posição qualquer em um tabuleiro vazio e então o cavalo deve percorrer todas as casas do tabuleiro exatamente uma vez, retornando, atacando a casa no qual ele iniciou.

        Para este problema existe 26.534.728.821.064 soluções com caminhos denominados “fechados”. As soluções de caminho fechado são soluções onde a peça do cavalo percorre todas as casas e retorna a posição inicial. A grande dificuldade deste problema se dá pela a forma que a peça do cavalo se movimenta segundo as regras do xadrez. A peça deve sempre se movimentar em forma de “L” sendo 3 passos em linha reta na horizontal ou vertical e depois um passo para direita ou esquerda.