Please enable JavaScript.
Coggle requires JavaScript to display documents.
Backtracking e branch-and-bound - Coggle Diagram
Backtracking e branch-and-bound
Técnicas utilizadas para desenvolvimento de algoritmos para resolução de problemas mais difíceis
Para ambas as técnicas, é gerada uma árvore solucionadora do problema, em que cada nó da árvore reflete escolhas específicas feitas para a solução de um componente do problema
Um nó é removido assim que o algoritmo percebe que é garantido que não é possível obter uma solução para o problema a partir das decisões tomadas até o momento
Branch and bound
Somente pra problemas de otimização
O problema da mochila
Dados n itens de pesos conhecidos e determinados valores, bem como uma mochila com uma determinada capacidade, encontrar o subconjunto de maior valor cuja capacidade é suportada pela mochila
Problema do caixeiro viajante
Dada uma lista de cidades e os pesos para realizar a travessia de uma cidade para outra, qual o caminho de menor peso que visita cada cidade exatamente uma vez e retorna para a cidade de origem?
Precisamos de funções para designar os limites (que podem ser superiores ou inferiores)
Se o problema for de maximização, temos que encontrar um limite superior
Se o problema for de minimização, temos que encontrar um limite inferior
Backtracking
Pode resolver problemas de otimização ou não
A cada etapa, o algoritmo avalia a solução construída parcialmente
Se uma solução parcial puder ser desenvolvida a partir do caminho atual sem violar as condições do problema, isto é feito
Se não, é feito um "backtrack". O algoritmo volta uma etapa e considera uma opção nova para tentar resolver o problema
Um nó é dito como promissor, se ele corresponde a um caminho parcialmente construído que pode ainda levar a uma solução para o problema
Caso ele não possa, ele será chamado de não-promissor
1 more item...
O problema das N rainhas
Consiste em posicionar n rainhas em um tabuleiro de xadrez N x N, de forma uma rainha não possa atacar a outra, de acordo com as regras do xadrez
O problema do ciclo Hamiltoniano
Percorrer todos os vértices de um grafo exatamente uma vez, e voltar para a origem
O problema do subconjunto soma
Dado um conjunto de inteiros positivos e um numero N, encontrar um subconjunto do conjunto dado cuja soma dos elementos é N