Projeto e

Anotacoes

Projeto e Análise de Algoritmos Divisão e Conquista Camila Martins Saporetti (camila.saporetti@iprj.uerj.br) Introdução Motivação ● É preciso resolver um problema com uma entrada grande ● Para facilitar a resolução do problema, a entrada é quebrada em pedaços menores (DIVISÃO) ● Cada pedaço da entrada é então tratado separadamente (CONQUISTA) ● Ao final, os resultados parciais são combinados para gerar o resultado final procurado Divisão e Conquista ● Ideia geral: 1. Dividir a instância do problema em duas ou mais instâncias menores; 2. Resolver as instâncias menores (geralmente recursivamente); 3. Obter a solução para as instâncias originais (maiores) através da combinação destas soluções. Divisão e Conquista ● O paradigma de dividir e conquistar envolve 3 passos: A técnica de Divisão e Conquista ● Algoritmos baseados em divisão e conquista são, em geral, recursivos. ● A maioria dos algoritmos de divisão e conquista divide o problema em a subproblemas da mesma natureza, de tamanho n/b Quando Utilizar Divisão e Conquista? ● Existem três condições que indicam que a estratégia de divisão e conquista pode ser utilizada com sucesso: – Deve ser possível decompor uma instância em sub- in...