Ramificação e encadernação é uma heurística eficaz para problemas de pesquisa, e a Wikipedia lista vários problemas difíceis nos quais ramificações e encadernações foram usadas. No entanto, não consegui encontrar referências para sugerir que é mais do que apenas "um método" para resolver esses problemas.
Curiosamente, ouvi dizer que algumas das melhores heurísticas para SAT e programação inteira vêm de branch and bound, então minha pergunta é:
Alguém pode me indicar referências que detalhem usos eficazes de ramificações e vinculado a problemas difíceis de NP?
ds.algorithms
reference-request
optimization
heuristics
Suresh Venkat
fonte
fonte
Respostas:
Para o TSP, confira este livro ... http://www.tsp.gatech.edu/book/index.html
Meu entendimento é que não existe uma ferramenta para matá-los todos. Indiscutivelmente, qualquer solução recursiva que implante backtracking e alguma função de pontuação está usando branch e bound. Como tal, uma grande fração de solucionadores de problemas difíceis de NP usa alguma forma de ramificação e vinculação.
fonte
O Problema de Particionamento de Clique pode não ser o problema mais comum do NP, mas foi resolvido com eficiência usando o branch-and-bound, consulte este documento: http://joc.journal.informs.org/content/6/2/141 .abstrato
fonte
Algoritmos exponenciais exatos é um bom livro recente sobre tais algoritmos. Também é bom saber o algoritmo X para o problema exato da capa.
fonte