Please enable JavaScript.
Coggle requires JavaScript to display documents.
Backtracking - Coggle Diagram
Backtracking
Duas técnicas de design de algoritmos que tornam possível resolver o problema pelo menos algumas instâncias de problemas combinatoriais dificéis.
Branch and Bound
Aplicável para problemas de otimização pois vai se basear nos possíveis valores da função de objetivo do problema.
-
Comparado ao backtracking, o branch and bound precisa de um jeito de dar a cada nó da árvore um LIMITE da melhor solução da função objetiva em qualquer solução que pode ser obtida ao adicionar mais componentes na solução representada pelo nó. Além disso, ela precisa manter o valor da melhor solução vista até o momento.
Sabendo disso, a gente compara o limite de um nó com o valor da melhor solução vista até o momento, se o limite (o quão bom pode se tornar aquela solução) não é melhor que o melhor valor de solução visto até agora, então não adianta continuar essa branch.
Não continuamos se: o limite não é melhor que a melhor solução vista até o momento, o nó viola as constraints do problema, não conseguimos mais avançar a partir daquele nó.
São ambas melhores que Busca Exaustiva, pois vão construir Candidatos que são potenciais soluções que vão sendo construídas um componente por vez. Se não há como prosseguir no candidato, então o algoritmo "volta" e não gera os componentes restantes do candidato.
São baseados na construções de uma árvore State-Space cujos nós refletem escolhas feitas para os componentes de uma solução. Ambas técnicas "podam" o nó quando se considera que pode ser garantido que nenhuma solução a partir daquele nó (e dos seus descendentes) é válida.
Mais flexível que o Branch and Bound, geralmente se aplica a problemas de não otimização. Gera a árvore State-Space em profundidade.
Dizemos que um nó em uma árvore Space-State tem potencial se corresponde a uma solução parcialmente construída que ainda pode gerar uma solução completa (Promising).
Se não pode, chamamo-o de NonPromising
n-Queens Problem
Problema: Posicionar N Rainhas em um tabuleiro de xadrez N x N tal que duas rainhas não se ataquem estando na mesma coluna, na mesma linha ou na mesma diagonal.
Vamos tentar posicionar rainhas uma por uma, a fim de posicionarmos todas (tendo assim uma solução completa).
Circuito hamiltoniano
Problema: Encontrar um circuito hamiltoniano em um certo grafo (Circuito de forma a passar por todos os nós sem repetição e voltar para o começo).
Começa de um vértice genérico e deve voltar a ele, andando pelos seus adjacentes, respeitando algum tipo de ordem arbitrariamente escolhida (Alfabética, por exemplo).
É importante notar que podemos ter os mesmos caminhos sendo construídos a depender do vértice que começamos (Já que é um CIRCUITO). Exemplo: ABFECDA = ADCEFBA
Subset Sum Problem
Problema: Encontrar um subconjunto de um dado set de n inteiros positivos cuja soma é igual a um inteiro positivo d ( nosso alvo).
É conveniente sortar o conjunto em ordem crescente, desse jeito, quando a soma de um conjunto for maior que d, sabemos que o candidato não é válido.
O filho à esquerda de um nó significa a inclusão do próximo elemento e o filho à direita significa a exclusão do próxima elemento.
Existem "truques" que aumentam a eficiência de um backtracking baseado em alguma propriedade do problema a ser resolvido, mas não é sempre.