Please enable JavaScript.
Coggle requires JavaScript to display documents.
Backtracking e Branch & bound - Coggle Diagram
Backtracking e Branch & bound
Baseadas na state-space tree
Nós refletem uma decisão específica para gerar uma parte da solução
Nó "promissor"- há uma solução parcial que pode eventualmente chegar a sua forma completa
Não promissor - um nó que não é promissor
Folha - nós promissores com a solução correta ou nós não promissores sem a solução
Branch & bound - otimização, enquanto que backtracking não envolve necessariamente esse aspecto
State-space tree é gerada de forma diferente. Em backtracking, geralmente como depth first
Backtracking
Construir soluções parte por parte, checando as soluções parcialmente feitas
Se não há solução viável no estado atual, o estado volta ao anterior e segue a opção que vem depois da que ele seguiu primeiramente
Ex2: problema das n rainhas (colocar n rainha no tabuleiro nxn, não deixando duas ou mais rainha na mesma coluna, linha ou diagonal)
Checar se há solução colocando a primeira rainha na primeira linha, depois a segunda rainha na terceira (primeira e segunda linha não podem para satisfazer a primeira decisão)... Se não tiver como avançar e a resposta não for encontrada, o algoritmo volta na decisão do posicionamento das rainhas até encontrar uma forma de gerar uma nova possível solução
Ex: subset sum - ordenar os elementos de um array e, na árvore de decisão, realizar uma bifurcação (uma para se a soma atual recebe o próximo menor elemento, outra se não recebe)
Tipicamente aplicado em problemas combinatórios que não possuem algoritmo eficiente, é capaz de resolver instâncias não triviais em um período de tempo razoável, e é uma técnica de resolução
Branch & Bound
Feasible solution - solução possível, optimal solution - melhor valor para uma solução possível (como o menor caminho em um circuito hamiltoniano) -->> problemas de otimização
Duas adições comparado ao Backtracking
Uma forma de providenciar o melhor valor da função em cada nó da árvore para cada solução que pode ser achada adicionando mais componentes na solução parcial do nó
O valor da melhor solução ao decorrer do algoritmo
Se o melhor resultado parcial de um nó é menos otimizado que a melhor solução encontrada, não é peciso checar os caminhos a partir desse nó (ou se a solução parcial dele não é satisfeita)
A cada iteração, todos os filhos dos nós mais promisssores são gerados (best first branch & bound)
Nó mais promissor - menor limite inferior, ou maior limite superior (depende do objetivo)
Depois da primeira solução gerada por esse método, ela é usada como um parâmetro quando for checar as próximas soluções possíveis
Possui alguns dos problemas do backtracking : não há como dizer quais instâncias vão ser resolvidas em um intervalo de tempo aceitável
Há várias formas de achar um limitante : gerando uma resposta inicial aleatória por exemplo, porém, a função do limitante não pode ser muito simples ou muito difícil de computar