Divisão e conquista
Origem: Wikipédia, a enciclopédia livre.
Divisão e Conquista é uma Técnica de Projeto de Algoritmos. Seu nome em inglês é divide and conquer; em português se diz "dividir para reinar".
Esta técnica consiste em dividir sucessivamente o problema em problemas menores até que uma solução simples exista, de forma que a combinação simples destas soluções parciais forme a solução completa do problema. É o que se faz com todos os problemas complexos em geral. Como algoritmo, entretanto, cabe uma definição mais precisa. Dado um problema a ser resolvido para n entradas, o algoritmo divide as entradas em k grupos distintos, gerando k novos problemas. Freqüentemente estes problemas são do mesmo tipo (ou tamanho) que o original, e então se aplica recursivamente o método até que o tamanho dos sub-problemas seja tratável. A solução de cada grupo de k sub-problemas divididos é combinada adequadamente até se ter a solução do problema original.
Esquematicamente, pode-se pensar que os algoritmos deste tipo têm três passos básicos:
- Divisão: Dividir os dados em subsequências pequenas, até que sejam tratáveis;
- Conquista: Resolver o problema das subsequências tratáveis;
- Combinação: Agregação das subsequências tratadas até a solução do problema inicial.