Please enable JavaScript.
Coggle requires JavaScript to display documents.
Lidando com as limitações dos algoritmos - Coggle Diagram
Lidando com as limitações dos algoritmos
Backtracking
Constrói soluções um componente por vez e os avalia.
A avaliação é feita da seguinte forma: se a solução parcialmente construida pode ser desenvolvida ainda mais sem violar as restrições do problema, isso é feito pegando a primeira opção legítima restante para o próximo componente. Se não houver opção legítima, o algoritmo retrocede para substituir o último componente da solução parcialmente construída por sua próxima opção.
É mais conveniente implementar esse tipo de processo construindo uma árvore de escolhas chamada de árvore de estado espaço.
Ela é chamada de promissora se corresponde a uma solução parcialmente construida que pode levar a uma solução completa, caso contrário é chamada de não promissora.
De uma forma mais geral, a maioria dos algoritmos de backtracking funciona da seguinte forma:
A saída de um algoritmo de backtraking pode ser pensada como uma n-tupla onde cada coordenada Xi é um elemento de uma lista finita ordenada Si.
Dependendo do problema as listas podem ter o mesmo tamanho ou não.
Um algoritmo de backtracking gera, explicita ou implicitamente, uma árvore de estado-espaço. Seus nós representam tuplas parcialmente completas com a primeira coordenada i definida como a primeira das ações do algoritmo
Esse algoritmo é pouco eficiente mas consegue resolver alguns dos problemas que existem hoje e necessitam de ser resolvidos.
Existem algumas maneiras de se otimizar o tamanho da árvore de estado-espaço a depender do que está sendo procurado.
Problema das N rainhas
Problema do Circuito hamiltoniano
Problema da soma de subconjuntos
Branck-and-bound
Comparado com o backtracking, ramificar e ligar apresenta dois itens adicionais
Uma forma de fornecer , para cada nó de uma árvore de estado-espaço, um limite sobre o melhor valor da função objetivo em qualquer solução que pode ser obtida adicionando outros componentes à solução parcialmente construída representada pelo nó.
O valor da melhor solução vista até agora
Se essas informações estiverem disponíveis, podemos comparar o valor limite de um nó com o valor da melhor solução vista até agora. Se o valor limite não for melhor do que o valor visto até agora o nó não é promissor e pode ser encerrado.
De forma geral, encerramos um caminho de pesquisa no nó atual em uma árvore de espaço estado de um algoritmo de branch-and-bound por uma das três razões a seguir:
O nó não representar uma solução viável para o problema por violar algum dos limites do problema.
O valor limite do nó não ser melhor do que o valor da melhor solução encontrada até agora.
O subconjunto de solução viável representado pelo nó consiste em um único ponto, neste caso comparamos o valor da função objetivo para a solução viável com o da melhor solução vista até agora e atualizamos o último caso a anterior seja melhor.
Problema de atribuição
Problema da mochila
Problema do caixeiro viajante