In de verdeel-en-heers aanpak, wordt het probleem opgedeeld in kleinere sub-problemen en wordt elk probleem onafhankelijk opgelost. Als we de deelproblemen blijven verdelen in nog kleinere deelproblemen, kunnen we uiteindelijk een stadium bereiken waarin geen verdeling meer mogelijk is. Die “atomaire” kleinst mogelijke deelproblemen (breuken) worden opgelost. De oplossing van alle deelproblemen wordt uiteindelijk samengevoegd om de oplossing van een oorspronkelijk probleem te verkrijgen.
In grote lijnen kunnen we de verdeel-en-over-benadering begrijpen in een proces van drie stappen.
Verdelen/Breken
Bij deze stap wordt het probleem in kleinere deelproblemen verdeeld. De deelproblemen moeten een deel van het oorspronkelijke probleem vertegenwoordigen. In deze stap wordt het probleem meestal recursief verdeeld totdat geen enkel deelprobleem meer deelbaar is. In dit stadium worden de sub-problemen atomair van aard, maar vertegenwoordigen nog steeds een deel van het eigenlijke probleem.
Veroveren/Oplossen
Deze stap ontvangt een heleboel kleinere sub-problemen die moeten worden opgelost. Over het algemeen worden de problemen op dit niveau als op zichzelf ‘opgelost’ beschouwd.
Samenvoegen/Combineren
Wanneer de kleinere deelproblemen zijn opgelost, worden ze in deze stap recursief gecombineerd tot ze een oplossing van het oorspronkelijke probleem vormen. Deze algoritmische aanpak werkt recursief en & samenvoegen stappen zo dicht bij elkaar dat ze als één lijken.
Voorbeelden
De volgende computeralgoritmen zijn gebaseerd op verdeel-en-veroveren programmeerbenadering –
- Merge Sort
- Quick Sort
- Binary Search
- Strassen’s Matrix Multiplication
- Closest pair (punten)
Er zijn verschillende manieren beschikbaar om elk computerprobleem op te lossen, maar de genoemde zijn een goed voorbeeld van verdeel-en-heers-benadering.