Please enable JavaScript.
Coggle requires JavaScript to display documents.
Lidando com limitações algorítmicas, Backtracking, Branch-and-Bound -…
-
Backtracking
-
O que é?
Backtracking é um aprimoramento do algoritmo de busca
por força bruta, de forma que, grande parte das soluções são eliminadas sem serem explicitamente examinadas.
Utilizado em:
-
Problemas que podem ser esquematizados em uma árvore, tendo a representação de todas as possíveis decisões
-
-
-
Branch-and-Bound
O que é?
É um algoritmo para encontrar soluções para problemas de otimização, especialmente em otimização combinatória, onde há uma dificuldade para o backtraking
-
Além do requerido pelo backtranking, necessita da observação de mais alguns pontos, são eles:
Uma maneira de fornecer, para cada nó de uma árvore de espaço de estado, um limite no melhor valor da função1 em qualquer solução que possa vir a ser obtida adicionando outros componentes para a solução parcialmente construída e representada pelo no, o valor da melhor solução vista.
Sendo assim:
Se esta informação estiver disponível, podemos comparar o valor de limite de um nó com o valor da melhor solução vista até agora. Se o valor limite não for melhor que o valor da melhor solução vista até agora, ou seja, não menor para um problema de minimização e não maior para um problema de maximização - o nó não é promissor e pode ser encerrado.
-
-
-
