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.