Please enable JavaScript.
Coggle requires JavaScript to display documents.
MM11 - Coggle Diagram
MM11
Branch-and-Bound
Abordagem
Branch-and-Bound é usado para resolver problemas de otimização. Quando percebe que já tem uma solução ótima melhor que aquela para a qual o pré-processamento leva, abandona esse caminho. Ele percorre a árvore de estados de forma seletiva para obter a melhor solução.
Percurso
Branch-and-Bound percorre a árvore de qualquer maneira, DFS ou BFS.
-
-
Busca
Em Branch-and-Bound, como a solução ótima pode estar em qualquer lugar da árvore de estados, a árvore precisa ser explorada completamente.
-
-
-
-
-
-
-
Backtracking
Abordagem
Backtracking é usado para encontrar todas as soluções possíveis disponíveis para um problema. Quando percebe que fez uma escolha ruim, desfaz a última escolha retrocedendo. Ele percorre a árvore de estados até encontrar uma solução para o problema.
-
-
-
Busca
No backtracking, a árvore de estados é percorrida até que a solução seja obtida.
-
Capacidade de Solução
Backtracking pode resolver praticamente qualquer problema (xadrez, sudoku etc.).
Finalidade
Tipicamente, backtracking é usado para resolver problemas de decisão.
-
-
Solução
Ao encontrar com sucesso uma solução na árvore de estados, a busca é interrompida.
-