Divide et impera

von Alexander Kirk
Letzte Änderung am Sonntag, 25. Februar 2007, 12:13 (v1)

Strategie in Algorithmen zur Lösung von Problemen durch Zerlegung in Teilprobleme.

Bücher zum Thema bei Amazon.de

Divide and Conquer (zu deutsch "teile und herrsche", lat. divide et impera; angeblich ein Ausspruch des französischen Königs Ludwigs XI., soll aber sogar auf Julius Caesar zurückgehen), bezeichnet eine Strategie in Algorithmen, bei der das Gesamt-Problem in (kleinere) Teilprobleme zerlegt wird. Dies kann verschiedene Vorteile haben:

• Das Teilproblem kann leichter (und damit schneller) lösbar sein.
  
  
• Die Teilprobleme können parallelisiert werden, dh. auf mehreren Computern gleichzeitig berechnet werden.
  
  

Die Gesamtlösung kann in verschiedenen Weisen von den Teilproblemen abhängig sein (je nach Algorithmus):

• Die Lösungen der Teilprobleme werden zu einer Gesamtlösung zusammengefügt. Zum Beispiel wird beim Sortieren mit Quicksort die sortierte Ergebnisliste aus kleinen, jeweils für sich sortierten Teillisten zusammengesetzt.
  
  
• Die Lösung für das letzte Teilproblem ist gleichzeitig Lösung des Gesamtproblems. Zum Beispiel beim Suchen im Binärbaum wird nach dem letzten Suchschritt die passende Stelle im Baum bestimmt.
  
  
• Die Lösungen der Teilprobleme sind alle für sich eine Lösung, wobei dann das beste Ergebnis als Gesamtlösung ausgesucht wird. Zum Beispiel bei Algorithmen zur Optimierung wird mit verschiedenen Strategien eine Lösung berechnet und dann das beste Ergebnis verwendet.
  
  

Divide and Conquer Algorithmen werden meist rekursiv imlementiert. Allerdings sind auch nicht-rekursive Lösungen möglich, wenn die Zwischenergebnisse in geeigneten Datenstrukturen (z.B. Stack) gespeichert werden.

Oft werden auch für (auf andere Art) einfach lösbare Probleme Divide and Conquer Implementierungen verwendet, um im spezielen die Vorteile der Parallelisierung auszunützen.