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.