Strutture dati - Divide and Conquer
Nell'approccio divide et impera, il problema alla mano viene suddiviso in sotto-problemi più piccoli e quindi ogni problema viene risolto in modo indipendente. Quando continuiamo a dividere i sottoproblemi in sotto-problemi ancora più piccoli, potremmo eventualmente raggiungere uno stadio in cui non è più possibile alcuna divisione. Quei sottoproblemi "atomici" più piccoli possibili (frazioni) sono risolti. La soluzione di tutti i sottoproblemi viene infine fusa per ottenere la soluzione di un problema originale.
In generale, possiamo capire divide-and-conquer approccio in un processo in tre fasi.
Dividi / Spezza
Questo passaggio comporta la suddivisione del problema in sottoproblemi più piccoli. I sottoproblemi dovrebbero rappresentare una parte del problema originale. Questo passaggio generalmente richiede un approccio ricorsivo per dividere il problema fino a quando nessun sottoproblema è ulteriormente divisibile. In questa fase, i problemi secondari diventano di natura atomica ma rappresentano ancora una parte del problema reale.
Conquista / Risolvi
Questo passaggio riceve molti sottoproblemi minori da risolvere. Generalmente, a questo livello, i problemi sono considerati "risolti" da soli.
Unisci / Combina
Quando i sottoproblemi più piccoli vengono risolti, questa fase li combina ricorsivamente fino a formulare una soluzione del problema originale. Questo approccio algoritmico funziona in modo ricorsivo e i passaggi di conquista e unione funzionano così vicini da apparire come uno.
Esempi
I seguenti algoritmi informatici si basano su divide-and-conquer approccio di programmazione -
- Unisci ordinamento
- Ordinamento rapido
- Ricerca binaria
- La moltiplicazione della matrice di Strassen
- Coppia più vicina (punti)
Ci sono vari modi disponibili per risolvere qualsiasi problema con il computer, ma quelli menzionati sono un buon esempio di approccio divide et impera.