Please enable JavaScript.
Coggle requires JavaScript to display documents.
Backtracking e branch-and-bound - Coggle Diagram
Backtracking e branch-and-bound
São dois algoritmos que fazem possível resolver ao menos alguma instâncias grandes, de problemas de dificuldade combinatória.
Ambas as estratégias podem ser consideradas melhorias sobre a busca exaustiva, porém, no pior caso, acontece o mesmo problema de explosão exponencial da busca exaustiva.
Ambos backtracking e branch-and-bound são baseados na construção de uma
árvore de estado de espaços (state-space tree)
na qual seus nós, refletem escolhas específicas, feitas para a solução de componentes.
Ambas as técnicas terminam um nó, logo que é garantido que nenhuma solução para o problema pode ser obtida a partir dos seus descendentes.
Dependendo da natureza do problema aplicado essas técnicas se diferem.
Branch-and-bound é aplicável somente na otimização de problemas, porque é baseado em computar um limite em possíveis valores de funções objetivas do problema.
Backtracking não está limitado à essa demanda, e é frequentemente usado em problemas de não-optimização.
Outra distinção entre essas duas técnicas é a ordem dos nós na árvore de estado de espaço.
No backtracking a árvore é desenvolvida como depth-first, similar à DFS.
No branch-and-bound os nós são gerados de acordo com várias regras: a mais natural é uma chamada melhor primeira regra.
Backtracking
Backtracking é uma variação mais inteligente do problema de busca exaustiva.
A principal ideia é construir soluções, um componente por vez, e avaliar cada candidato parcialmente construído da seguinte forma.
Se uma solução parcialmente construída pode ser desenvolvida sem violar as condições do problema, ela é feita pegando a primeira opção legítima restante para o próximo componente.
Se não existir opções legítimas para o próximo componente, nenhuma alternativa para quaisquer componentes restantes precisa ser considerada.
Neste caso o algoritmo volta para substituir o último componente da solução parcialmente construída com sua próxima opção.
É conveniente implementar este tipo de processamento, construindo uma árvore de escolhas que estão sendo feitas, chamada
árvore de estado de espaços (state-space tree)
.
Sua raiz representa o estado inicial antes do início da busca pela solução.
Os nós do primeiro nível da árvore representam as escolhas feitas para o primeiro componente de uma solução, os nós do segundo nível representam as escolhas para o segundo componente e assim por diante.
Um nó nesta árvore é dito
promissor (promising)
se ele corresponde à uma solução parcialmente construída que pode levar à uma solução completa; de outro modo é chamado
não-promissor
.
Folhas ou são becos sem saída não-promissor ou são soluções completas encontradas pelo algoritmo.
Na maioria dos casos a árvore é construída de maneira DFS para o algoritmo de backtracking.
Se o nó atual é promissor, seu filho é gerado adicionando a primeira opção legítima para o próximo componente de uma solução, e o processamento move para o seu filho.
Se o nó atual é não-promissor, o algoritmo volta para o seu pai para considerar a próxima opção possível para o seu último componente; se não existir essa opção, ele volta mais um nível na árvore e assim por diante.
Finalmente, se o algoritmo chega a uma solução completa para o problema, ou ele para, ou ele continua procurando para outras possíveis soluções.
Problema n-Rainhas
O problema é colocar
n
rainhas em um tabuleiro
n x n
de xadrez, de forma que nenhuma rainha seja atacada por outra estando na mesma linha ou coluna ou diagonal.
No problema de 4-rainhas em um tabuleiro
4 x 4
, uma linha diferente é atribuída para cada rainha.
Começando num tabuleiro vazio a rainha 1 é colocada na primeira posição possível da sua linha, que seria na coluna 1 (1, 1). Então, é colocada a rainha 2 na primeira opção possível da linha 2 que seria então a coluna 3 (2,3). Porém, não sobra posições possíveis para a rainha 3. Então é feito o backtracking para a rainha 2.
A rainha 2 é colocada na próxima posição possível que é a coluna 4 (2,4). A rainha 3 portanto consegue encontrar uma posição na próxima linha e é na coluna 2 (3,2). Porém não sobra posições possíveis para a rainha 4. Então é feito o backtracking para a rainha 1.
A rainha 1, então, é movida para a próxima coluna (1,2). A rainha 2 vai para a coluna 4 (2, 4). A rainha 3 encontra uma posição na coluna 1 (3,1). E, por fim, há uma solução para a rainha 4 na coluna 3 (4,3), que é a solução para o problema.
Problema de circuito hamiltoniano
Podemos assumir que, se existir um circuito hamiltoniano ele começa no vértice
a
. Esse vértice
a
portanto, será a raiz da árvore de estado de espaços.
O primeiro componente da futura solução, se existir, é um primeiro vértice intermediário de um circuito Hamiltoniano a ser construído.
O algoritmo vai então, indo da raiz e passando pelos vértices até chegar à uma solução, ou, à um final sem saída, fazendo assim um backtracking e testando outros vértices, até uma solução ser encontrada (ou não).
Uma saída de um algoritmo backtracking pode ser pensando como uma
n
-tupla (x1, x2, ..., xₙ) onde cada coordenada
x
ᵢ é um elemento de algum conjunto
S
ᵢ finito linearmente ordenado.
O backtracking é tipicamente aplicado para problemas de dificuldade combinatória, os quais não existem algoritmos eficientes para encontrar soluções exatas.
Diferente da busca por exaustão, que é extremamente lento para todas as as instâncias de um problema, o backtracking ao menos dá esperança de resolver algumas instâncias de tamanhos não-triviais em uma quantidade aceitável de tempo.
Mesmo que o backtracking não elimine nenhum elemento de um estado de espaço do problema e termine gerando todos os seus elementos, ele proporciona uma técnica específica que pode ser de valor.
Branch-and-bound
Um problema de otimização procura minimizar ou maximizar alguma função objetiva, usualmente sujeita a algumas condições.
Em uma terminologia padrão de otimização de problemas, uma
solução viável (feasible solution)
é um ponto no espaço de procura do problema que satisfaz todas as condições do problema. E, uma
solução ótima (optimal solution)
é uma solução viável com o melhor valor da função objetiva.
Comparado ao backtracking, o branch-and-bound requere dois itens adicionais:
um jeito de proporcionar, para cada nó da árvore de estado de espaços, um limite no melhor valor da função objetiva, em qualquer solução que pode ser obtida adicionando mais componentes para a solução parcialmente construída representada pelo nó.
o valor da melhor solução vista até aqui.
Se a informação estiver disponível, o valor limite do nó é comparado com o valor da melhor solução vista até aqui.
Se o valor limite não for melhor que o valor da melhor solução vista, o nó é não-promissor e pode ser terminado. De fato, nenhuma solução obtida pode produzir uma solução melhor do que a que já está disponível. Essa é a principal ideia da técnica branch-and-bound.
Em geral, nós terminamos um caminho de busca no nó atual, em uma árvore de estado de espaços, de um algoritmo branch-and-bound, por quaisquer das seguintes razões:
Quando o valor do limite do nó não é melhor que o valor da melhor solução vista até aqui.
Quando o nó não representa soluções viáveis porque as condições do problema já são violadas.
Quando o subconjunto de soluções viáveis representada pelo nó consiste de um único ponto, neste caso nós comparamos o valor da função objetiva para esta solução viável com a melhor solução vista até aqui e atualizamos a última com a primeira se a nova solução for melhor.
Problema do caxeiro viajante
Um limite inferior simples pode ser obtido encontrando o menor elemento na matriz de distância interurbana
D
e multiplicando pelo número de cidades
n
.
Podemos aplicar a técnica branch-and-bound para instâncias do problema se encontrarmos um limite inferior razoável nos tamanhos da tour.
Dado um conjunto de cidades e a distância entre cada par de cidades, temos que encontrar a menor rota possível que visita cada cidade exatamente 1 vez e retorna à cidade inicial.
Encontrar uma boa função limite não é uma tarefa simples. Essa função tem que ser simples de computar, porém não pode ser muito simplista, ou vai falhar na sua principal tarefa que é aparar tantos galhos da árvore de estado de espaços quanto for possível.