Algoritmos Paralelos Probabilísticos para Busca em "Backtrack" e
Heurística "Branch-and-Bound"

Problemas de  busca combinatória são  problemas em que se  procura uma
certa combinação  de objetos entre  um grande conjunto  de combinações
possíveis.   Os  métodos   usualmente  empregados  na  solução  desses
problemas    são    a    busca    em    "backtrack"    e    heurística
"branch-and-bound". Exemplos típios de problemas de busca combinatória
são o 3-SAT e o  Problema do Caixeiro Viajante, entre outros problemas
NP. A  utilização de  Computação Paralela na  solução de  problemas de
busca  combinatória  pode  trazer  ganhos enormes,  aproximando-se  do
"speedup" ótimo.

Neste seminário apresentaremos  o trabalho de Karp e  Zhang sobre esse
assunto,   trazendo   métodos   probabilísticos   genéricos   para   a
paralelização de  algoritmos de busca  sequencial em "backtrack"  e de
heurísticas   "branch-and-bound".   As  vantagens   introduzidas  pela
randomização nos  métodos serão apresentadas,  bem como os  limites de
tempo de execução teóricos apresentados no artigo.