Please enable JavaScript.
Coggle requires JavaScript to display documents.
Backtracking, Branch-and-bound - Coggle Diagram
Backtracking
A principal ideia é construir soluções um componente por vez e avaliar parcialmente os candidatos construídos das formas que seguem
Se a solução parcialmente construída pode ser desenvolvida sem que nenhuma das restrições do problema sejam violadas, então é feita pela primeira opção válida para o próximo componente, caso contrário, nenhuma alternativa para nenhum componente restante precisa ser considerado, nesse caso o algoritmo volta para substituir o último componente da solução parcialmente construída com a próxima opção
-
-
Os nós do primeiro nível representam as escolhas feitas para o primeiro componente da solução, os do segundo nível as escolhas do segundo componente e continua assim até o fim
Um nó dito promissor (promising) corresponde a uma solução parcialmente construída que ainda pode levar a uma solução completa, caso contrário é não promissor (nonpromising)
Folhas podem representar o fim de soluções não promissoras ou soluções completas encontradas pelo algoritmo
-
-
-
Geralmente é utilizado em problemas combinatórios difíceis onde não existem algoritmos eficientes que encontrem as exatas soluções possíveis
Branch-and-bound
-
- Uma maneira de fornecer, para cada nó de uma árvore state-space, um limite no melhor valor da função objetivo em qualquer solução que pode ser obtida adicionando outros componentes para a solução parcialmente construída representada pelo nó
- O valor da melhor solução descoberta até o momento
- Com as informações presentes pode-se comparar o nó de valor limite com o valor da melhor solução até então
-
- O valor do nó limite não é melhor que a melhor solução até agora
- O nó não apresenta uma solução factível
- O subconjunto de soluções factíveis representada pelo nó consiste em um único ponto
Uma solução factível é um ponto onde o problema de busca em espaço onde todas as solução são resolvidas sem violar nenhuma das restrições do problema, enquanto uma solução ótima é uma solução factível com o melhor valor para a função que é o objetivo
-
-
-