Partitionierungsproblem

Das Partitionierungsproblem ist ein mathematisches Problem, das durch seine NP-Schwere eine große Bedeutung in der Informatik erlangt hat. Es beschäftigt sich damit, einen Algorithmus zu finden, mit dem für eine beliebige natürliche Zahl alle möglichen Darstellungen als Summe von natürlichen Zahlen (die Zahlpartitionen der Ausgangszahl) bestimmt werden können.

→ Die Anzahl der Darstellungen einer natürlichen Zahl $N$ als Summe von natürlichen Zahlen wird als Wert der Partitionsfunktion von $N,\,P(N)$ definiert. Formeln zur Berechnung der Partitionsfunktion und mathematische Anwendungen der Zahlpartitionen werden im Artikel Partitionsfunktion beschrieben. Der vorliegende Artikel beschreibt die Fragestellung als Problem der theoretischen Informatik und Komplexitätstheorie und Anwendungen der Zahlpartitionen auf Probleme in Informatik und Technik.

Erläuterung

Wie viele Möglichkeiten gibt es, eine natürliche Zahl als Summe von natürlichen Zahlen zu schreiben?

Die Lösung für die Zahl 4 ist simpel.

• 4 = 1+1+1+1
• 4 = 2+1+1
• 4 = 2+2
• 4 = 3+1
• 4 = 4

Für die Zerlegung der Zahl 6, angefangen bei der Zerlegung in lauter Einsen 1+1+1+1+1+1=6 über 2+2+2=6 bis 6=6, gibt es bereits genau 11 Möglichkeiten. Der indische Mathematiker S. Ramanujan kam sehr schnell auf eine Vielzahl von Varianten, als er eine Liste der Zerlegungen aller Zahlen bis 200 berechnete. Die Zahl 200 lässt sich in genau 3972999029388 Additionsvarianten aufspalten.

Anwendungen in Informatik und Technik

Die Bedeutung des Partitionierungsproblems liegt nur indirekt in der Partitionierung einer Zahl in kleinere Einheiten. Vielmehr lässt sich ein Problem durch die Umkehrung der Partitionierung beschreiben.

Einführendes Beispiel

Wenn eine Gruppe Kinder Mannschaften bilden will, um ein Spiel zu spielen, wird normalerweise gewählt. Dabei steht ein Pool von potentiellen Spielern am Spielfeldrand, und die Mannschaftsführer beider Mannschaften wählen abwechselnd so lange, bis jeder Teilnehmer einer Mannschaft zugeordnet wurde. Der Sinn dieses Rituals besteht darin, dass am Ende etwa gleich starke Mannschaften gegeneinander antreten.

Formal könnte man das Problem wie folgt spezifizieren:

• Es existiert eine Menge von Spielern.
• Die Spieler besitzen verschiedene Fähigkeiten. Diese könnte man verallgemeinernd als Spielstärke auf eine Skala von 1 bis 10 abbilden.
• Gesucht ist die Aufteilung in 2 Gruppen, bei der die Spielstärken der einzelnen Spieler addiert in beiden Gruppen gleich sind.

Auf das Partitionierungsproblem könnte man vorhergehende Beschreibung abbilden, indem die Spielstärken aller Spieler zum Wert $X$ addiert werden. Damit steht fest, dass Gruppe $A$ sowie Gruppe $B$ jeweils eine Spielstärke von ${\frac {X}{2}}$ erreichen müssen, damit das Spiel ausgeglichen ist.

Damit wird schnell deutlich, dass es einen einfachen Algorithmus gibt, sich einer Lösung des Problems anzunähern, indem abwechselnd der jeweils beste verbliebene Spieler gewählt wird. Ebenso ist ersichtlich, dass es unter Umständen keine perfekte Lösung des Problems gibt.

Inakzeptabel wird dies bei der Herausgabe von Wechselgeld an einem Fahrkartenautomaten. Oftmals ist jedoch auch eine näherungsweise Lösung des Problems hilfreich, um stark ungünstige Kombinationen auszuschließen.

Parallelverarbeitung in Computern

Ein wichtiger Bereich, in dem das Partitionierungsproblem zum Tragen kommt, ist die Verteilung von Rechenaufgaben in Multiprozessorsystemen. Das Problem besteht darin, bei $n$ zur Verfügung stehenden CPUs oder Rechenkernen genau $n$ Mengen von Rechenaufgaben mit gleicher Laufzeit zu bestimmen.

Allgemein: Graphpartitionierung

→ Hauptartikel: Graphpartitionierung

Um in einem rechenintensiven Computerprogramm die Vorteile eines parallelen Systems optimal ausnutzen zu können, muss dieses zwei Kriterien erfüllen:

• Die Rechenlast muss gleichmäßig auf die Recheneinheiten verteilt werden.
• Die zur Abarbeitung des Programms nötige Kommunikation zwischen den Recheneinheiten soll möglichst klein gehalten werden, da diese immense Ausführungszeit beansprucht.

Parallele Suchalgorithmen

Ein klassisches Problem für Künstliche Intelligenz ist die effiziente Abarbeitung von Suchbäumen. Zu den damit gegebenen Aufgabenstellungen gehören u. a. die Suche nach kürzesten Wegen, die Lösung des Constraint-Satisfaction-Problem oder die hier betrachtete Lösung der diskreten Optimierung. Für die Optimierung wird oft das aus dem Operations Research bekannte Baumsuchverfahren „Branch-and-Bound“ verwendet. In der Künstlichen Intelligenz ist es unter dem Namen A*-Algorithmus bekannt.

Typischerweise sind die diskreten Optimierungsprobleme, wie z. B. das Problem des Handlungsreisenden, das Rucksackproblem oder die Maschinenbelegungsplanung, von hoher Komplexität und somit durch lange Berechnungszeiten gekennzeichnet. Da die technische Entwicklung sequentieller Rechner zunehmend an physikalische Grenzen stößt, ist die Verwendung massiver Rechenparallelität eine vielversprechende Alternative. Bei Parallelrechnern muss aber eine ausgeglichene Beschäftigung der Prozessoren zur Aufrechterhaltung der Effizienz gewährleistet sein. Gerade für feinkörnige Parallelrechner mit mehreren 10.000 Prozessorelementen stellt die dazu erforderliche Lastverteilung der anstehenden Rechenarbeit auf die Prozessoren ein zentrales Problem dar.

Partitionierung in Datenbanken

Neben dem transparenten Betrieb einer logischen Datenbank auf mehrere Rechnerknoten findet vor allem in Bereich des Data-Warehouse zusätzlich eine Partitionierung des Datenbestandes statt. Logisch zusammenhängende Daten einer Tabelle werden dabei in Gruppen sortiert und horizontal fragmentiert. Dies ist vorteilhaft zur Abarbeitung von Suchanfragen, da aus der Anfrage meist direkt ersichtlich ist, welche Teilpartitionen zur Anfragebearbeitung herangezogen werden müssen. Andere Teile der logischen Tabelle werden dann nicht mehr durchsucht. Erweitert werden kann das Konzept durch vertikale Fragmentierung, bei der über die Spalten einer Tabelle gruppiert und fragmentiert wird, sowie Verteilung der einzelnen Fragmente auf verschiedene Rechnerknoten.

Suboptimale Fragmentierung kann zu mäßigem Performancegewinn führen. Optimal zur effizienten Netzplanung ist die Aufteilung der Datensätze mit der höchsten Anfragefrequenz in kleinere Partitionen. Zu Zwecken der Archivierung kann auch die Partitionierung in aktive und passive Daten sinnvoll eingesetzt werden.

Beispiel: Tabelle Aufträge

• Partition 1: Jahre 2000–2005
• Partition 2: Jahre 2005–2007
• Partition 3: Jahr 2008

Anwendung in Netzwerken

Das Prinzip der Lastverteilung ist in vielen Bereichen essentiell, beispielsweise für den Betrieb großer Datenbanken, Serveranwendungen oder den Betrieb und die Planung von Netzwerkinfrastruktur.

DNS Namensauflösung

→ Hauptartikel: Lastverteilung per DNS

Bereits mittelgroße Websites verursachen oft zu viele Anfragen, als dass sie von einem Computersystem beantwortet werden könnten. Es hat sich herausgestellt, das die dynamische Auflösung von Domainnamen zu wechselnden IP-Adressen ein wirkungsvolles Verfahren zur Umleitung der Nutzeranfragen an verschiedene, aber in ihrer Funktion gleichartige Computersysteme darstellt.

Das Konzept des Round Robin DNS hat sich als günstige Lösung herausgestellt. Es verbindet einen geringen administrativen Aufwand mit ausreichend Nutzen. Dieser kann aufgrund des geschickten Einsatzes von IPs auch im Falle eines Ausfalls ohne Probleme weiterarbeiten, ohne am DNS-System an sich Eingriffe vornehmen zu müssen. Das Round Robin wird beispielsweise über den Namen www.bildungsmarkt-sachsen.de angesetzt und dieser wird auf die IPs abgebildet, die den Namen bms1.hrz.tu-chemnitz.de und bms2.hrz.tu-chemnitz.de zugeordnet sind.

Planung von Funknetzen

Zum Betrieb eines Drahtlosnetzwerkes ist es wichtig, die erreichte Granularität der Netzabdeckung mit den entstehenden Kosten abzuwägen.

Das Problem besteht formal darin, eine Partitionierung für ein Gebiet $A$ zu finden, so dass die entstehenden Regionen mit der Menge zur Verfügung stehender Sensoren die höchste bzw. mit so wenig Sensoren wie möglich die gewünschte Granularität aufweisen.

Für eine optimale Entscheidung sind verschiedene Parameter zu berücksichtigen. Diese werden durch eine lineare Gewichtungsfunktion zu einem (variablen) Wert addiert werden über den die Partitionierung erfolgt.

Es ist ebenso möglich, dass einige Regionen des Netzes wichtiger als andere sind und daher mit mehr Sensoren ausgestattet werden müssen (sog. hot spots). Werden mehr Sensoren aufgestellt als benötigt werden, kommt es seltener zu Engpässen und zu einer höheren Ausfalltoleranz bei Fehlfunktionen einzelner Sensoren. Zudem gewinnt Energieeffizienz zunehmend an Bedeutung. Netze können durch geschickte Optimierung in Zeiten geringer Auslastung einzelne Sensoren abschalten, wenn ihr Abdeckungsbereich derart überlappt, dass er durch benachbarte Sensoren mitversorgt wird.

Verwandte Probleme

Flaschenhals-Graph-Partitionierungsproblem

Das Flaschenhals-Graph-Partitionierungsproblem besteht in der Verteilung der Eckpunkte eines ungerichtet Kanten-gewichteten Graphen in zwei gleich große Mengen, so dass das größte Kantengewicht (maximum) in den Teilmengen minimal wird. Im Gegensatz zum Graph-Partitionierungsproblem (Graphpartitionierung), bei dem die Summe der Gewichte in den Teilmengen minimiert wird, ist die Flaschenhals-Version kein NP-schweres Problem, sondern lässt sich in polynomialer Zeit lösen.