Estruturas de dados - dividir e conquistar
Na abordagem dividir para conquistar, o problema em questão é dividido em subproblemas menores e, em seguida, cada problema é resolvido de forma independente. Quando continuamos dividindo os subproblemas em subproblemas ainda menores, podemos eventualmente atingir um estágio em que nenhuma divisão é possível. Esses menores subproblemas "atômicos" possíveis (frações) são resolvidos. A solução de todos os subproblemas é finalmente combinada para obter a solução de um problema original.
Em termos gerais, podemos entender divide-and-conquer abordagem em um processo de três etapas.
Divide / Break
Esta etapa envolve dividir o problema em subproblemas menores. Os subproblemas devem representar uma parte do problema original. Essa etapa geralmente usa uma abordagem recursiva para dividir o problema até que nenhum subproblema seja mais divisível. Nesse estágio, os subproblemas tornam-se atômicos por natureza, mas ainda representam uma parte do problema real.
Conquistar / Resolver
Esta etapa recebe muitos subproblemas menores a serem resolvidos. Geralmente, neste nível, os problemas são considerados 'resolvidos' por conta própria.
Unir / Combinar
Quando os subproblemas menores são resolvidos, esse estágio os combina recursivamente até que formem uma solução para o problema original. Esta abordagem algorítmica funciona recursivamente e as etapas de conquista e mesclagem funcionam tão próximas que aparecem como uma só.
Exemplos
Os seguintes algoritmos de computador são baseados em divide-and-conquer abordagem de programação -
- Mesclar Classificar
- Ordenação rápida
- Pesquisa Binária
- Multiplicação da matriz de Strassen
- Par mais próximo (pontos)
Existem várias maneiras de resolver qualquer problema de computador, mas as mencionadas são um bom exemplo de abordagem de dividir para conquistar.