C++ Programmieraufgabe: Matching

Matching-Probleme treten dann auf, wenn zwischen zwei Gruppen eine Zuordnung hergestellt werden soll (jedem Bewerber soll eine Stelle vermittelt werden; jedem Gast soll ein Geschenk ĂŒberreicht werden). Dabei können unterschiedliche Nebenbedingungen hinzutreten (ein Bewerber ist nur fĂŒr bestimmte Stellen qualifiziert; nicht jedes Geschenk ist fĂŒr jeden Gast geeignet). Bei kleinen GruppengrĂ¶ĂŸen können diese Zuordnungen meist direkt gefunden werden; im Allgemeinen versucht man Algorithmen zu formulieren, die die Zuordnungen finden. Matching-Probleme werden in der Graphentheorie behandelt. Die hier vorgestellten Programmieraufgaben sollen einige typische Fragestellungen aufzeigen.
Noch keine Stimmen abgegeben
Noch keine Kommentare

Einordnung des Artikels

EinfĂŒhrung

Der Idealfall

Mit Matching werden Probleme bezeichnet, bei denen zu einer Gruppe B1, B2, ... , Bn (von n Personen, Objekten) passende GegenstĂŒcke (m Personen, Objekte) S1, S2, ... , Sm 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 Bi fĂŒr die Stelle Sj werde mit bij 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 B2 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 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 BewerbersAbbildung 2: 4 Bewertungen des zweiten Bewerbers

In Abbildung 2 sind sind die 4 Bewertungen b2,1, b2,2, b2,3, b2,4 eingezeichnet (beschriftet sind nur die erste und die letzte Bewertung), die Bewerber B2 fĂŒr die 4 Stellen S1, S2, S3, S4 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.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) = b1, j1 + b2, j2 + ... + bn, 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 sji, mit der der Anbieter der Stelle Sj den Bewerber Bi beurteilt (wieder auf der Skala von 0 bis 10), wobei natĂŒrlich bij nicht mit sji ĂŒ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) = b1, j1 + b2, j2 + ... + bn, jn + s1, j1 + s2, j2 + ... + sn, jn

zu maximieren.

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

In Abbildung 4 sind sind die 4 Bewertungen s3,1, s3,2, s3,3, s3,4 eingezeichnet (beschriftet sind nur die erste und die letzte Bewertung), die der Anbieter der Stelle S3 fĂŒr die 4 Bewerber B1, B2, B3, B4 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 (bij und sji stimmen ungefĂ€hr ĂŒberein). In diesem Fall sollte sich ein Matching mit wenigen Konflikten ergeben.
    • Mit deutlich unterschiedlichen Bewertungen: die bij weichen deutlich von den sji 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 np
    • zu en (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?