Please enable JavaScript.
Coggle requires JavaScript to display documents.
BackTracking, Branch and bound - Coggle Diagram
BackTracking
Características básicas
Para cada chamada recursiva existem diversas opções que podem ser seguidas. Ex.: Muitos vértices podem ser o próximo.
O algoritmo pode tentar uma chamada recursiva para cada um dos candidatos (solução para pesquisa exaustiva).
-
O que ele faz?
De maneira incremental, busca por candidatos à soluções e abandona cada candidato parcial C quando C não pode resultar em uma solução válida.
Quando sua busca chega a uma extremidade da estrutura de dados, como um nó terminal de uma árvore, o algoritmo realiza um retrocesso tipicamente implementado através de uma recursão.
n-queens
problem
The problem is to place n queens on an n × n chessboard so that no two queens attack each other by being in the same row or in the same column or on the same diagonal.
Backtracking é um algoritmo genérico que busca, por força bruta, soluções possíveis para problemas computacionais (tipicamente problemas de satisfações à restrições).
-
-
Branch and bound
o que ele faz
A branch-and-bound algorithm consists of a systematic enumeration of candidate solutions by means of state space search: the set of candidate solutions is thought of as forming a rooted tree with the full set at the root.
The algorithm explores branches of this tree, which represent subsets of the solution set.
Before enumerating the candidate solutions of a branch, the branch is checked against upper and lower estimated bounds on the optimal solution, and is discarded if it cannot produce a better solution than the best one found so far by the algorithm.
-
Branch and bound is an algorithm design paradigm for discrete and combinatorial optimization problems, as well as mathematical optimization.