Please enable JavaScript.
Coggle requires JavaScript to display documents.
backtrakcing e brunch-and-bound - Coggle Diagram
backtrakcing e brunch-and-bound
design de algoritmos usados na resolução de grandes problemas combinatórios
ambos são construídos coomo uma àrvore de estados onde cada nó reflete a escolha feita para o componente de uma solução
as duas técnicas encerram o algoritmo assim que detecta que não é possível achar uma solução para o problema.
eles diferem na ordem que os nós da árvore de estados é gerado.
backtracking
pode ser aplicado para problemas de otimização ou não otimização.
árvore de espaço/estado é desenvolvida de maneira similar a uma DFS
pode ser usado para problemas de crescimento exponencial com o aumento do input(2^n).
se baseia em construir soluções, um componente por vez, e avaliar de forma parcial os candidatos
é cahamdo nó promissor o nó que construiu uma parte de uma solução e ainda pode chegar a uma solução válida. caso o nó não possa chegar a uma solução válida, é chamado de não promissor
a maioria dos algoritmos de backtracking tem uma saída que pode ser definida como uma n-upla [x1, ... , xn] onde cada coordenada xi é um elemento de
algum conjunto finito linearmente ordenado Si.
caso a tupla não seja uma solução válida, o algoritmo adiciona um novo elemento de Si + 1 que possa ser parte da resposta. caso não exista esse elemento, ela volta para xi e assim por diante.
branch-and-bound
usado para problemas de otimização
uma solução ótima é uma solução que tem o melhor valor da função e é viável
duas adições são feitas do backtracking para o branch-and-bound
uma maneira de fornecer, para cada nó da árvore, um limite de melhor valor da função para qualquer solução que possa ser obtida.
o valor da melhor solução encontrada até o momento.
é possível comparar o limite de um nó com a melhor solução encontrada até então. caso seja pior o limite do nó, esse nó não é promissor e pode ser terminado.
podemos acabar a busca em um nó por alguns motivos
o que comentamos antes, onde o limite é pior que o melhor caso até o momento
as restrições do problema serem violadas.
o subconjunto de soluções viáveis consiste em um único ponto