Robert Sedgewick: Algorithmen

[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]


34. Paarung



Ein häufig auftretendes Problem ist die »Bildung von Paaren« von Objekten auf der Grundlage von Präferenzen, die gewöhnlich miteinander kollidieren. Zum Beispiel wurde in den USA ein sehr kompliziertes System entwickelt, wie graduierende Medizinstudenten auf Arbeitsplätze in Krankenhäusern zu verteilen sind. Jeder Student gibt eine Präferenzliste der Krankenhäuser an, und jedes Krankenhaus gibt eine Präferenzliste mehrerer Studenten an. Das Problem besteht darin, unter Beachtung aller angegebenen Präferenzen auf eine gerechte Weise Studenten zu Arbeitsplätzen zuzuordnen. Es wird ein komplizierter Algorithmus benötigt, da die besten Studenten gewöhnlich von mehreren Krankenhäusern bevorzugt werden, während die besten Positionen in Krankenhäusern sicher von mehreren Studenten bevorzugt werden. Es ist nicht einmal klar, ob jede Stelle in einem Krankenhaus mit einem Studenten besetzt werden kann, den das Krankenhaus angegeben hat, oder ob jedem Studenten eine der von ihm gewünschten Positionen vermittelt werden kann, ganz zu schweigen davon, ob die Reihenfolge in den Präferenzlisten eingehalten werden kann. Nachdem der Algorithmus sein Bestes geleistet hat, kommt es - um den Prozeß zu beenden - oft in letzter Minute noch zu einer Balgerei zwischen Studenten und Krankenhäusern um die nicht verteilten Stellen.

Dieses Beispiel ist ein Spezialfall eines komplizierten grundlegenden Problems bei Graphen, das gründlich untersucht worden ist. Für einen gegebenen Graph ist eine Paarung eine Teilmenge der Kanten, in der kein Knoten mehr als einmal erscheint. Das heißt, daß jeder Knoten, der von einer der Kanten der Paarung berührt wird, mit dem anderen Knoten dieser Kante zu einem Paar vereinigt wird, wobei jedoch einige Knoten ungepaart bleiben können. Selbst wenn wir darauf bestehen, daß eine Paarung so viele Knoten wie möglich einbeziehen soll, daß also keine der nicht in der Paarung enthaltenen Kanten ungepaarte Knoten verbinden soll, können verschiedene Arten der Auswahl der Kanten zu verschiedenen Anzahlen von übriggebliebenen (ungepaarten) Knoten führen.

Von besonderem Interesse ist eine maximale Paarung, welche so viele Kanten wie möglich enthält, oder, was dazu äquivalent ist, welche die Anzahl der ungepaarten Knoten minimiert. Als Optimum können wir eine Menge von Kanten erhalten, in der jeder Knoten genau einmal auftritt (eine solche Paarung in einem Graph mit 2V Knoten würde V Kanten enthalten), doch es ist nicht immer möglich, dies zu erreichen.

Abbildung 34.1 zeigt eine maximale Paarung (die schattierten Kanten) für den Graph aus unserem Beispiel. Bei 13 Knoten können wir nichts Besseres erreichen als eine Paarung mit sechs Kanten. Doch einfache Algorithmen für die Bestimmung von Paarungen hätten bereits bei diesem Beispiel Schwierigkeiten. Ein Verfahren, welches man ausprobieren könnte, wäre zum Beispiel, auswählbare Kanten für die Paarung in der Reihenfolge zu wählen, in der sie bei der Tiefensuche erscheinen (vgl. Abbildung 29.7). Für das Beispiel in Abbildung 34.1 würde dies die fünf Kanten AF EG HI JK LM ergeben, keine maximale Paarung. Auch läßt es sich, wie bereits erwähnt wurde, nicht einmal leicht sagen, wie viele Kanten für einen gegebenen Graph in einer maximalen Paarung enthalten sind. Wir bemerken zum Beispiel, daß keine aus drei Kanten bestehende Paarung für den Teilgraph existiert, der nur aus den sechs Knoten A bis F und den sie verbindenden Kanten besteht. Während es oft sehr leicht ist, bei einem großen Graph eine umfangreiche Paarung zu erhalten (zum Beispiel ist es nicht schwierig, eine maximale Paarung für den Graph für das »Labyrinth« aus Kapitel 29 zu finden), ist die Entwicklung eines Algorithmus zur Bestimmung der maximalen Paarung für einen beliebigen Graph tatsächlich eine komplizierte Aufgabe, wie Gegenbeispiele wie das obige verdeutlichen.

Abbildung 34.1
Abbildung 34.1 Eine maximale Paarung (schattierte Kanten).

Für das oben beschriebene Problem der Paarung mit den Medizinstudenten entsprechen die Studenten und Krankenhäuser Knoten im Graph; ihre Präferenzen entsprechen Kanten. Wenn sie ihren Präferenzen Werte zuordnen (vielleicht unter Benutzung der bewährten Skala »1-10«), so liegt das Problem der gewichteten Paarung vor: Für einen gegebenen gewichteten Graph ist eine Menge von Kanten zu finden, in der kein Knoten mehr als einmal erscheint, so daß die Summe der Kantengewichte in der gewählten Menge maximiert wird. Weiter unten werden wir eine andere Alternative kennenlernen, bei der wir die Reihenfolge der Präferenzen berücksichtigen, jedoch nicht fordern, daß ihnen (vielleicht willkürliche) Werte zugewiesen werden.

Dem Problem der Paarung ist aufgrund seiner intuitiven Natur und seiner vielfältigen Anwendungen von Mathematikern viel Aufmerksamkeit geschenkt worden. Seine Lösung erfordert im allgemeinen Fall komplizierte, doch wunderschöne Hilfsmittel aus der kombinatorischen Mathematik, deren Darlegung weit über den Rahmen dieses Buches hinausführen würde. Unsere Absicht ist es hier, dem Leser einen Eindruck von diesem Problem zu vermitteln, indem wir einige interessante Spezialfälle betrachten, wobei wir gleichzeitig einige nützliche Algorithmen entwickeln.


[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]