Na abordagem dividir e conquistar, o problema em questão, é dividido em sub-problemas mais pequenos e depois cada problema é resolvido independentemente. Quando continuamos a dividir os sub-problemas em sub-problemas ainda mais pequenos, podemos eventualmente chegar a uma fase em que não seja possível mais nenhuma divisão. Esses sub-problemas (fracções) “atómicos” mais pequenos possíveis são resolvidos. A solução de todos os sub-problemas é finalmente fundida para obter a solução de um problema original.
p>Broadly, podemos compreender a abordagem dividir e conquistar num processo de três etapas.
Divide/Break
Esta etapa envolve a divisão do problema em sub-problemas mais pequenos. Os sub-problemas devem representar uma parte do problema original. Esta etapa geralmente adopta uma abordagem recorrente para dividir o problema até que nenhum sub-problema seja mais divisível. Nesta fase, os sub-problemas tornam-se atómicos por natureza, mas ainda representam alguma parte do problema real.
Conquista/Solução
Esta etapa recebe muitos sub-problemas mais pequenos para serem resolvidos. Geralmente, a este nível, os problemas são considerados ‘resolvidos’ por si mesmos.
Merge/Combine
Quando os sub-problemas mais pequenos são resolvidos, esta etapa combina-os recursivamente até que formulem uma solução para o problema original. Esta abordagem algorítmica funciona recursivamente e conquista & fundir etapas funciona tão perto que aparecem como uma só.
Exemplos
Os seguintes algoritmos informáticos são baseados em dividir-e-Conquer Programming Approach –
- Merge Sort
- Quick Sort
- Binary Search
- Strassen’s Matrix Multiplication
- Closest Par (pontos)
Existem várias maneiras disponíveis para resolver qualquer problema informático, mas os mencionados são um bom exemplo de abordagem de dividir e conquistar.