Matching-Algorithmen erklärt
Matching fragt, wie sich zwei Seiten (oder eine einzelne Gruppe) einander zuordnen lassen: Fahrzeuge und Aufträge, Bewerber und Kliniken, Beschäftigte und Parkplätze, Patienten und Spenderorgane. Das durchgehende Beispiel der ersten neun Stücke ist ein Dispatcher mit Fahrzeugen und Aufträgen auf einer Karte; die letzten vier Stücke wechseln zu Präferenz- und Marktdesign-Beispielen, die Alvin Roths Arbeiten zu Marktdesign ohne Geld folgen (Wohngemeinschaft, Klinik-Zulassung, Dauerparkplatz-Tausch, Nierenspende).
Der Graph zerfällt in drei Äste: Kosten (Greedy → Verbesserungswege → Hopcroft–Karp/Ungarische Methode/Blossom → Gewichteter Blossom als Konvergenz von Ungarisch und Blossom), Präferenzen (Gale–Shapley und seine vier Erweiterungen um Stabile Mitbewohner, Krankenhaus-Zulassung, Top Trading Cycles und Nierentausch) und Online (Entscheidungen ohne Blick in die Zukunft). Jedes Stück misst seine eigene, oft überraschende Grenze, statt sie nur zu behaupten.
In short: Covers matching algorithms: greedy matching, the Hungarian method, blossom algorithm, stable matching (Gale-Shapley) and kidney exchange. Interactive demos range from bipartite assignment to preference-based market design, each with a measured limit.
Diese Seite gehört zu Algorithmen und Verfahren erklärt. So lesen Sie sie: Das Diagramm zeigt, wie die Stücke zusammenhängen. Jede Kachel darunter öffnet eine interaktive Demo, wo es eine gibt, mit einer Erklärseite für Einsteiger und Fachleute. Auf der Suche nach einer Lösung für ein konkretes Problem? Zu den Interaktiven Demos.
Hinweis: Alle Demos rechnen mit synthetischen oder frei verfügbaren Beispieldaten und laufen auf einem externen Anbieter (Datenschutz). Bitte geben Sie darin keine vertraulichen oder personenbezogenen Daten ein. Die Ergebnisse gelten für die jeweilige Demo-Instanz und lassen sich nicht ungeprüft auf reale Fälle übertragen; für darauf gestützte Entscheidungen übernehme ich keine Gewähr.
Zuletzt aktualisiert:
Welches Verfahren passt zu Ihrem Fall? Zum Entscheidungsbaum ↓
Zum Nachlesen: erst einfach, dann fachlich
Greedy-Matching verständlich erklärt
Warum die Regel „billigste Kante zuerst“ Fahrzeuge und Aufträge schlechter zuordnet als nötig, weil sie nie etwas zurücknimmt: erst für Einsteiger ohne Formeln, dann für Fachleute mit Modell, Formeln und Messwerten.
Die 13 Stücke im Überblick
Von der Wurzel (Greedy-Matching) führt ein Kostenast über die Verbesserungswege zu Hopcroft–Karp (mehr Paare), der Ungarischen Methode (auch die Kosten) und Blossom (allgemeine Graphen statt zwei Seiten); die Ungarische Methode und Blossom fließen in Gewichteter Blossom zusammen (Doppelrahmen). Zwei gestrichelte Gegenstück-Kanten führen von der Wurzel weg: zu Gale–Shapley (Vorlieben statt Kosten) und zu Online-Matching (nichts ist vorab bekannt).
Gale–Shapley verzweigt in drei Erweiterungen: Stabile Mitbewohner (eine Gruppe statt zwei Seiten), Krankenhaus-Zulassung (mehrere Plätze je Klinik) und, als Gegenstück-Kante, Top Trading Cycles (jeder besitzt schon etwas, statt nur zu präferieren). Top Trading Cycles führt weiter zu Nierentausch, das dieselbe Kreissuche auf kurze, medizinisch zulässige Zyklen und Ketten einschränkt.
Die Kästen sind klickbar und öffnen die jeweilige Demo direkt.
- behebt eine Schwäche des Vorgängers oder baut darauf auf
- Gegenstück: derselbe Zweck, andere Bauweise (kein Fix)
- Zusammenfluss mehrerer Stränge
Gestrichelte Doppelpfeile sind Gegenstücke (derselbe Zweck, andere Bauweise), kein Fix: Gale–Shapley und Online-Matching lösen dasselbe Zuordnungsproblem wie die Wurzel, aber mit einer anderen Grundannahme; Top Trading Cycles bricht mit der Vorschlags-Logik von Gale–Shapley und tauscht stattdessen bereits vorhandenen Besitz.
Verwandt in anderen Linien
- Spieltheorie — Stabilität steht auch dort im Mittelpunkt: der Kern fragt, ob eine Kostenaufteilung stabil ist, wie Gale–Shapley eine stabile Zuordnung sucht, und der Moulin-Mechanismus fragt, wer bei privater Zahlungsbereitschaft lügen kann.
- Netzwerkfluss — bipartites Matching ist Fluss auf Einheitsnetzen, und die Netzwerkfluss-Linie verallgemeinert es auf Kapazitäten und Kosten: Dinic ist auf Einheitsnetzen der Algorithmus von Hopcroft–Karp, Successive Shortest Paths ist die Ungarische Methode mit allgemeinen Kapazitäten, und die ε-Skalierung der Auktion kehrt in Cost Scaling wieder.
- Kürzeste Wege — Die Ungarische Methode wechselt in ihrer Wege-Sicht jede Runde auf einen kürzesten Weg über reduzierte Kosten: ein Dijkstra, nur teurer als ihre eigene Preis-Sicht (1698 gegen 140 durchsuchte Kanten bei Reichweite 40).
- Graphen und Netzwerke — Bipartite Graphen sind 2-färbbar: die Hopcroft–Karp-Demo setzt genau diese Zweiteilung voraus, die Graphfärbung-Demo der Graphen-und-Netzwerke-Linie zeigt, dass DSATUR darauf beweisbar höchstens 2 Farben braucht.
- Turnierplanung — Ein Rundenturnier ist eine 1-Faktorisierung von K_n (n−1 perfekte Matchings, eines je Runde), und die Schweizer-System-Paarung ist selbst ein gewichtetes allgemeines Matching je Runde, wie es der Gewichteter-Blossom-Demo löst. Die Schweizer-System-Demo der Turnierplanung-Linie baut stattdessen wörtlich den FIDE-Regeltext nach (Bracket für Bracket statt global) und misst die Differenz zu diesem Weg direkt.
- Zustandsschätzung und Filter — Die Ungarische Methode ordnet auch Messungen Fahrzeugen zu: Die Mehrzielverfolgung-Demo der Linie Zustandsschätzung und Filter löst damit die globale Zuordnung (geprüft gegen scipy.optimize.linear_sum_assignment) und zeigt, wann sie die Identitäten trotzdem schlechter erhält als die einfache Regel.
- Ranking — Die footrule-optimale Aggregation in der Rangaggregation ist ein Zuordnungsproblem und wird mit der Ungarischen Methode berechnet; die exakte Kemeny-Aggregation braucht dagegen eine Teilmengen-Rekursion, deren Aufwand mit 2ⁿ · n wächst.
- Härte und Struktur — Auf bipartiten Graphen sind kleinste Überdeckung und größte unabhängige Menge Matching-Fragen: die Knotenüberdeckung der Linie Härte und Struktur bestätigt den Satz von König (kleinste Überdeckung gleich größtes Matching), und die Reduktions-Demo rechnet auf Rastern selbst ein Matching nach dem Verfahren von Hopcroft–Karp, um den Wert zu beweisen, wo die Zerlegung zu breit ist.
- Ordnung und Abhängigkeit — Die kleinste Zahl von Teams in einem Abhängigkeitsplan ist ein Matching auf der Hülle: Die Demo zu Ketten und Antiketten in der Linie Ordnung und Abhängigkeit rechnet Ketten gleich n minus Matching und nutzt dafür Kuhn und Hopcroft–Karp als Werkzeuge.
- Abstimmen und Fair Teilen — Die Mietaufteilung der Linie Abstimmen und Fair Teilen ordnet Mieter und Flächen zu und setzt dann Preise, damit niemand eine fremde Fläche vorzieht; die Hungarian-Demo dieser Linie sucht dieselbe Zuordnung ohne Preise.
Greedy-Matching an Fahrzeugen und Aufträgen
Verfolgen Sie, wie „billigste Kante zuerst” eine Zuordnung Schritt für Schritt aufbaut und nie wieder zurücknimmt: nie unter der Hälfte der möglichen Paare, aber bei mittlerer Reichweite verliert die Regel auf 99 von 100 Karten Paare (16,7 statt 19,5). Auf der kleinsten Lehrbuchkarte zahlt Greedy 80 % mehr als nötig, weil die billigste Kante die zweitbilligste blockiert.
Verständlich erklärt: erst für Einsteiger, dann für Fachleute
Demo starten →Augmentierende Pfade an Fahrzeugen und Aufträgen
Sehen Sie, wie ein alternierender Weg Greedys Paarzahl auf das nachweisbare Optimum hebt: im Mittel genügen 2,7 Verbesserungswege. Die Kosten bleiben dabei außen vor: im Median 8 % über dem Optimum ab Greedy-Start, auf nur 1 von 100 Karten zufällig optimal.
Demo starten →Hopcroft–Karp an Fahrzeugen und Aufträgen
Verfolgen Sie, wie eine Phase gleich lange, einander nicht berührende kürzeste Verbesserungswege auf einmal umklappt, statt sie einzeln zu suchen. Die Demo zeigt Schichten, Wege und den Beweis der größtmöglichen Paarzahl. Ehrlich gemessen: bei der Demogröße durchsucht das Bündeln mehr Kanten als einzelne Wege (197 gegen 140), der Vorteil zeigt sich erst im Aufwand-Experiment ab 113 Fahrzeugen, und die Kosten bleiben dieselben.
Demo starten →Ungarische Methode an Fahrzeugen und Aufträgen
Schalten Sie zwischen zwei Sichten auf dieselbe Rechnung um: Preise (jede Runde hebt die Preise unversorgter Aufträge an) und kürzeste Wege (ein Dijkstra auf reduzierten Kosten je Runde). Das Ergebnis ist immer optimal (bei Paarzahl UND Kosten), kostet dafür aber rund 12-mal so viele durchsuchte Kanten wie die Verbesserungswege (1698 gegen 140 bei Reichweite 40).
Demo starten →Auktionsalgorithmus an Fahrzeugen und Aufträgen
Sehen Sie, wie Fahrzeuge dezentral auf Aufträge bieten und trotzdem auf allen 100 Karten das Optimum der Ungarischen Methode treffen, solange das ε klein genug ist. Mit fester Schrittweite drohen Preiskriege (im Mittel 3036 Gebote, stark rechtsschief, Ausreißer über 40000); ε-Skalierung (groß anfangen, verkleinern) drückt das auf im Mittel 209 (14,5-mal weniger).
Demo starten →Blossom an Fahrern ohne zwei Seiten
Verfolgen Sie, wie Edmonds' Algorithmus ungerade Kreise (Blüten) kontrahiert, um Paare auch innerhalb einer einzigen Gruppe zu finden. Überraschender Befund: die faire Baseline ohne Kontraktion verliert nur auf 18 von 100 Karten Paare, kann aber selbst ein richtiges Ergebnis fast nie beweisen (nur 16 von 82). Blossom beweist es auf allen 100.
Demo starten →Gewichteter Blossom an Fahrern mit Kosten
Sehen Sie die Konvergenz der Linie: dieselbe Blüten-Kontraktion wie Blossom, jetzt mit den Preisen der Ungarischen Methode kombiniert. Kosten zu ignorieren kostet echt: eine kostenblinde größtmögliche Paarung ist auf allen 100 Karten teurer, im Mittel um 32,42 Minuten, und die Prämie wächst mit der Reichweite streng von 4,13 auf 342,85 Minuten.
Demo starten →Gale–Shapley an Fahrzeugen mit Vorlieben
Verfolgen Sie das aufgeschobene Annehmen: eine Seite schlägt vor, die andere hält immer den besten bisherigen Vorschlag. Das Ergebnis ist stabil, aber nicht billig: auf allen 100 Karten ist das Kosten-Optimum instabil, und Stabilität kostet bei realistischer Streuung im Median 24,3 % Prämie gegenüber der billigsten Paarung gleicher Größe.
Demo starten →Stabile Mitbewohner in einer einzigen Gruppe
Sehen Sie, wie Irvings Algorithmus in einer einzigen Gruppe eine stabile Paarung findet oder beweist, dass es keine gibt: anders als bei zwei Seiten muss sie nicht existieren. Die Demo zeigt den Ablauf Schritt für Schritt. Gegenintuitiv: im Standardfall gibt es nur auf 61 von 100 Karten eine Lösung, und mehr Reichweite macht sie seltener, weil mehr Kandidaten mehr Gelegenheit für einen Kreis in den Vorlieben bieten.
Demo starten →Krankenhaus-Zulassung mit mehreren Plätzen je Klinik
Verfolgen Sie, wie jede Klinik mit mehreren Plätzen die besten Bewerber vorläufig behält und verdrängt, wenn ein besserer kommt. Anders als bei den Mitbewohnern gibt es hier beweisbar eine stabile Zulassung. Die Demo prüft auch, ob Lügen sich lohnt. Ehrlich gemessen: bei reichlicher Kapazität bleibt auf 100 % der Karten eine Klinik trotz freier Plätze leer, und Untertreiben der Kapazität gewinnt nur bei klinikseitigem Vorschlagen (1 von 112 Fällen).
Demo starten →Top Trading Cycles auf dem Dauerparkplatz-Markt
Sehen Sie, wie jeder Beschäftigte mit einem Dauerparkplatz auf den Besitzer seines Lieblingsplatzes zeigt, bis sich ein Kreis schließt und alle darin tauschen: ohne Geld, und niemand steht danach schlechter da als mit dem eigenen Platz. Die Demo zeigt Kreise und Gewinn. Ehrlicher Haken: im Mittel tauschen nur 78,8 % tatsächlich, und ließe man nachträglich nur Kreise der Länge 2 zu, gingen 76,6 % des Distanzgewinns verloren.
Demo starten →Nierentausch unter medizinischen Zwängen
Verfolgen Sie, warum ein Nierentausch nicht einfach ein längerer Top-Trading-Cycle ist: jede Operation eines Kreises muss gleichzeitig stattfinden, eine Kette ab einem altruistischen Spender nicht. Reiner Paartausch ist dadurch exakt lösbar (Maximum-Weight-Matching, dieselbe Aufgabe wie beim Gewichteten Blossom), ab Kreislänge 3 NP-schwer. Die Heuristik trifft ehrlich gemessen nur 58 von 80 kleinen Testfällen exakt.
Demo starten →Online-Matching bei Aufträgen, die nacheinander eintreffen
Sehen Sie, wie Aufträge nacheinander eintreffen und jede Zusage sofort und unwiderruflich ist, bevor der nächste Auftrag bekannt ist. Die Demo vergleicht Greedy, Ranking und Batching mit dem Offline-Optimum, das alle Aufträge vorab kennt. Ehrlicher Haken: auf Zufallskarten findet Greedy im Mittel 89,0 % der möglichen Paare; Ranking findet etwas mehr, ist aber kostenblind und kommt auf 71,0 % Mehrkosten statt 18,8 %.
Demo starten →Welches Matching-Verfahren passt zu meiner Aufgabe?
Zwei Entscheidungsbäume: Baum 1 führt durch den Kosten- und den Online-Ast (acht Verfahren von Greedy bis Online-Matching), Baum 2 durch den Präferenz-/Tausch-Ast (fünf Verfahren von Gale–Shapley bis Nierentausch). Alle Antworten stützen sich auf Messungen in den Demos.
Baum 1: Kosten oder Online?
Baum 2: Bewerbung oder Tausch von Besitz?
Beige Kästen sind Fragen (nicht klickbar), weiße Kästen sind Ergebnisse (klickbar, sie öffnen die jeweilige Demo). Was die Bäume nicht zeigen: Verbesserungswege (Kuhn) sind hier nur das Blatt für kleine und mittlere Karten, weil sie von Hopcroft–Karp oder der Ungarischen Methode abgelöst werden, sobald Größe oder Kosten wichtig werden. Sie sind der direkte Baustein beider Nachfolger. „Viele hundert Teilnehmer“ ist grob: Hopcroft–Karp lohnt sich messbar erst ab rund 113 Fahrzeugen bei den Demo-Einstellungen, nicht scharf ab „hundert“.
Weitere Linien in diesem Bereich
Kürzeste Wege
Wie findet man die beste Route? Zwölf Verfahren von der Breitensuche bis zur Fahrplanauskunft, jedes mit seiner gemessenen Grenze.
Spannbäume
Wie verbindet man alle Standorte mit möglichst wenig Leitung? Elf Stücke vom billigsten Baum über Richtung, Kapazität und Zwischenknoten bis zum Zufallsbaum.
Netzwerkfluss
Wie viel geht durch ein Netz, was kostet es, und was ändert sich, wenn Güter sich Kanten teilen, der Ausbau selbst Entscheidung ist oder die Zeit mitzählt? Neunzehn Stücke von Edmonds-Karp bis zum Fluss über die Zeit.
Schnitte und Zusammenhang
Wie robust hängt ein Netz zusammen, und wie teilt man es in Teile? Acht Stücke über Engstellen, kleinste Schnitte, getrennte Terminals, fehlende Leitungen, ausgewogene Hälften und zusammenhängende Gebiete.
Graphen und Netzwerke
Wie durchmustert man ein Netz, welche Kante ist kritisch, wie wichtig ist ein Knoten, und wie verwundbar ist das Ganze? Dreizehn Stücke von BFS/DFS über die interne Verlinkung einer echten Website bis zur eigenen Forschung über Bandbreite.
Härte und Struktur
Welche Sendungen dürfen zusammen fahren? Acht Stücke über Cliquen, Überdeckungen und Baumweite: was Struktur auf einem Konfliktgraphen leicht macht und wo sie nicht reicht.
Ordnung und Abhängigkeit
Ist ein Plan einhaltbar? Neun Stücke über Kreise, kritische Pfade, Ketten und Reihenfolgen: was Abhängigkeiten zwischen Aufgaben bedeuten und wo die Rechnung teuer wird.
Planarität und Zeichnen
Lässt sich ein Netz ohne Überkreuzung zeichnen, und was folgt daraus? Neun Stücke über Färben, Trennen, Zeichnen, Flüsse als kürzeste Wege, Näherung, Zählen und fast planare Netze.
Netzwerkanalyse
Was verrät die Struktur eines Netzes, wie breitet sich etwas darauf aus, und wie gleichen sich seine Betriebe an? Dreizehn Stücke über Kernzahl, Gemeinschaften, Einfluss, Eindämmung, Meinungen, Standorte und Kontaktfolgen.
Netzmodelle
Welches Zufallsmodell erzeugt welche Eigenschaft eines Netzes, wie prüft man ein Netz gegen ein Modell, und was geschieht, wenn keines passt? Neun Stücke vom Zufallsgraphen bis zur Modellwahl.