Ramificar e limitar
Aspeto
(Redirecionado de Branch and bound)
Este artigo não cita fontes confiáveis. (Junho de 2011) |
![](http://upload.wikimedia.org/wikipedia/commons/thumb/2/20/Branch%26bound.jpg/220px-Branch%26bound.jpg)
O método de Ramificar e limitar (em inglês, Branch and bound) é um algoritmo para encontrar soluções ótimas para vários problemas de otimização, especialmente em otimização combinatória. Consiste em uma enumeração sistemática de todos os candidatos a solução, através da qual grandes subconjuntos de candidatos infrutíferos são descartados em massa utilizando os limites superior e inferior da quantia otimizada.
O método foi proposto por A. H. Land e A. G. Doig em 1960 para programação discreta. É utilizado para vários problemas NP-completos como o problema do caixeiro viajante e o problema da mochila.