C++ Programmieraufgabe: Matching

Einordnung des Artikels

• Einführung in die Informatik
  • C++ Programmieraufgaben
    • Matching

Einführung

Der Idealfall

Mit Matching werden Probleme bezeichnet, bei denen zu einer Gruppe B₁, B₂, ... , B_n (von n Personen, Objekten) passende Gegenstücke (m Personen, Objekte) S₁, S₂, ... , S_m gefunden werden sollen. Ein Beispiel dafür — und diese Nomenklatur wird im Folgenden verwendet — sind n Bewerber, denen m Stellen angeboten werden. Welche der Zahlen n oder m größer ist, soll nicht vorausgesetzt werden. Aber es soll jedem Bewerber höchstens eine Stelle angeboten werden (falls mehr Stellen als Bewerber vorhanden sind, werden einige Bewerber kein Angebot erhalten).

Zudem sollen die Bewerber die Möglichkeit haben, für die angebotenen Stellen eine Bewertung abzugeben; diese soll eine ganze Zahl von 0 bis 10 sein. Die Bewertung des Bewerbers B_i für die Stelle S_j werde mit b_ij bezeichnet.

Im einfachsten Fall gilt:

• es gibt gleich viele Bewerber wie Stellen (n = m).
• Jeder Bewerber bewertet genau eine Stelle mit einer Zahl ungleich null und alle anderen Stellen mit null.
• Jeder Bewerber hat einen anderen Favoriten.

In diesem Fall kann jedem Bewerber genau eine Stelle vorgeschlagen werden und jeder Bewerber ist zufrieden, weil seinem Wunsch entsprochen wurde. Eine derartige Situation mit 4 Bewerbern und 4 Stellen ist in Abbildung 1 dargestellt. Dadurch dass jeder Bewerber aber jede Stelle bewerten kann, sind Konflikte möglich; in Abbildung 2 sind etwa die 4 Bewertungen eingezeichnet, die Bewerber B₂ abgibt.

Abbildung 1: Idealfall für ein Matching: Die Anzahl der Bewerber stimmt mit der Anzahl der Stellen überein (hier n = m = 4). Und jeder Bewerber bevorzugt eine andere Stelle. Dazu ist nur die höchste von jedem Bewerber vergebene Bewertung eingezeichnet. In diesem Fall kann jedem Bewerber ein Angebot gemacht werden, das kein anderer Bewerber erhält.

Abbildung 2: 4 Bewertungen des zweiten Bewerbers

In Abbildung 2 sind sind die 4 Bewertungen b_2,1, b_2,2, b_2,3, b_2,4 eingezeichnet (beschriftet sind nur die erste und die letzte Bewertung), die Bewerber B₂ für die 4 Stellen S₁, S₂, S₃, S₄ abgibt.

Das Matching mit asymmetrischer Gesamtbewertung

Allerdings sind im Vergleich zum beschriebenen Idealfall sehr viel mehr Fälle denkbar, in denen nicht den Wünschen aller Bewerber entsprochen werden kann und man Kompromisse eingehen muss. Die einfachsten Fälle sind leicht vorstellbar:

• es gibt mehr Bewerber als Stellen
• mehrere Bewerber bevorzugen eine einzige Stelle.

Im allgemeinen Fall kann man folgendermaßen vorgehen:

Abbildung 3: Matching als Zuordnung: jedem Bewerber B wird eine Stelle S zugeordnet.

Man definiert zu einem Matching, also einer Zuordnung wie in Abbildung 3, eine Gesamtbewertung G (B), die sich aus der Summe der Einzelbewertungen der realisierten Zuordnungen zusammensetzt:

G(B) = b_{1, j1} + b_{2, j2} + ... + b_{n, jn}

und versucht die Gesamtbewertung G (B) zu maximieren.

Man beachte, dass nur für den Fall n < m die Gesamtbewertung G tatsächlich aus n Summanden besteht; für n > m sind es nur m Summanden (m -n Bewerbern kann man kein Angebot machen).

Besteht bei einem Matching nur für eine Gruppe (wie hier für die Bewerber) die Möglichkeit Bewertungen abzugeben, wird dies als Matching mit asymmetrischer Gesamtbewertung bezeichnet.

Das Matching mit symmetrischer Gesamtbewertung

Das Problem aus dem letzten Abschnitt kann leicht verallgemeinert werden: Ist es zusätzlich möglich, dass die Anbieter der Stellen eine Bewertung der Bewerber abgeben können, wird dies als Matching mit symmetrischer Gesamtbewertung bezeichnet.

Dann gibt es also Zahlen s_ji, mit der der Anbieter der Stelle S_j den Bewerber B_i beurteilt (wieder auf der Skala von 0 bis 10), wobei natürlich b_ij nicht mit s_ji übereinstimmen muss. Man beachte bei der Schreibweise die Reihenfolge der Indizes (der erste Index gibt immer an wer bewertet, der zweite Index was bewertet wird).

Um jetzt ein ideales Matching zu finden, wird man versuchen die Gesamtbewertung

G(B, S) = b_{1, j1} + b_{2, j2} + ... + b_{n, jn} + s_{1, j1} + s_{2, j2} + ... + s_{n, jn}

zu maximieren.

Abbildung 4: 4 Bewertungen, die der Anbieter der 3. Stelle für die 4 Bewerber abgibt.

In Abbildung 4 sind sind die 4 Bewertungen s_3,1, s_3,2, s_3,3, s_3,4 eingezeichnet (beschriftet sind nur die erste und die letzte Bewertung), die der Anbieter der Stelle S₃ für die 4 Bewerber B₁, B₂, B₃, B₄ abgibt.

Die Schreibweise G(B) soll andeuten, dass nur die Bewerber eine Bewertung abgeben, dagegen steht G(B, S) dafür, dass sowohl Bewerber als auch Anbieter von Stellen eine Bewertung abgeben. Denkbar ist dann auch die andere asymmetrische Bewertung G(S) zu untersuchen, bei der nur die Anbieter der Stellen die Bewertung abgeben. Aber um das aus der Sicht der Anbieter ideale Matching zu finden, geschieht nichts Neues: Die Vorgehensweise wird sich nicht davon unterscheiden, das ideale Matching für G(B) zu finden — man hat nur andere Zahlen für die Einzelbewertungen.

Mit diesen Schreibweisen kann man G(B, S) auch ausdrücken durch:

G(B, S) = G(B) + G(S).

Man darf aber nicht erwarten, dass im Allgemeinen G(B, S) maximal wird, wenn G(B) und zugleich G(S) maximal sind — für spezielle Einzelbewertungen kann dies richtig sein.

Mögliche Algorithmen zum Auffinden eines idealen Matchings

Für den Verwalter der Bewerber und Stellen, der die Stellen-Angebote an die Bewerber vergibt, wäre ein Algorithmus hilfreich, der das ideale Matching findet. Und zwar je nachdem, ob

• nur die Wünsche der Bewerber berücksichtigt werden sollen: Maximieren von G(B),
• ob nur die Wünsche der Anbieter der Stellen berücksichtigt werden sollen: Maximieren von G(S) oder
• ob die Wünsche beider gleichermaßen berücksichtigt werden sollen: Maximieren von G(B, S) = G(B) + G(S).

Naheliegend sind folgende Algorithmen:

1. brute force Algorithmus (brute force = rohe Gewalt): es werden alle möglichen Matchings durchgespielt und dann das ideale Matching ausgewählt.
2. greedy Algorithmus (greedy = gierig): Man sucht immer diejenige Zuordnung, die den größten Zuwachs in der Gesamtbewertung liefert und erhält damit ein Matching, das gute Aussichten hat, dem idealen Matching nahe zu kommen. Ist in einem Schritt keine eindeutige Auswahl möglich, wird eine Zuordnung zufällig ausgewählt.
3. greedy Algorithmus 2. Ordnung: Man sucht in jedem Schritt, nach den beiden Zuordnungen die den höchsten Zuwachs in der Gesamtbewertung liefern. Alle so entstehenden Matchings werden gebildet und am Ende das Matching mit der höchsten Gesamtbewertung ausgewählt.

Vorerst soll jedem Bewerber maximal ein Angebot gemacht werden:

• Für n > m bedeutet dies, dass einige Bewerber kein Angebot erhalten (nämlich n-m),
• für n < m erhält jeder Bewerber ein Angebot.

Die Programmieraufgaben

1. Erzeugen Sie geeignete Testdaten zum Testen der Algorithmen:
   • Mit unterschiedlichen Anzahlen:
     • n = m
     • n < m
     • n > m.
   • Mit nahezu gleichen Bewertungen; soll heißen; gibt ein Bewerber eine hohe Bewertung für eine Stelle ab, so gibt auch der Anbieter eine hohe Bewertung für den Bewerber ab (b_ij und s_ji stimmen ungefähr überein). In diesem Fall sollte sich ein Matching mit wenigen Konflikten ergeben.
   • Mit deutlich unterschiedlichen Bewertungen: die b_ij weichen deutlich von den s_ji ab.
2. Schreiben Sie die Algorithmen, die oben beschrieben wurden (brute force, greedy Algorithmus und greedy Algorithmus 2. Ordnung) zur Maximierung von G(B), G(S) und G(B, S).
3. Testen Sie Ihre Algorithmen mit den Testdaten.
4. Diskutieren Sie, wie gut die drei Algorithmen das ideale Matching finden.
5. Untersuchen Sie die Komplexität der Algorithmen: Versuchen Sie abzuschätzen, wie die Rechenzeit zunimmt, wenn n erhöht wird (für diese Untersuchung können Sie n = m wählen). Welche der Algorithmen besitzen eine Rechenzeit T(n), die proportional ist zu:
   • n
   • zu einer Potenz p von n, also n^p
   • zu eⁿ (exponentielle Abhängigkeit)?
6. Aus den bisherigen Ergebnissen lassen sich Verbesserungen für die Algorithmen ableiten: Versuchen Sie einen Algorithmus zu entwickeln, der nicht alle möglichen Kombinationen durchspielt, aber ein besseres Matching findet als die greedy Algorithmen.
7. Diskutieren Sie: Wie wird man die Gesamtbewertung G definieren, wenn einem Bewerber nicht höchstens eine sondern höchstens zwei, höchstens drei, ... Angebote gemacht werden? Wie lassen sich die Algorithmen auf diesen Fall anpassen?