In approccio divide et impera, il problema in questione viene diviso in sottoproblemi più piccoli e poi ogni problema viene risolto indipendentemente. Quando continuiamo a dividere i sottoproblemi in sottoproblemi ancora più piccoli, possiamo alla fine raggiungere uno stadio in cui non è più possibile alcuna divisione. Questi sottoproblemi “atomici” più piccoli possibili (frazioni) vengono risolti. La soluzione di tutti i sotto-problemi viene infine fusa per ottenere la soluzione di un problema originale.
In generale, possiamo comprendere l’approccio divide et impera in un processo in tre fasi.
Dividere/rompere
Questa fase comporta la rottura del problema in sotto-problemi più piccoli. I sottoproblemi dovrebbero rappresentare una parte del problema originale. Questo passo generalmente prende un approccio ricorsivo per dividere il problema finché nessun sottoproblema è ulteriormente divisibile. A questo stadio, i sotto-problemi diventano di natura atomica ma rappresentano ancora una parte del problema reale.
Conquista/Solve
Questo passo riceve molti sotto-problemi più piccoli da risolvere. Generalmente, a questo livello, i problemi sono considerati ‘risolti’ da soli.
Merge/Combine
Quando i sottoproblemi più piccoli sono risolti, questa fase li combina ricorsivamente fino a formulare una soluzione del problema originale. Questo approccio algoritmico funziona ricorsivamente e conquistare & le fasi di fusione funziona così vicino che appaiono come uno solo.
Esempi
I seguenti algoritmi informatici sono basati sull’approccio di programmazione divide et imperaconquer programming approach –
- Merge Sort
- Quick Sort
- Binary Search
- Strassen’s Matrix Multiplication
- Closest pair (points)
Ci sono vari modi disponibili per risolvere qualsiasi problema informatico, ma quelli menzionati sono un buon esempio di approccio divide et impera.