Please enable JavaScript.
Coggle requires JavaScript to display documents.
Limitações do poder do algoritmo, Essa técnica tem dois itens que a…
Limitações do poder do algoritmo
Muitos problemas são difíceis de resolver com algoritmos em tempo polinomial, porém alguns desses problemas são tão importantes que não podemos simplesmente ignorá-los
Backtracking e Branch-and-bound
são estratégias que ajudam a resolver algumas instâncias grandes desses problemas (combinatórios)
Essa estratégia consiste em ir construindo uma possível resposta gerando componente a componente, caso nenhum valor dos componentes restantes possam gerar uma solução, então eles não são gerados
Ambas usam um tipo de árvore chamada de state-space tree
Essas duas técnicas constroem essa árvore de maneira diferente, a Backtracking constrói de maneira Depth-first enquanto a Branch-and-bound pode seguir diferentes regras de geração, porém a mais comum é a best-first (que deve ser explicada adiante)
Backtracking
Existem alguns problemas que consistem em encontrar um elemento com propriedades especificas em um domínio que cresce exponencialmente de acordo com a entrada, esse tipo de problema "não pode" ser resolvido em tempo polinomial, a menos que nós usemos alguma técnica especifica para algumas instâncias desse problema, como por exemplo, criar uma lista de elementos candidatos a respeitar tais propriedades, e em seguida ver quais deles realmente respeita
"Se o nó atual for promissor, seu filho será gerado adicionando-se a primeira opção legítima restante para o próximo componente de uma solução e o processamento será movido para esse filho. Se o nó atual revelar-se não promissor, o algoritmo retrocede até o pai do nó para considerar a próxima opção possível para seu último componente; se não houver essa opção, ele volta mais um nível acima na árvore e assim por diante". O algoritmo pode parar quando encontrar uma solução completa ou pode procurar por outras
Essa lista é feita através de uma árvore e de componente em componente (formando a árvore, sendo cada componente um vértice), se "estamos" em um componente e vemos que se adicionarmos outro componente ele pode ser uma solução, então isso é feito (como uma DFS)
Nessa árvore a raiz é o estado inicial da árvore antes da busca começar, no primeiro nível, são os elementos escolhidos para ser o primeiro componente, no segundo nível são os que representam o segundo componente e assim vai
Um nó dessa árvore é chamado de
promissor
se ele fizer parte de uma solução parcialmente construída que ainda pode levar a uma solução completa, do contrário ele é chamado de
não promissor
As folhas podem ser galhos que acabam em nós não promissores ou podem ser soluções completas
Alguns problemas que podem ser resolvidos com essa técnica:
Probelma das N-rainhas
Problema do Circuito hamiltoniano
Um dos problemas que esse método pode trazer é se a árvore crescer tanto que dê algum limite excedido (memória ou tempo)
Algumas "técnicas" podem utilizadas para dificultar a ocorrência desses problemas:
??explorar a simetria dos problemas de combinação??
Fixar valores para alguns componentes (assim como foi feito no exemplo do problema hamiltoniano contido no livro do Levithin)
Não serve para otimização
Na volta das chamadas recursivas que não foram bem sucedidas, temos que desmarcar a opção vista anteriormente
Branch-and-bound
Uma
solução viável
é um "elemento" que satisfaz todas as restrições do problema
Já a
solução ótima
é a solução viável com o melhor valor (dependendo do que se trata), por exemplo, dentre se é pedido um caminho de v para u em um grafo com pesos, todos caminhos possíveis são soluções viáveis, porém a solução ótima é o menor deles
Problemas de otimização
A ideia é quando estiver em um vértice que não seja o final, comparar seu valor com o melhor valor possível, se ele não for melhor que o melhor possível (que é o valor de uma solução completa), então esse vértice não é promissor e deve ser terminada a busca por esse caminho ( o vértice é "terminado")
por exemplo no caso de uma otimização mínima de caminhos, se no meio do caminho eu vejo que o valor já é maior que o menor valor possível eu paro, pois não tem como o caminho atual ser o menor possível... (exemplo do livro)
????E se tiver caminhos negativos????
Além dessa forma de parar a busca, existem mais duas:
Se um nó não representa uma solução viável
"O subconjunto de soluções viáveis representado pelo nó consiste em um único ponto (e, portanto, nenhuma outra escolha pode ser feita) - neste caso, comparamos o valor da função objetivo para esta solução viável com aquele da melhor solução vista até agora e atualize o último com o anterior se a nova solução for melhor."
?????
E a geração dos nós de sua árvore?
Diferente da técnica anterior, ao invés de usarmos o depth-first, vamos usar o
best-first
, que consiste em gerar todos os filhos do nó mais promissor entre as folhas não terminadas (folhas não terminadas são chamadas de vivas)
Alguns problemas que podem ser resolvidos com essa técnica:
Problema de Atribuição
Problema da Mochila
Problema do Traveling Salesman
A eficiência vai depender de cada problema
Essa técnica tem dois itens que a técnica anterior não tinha:
Um limite com o melhor valor (pode ser o maior ou o menor dependendo do problema) possível que pode ser achado
O melhor valor parcial (vai sendo atualizado conforme valores melhores forem encontrados)