Zuordnung gegen Rundreise verständlich erklärt

Eine Tabelle mit Fahrkosten zwischen Orten trägt zwei Aufgaben, die sich fast gleich anhören: Fahrzeuge Aufträgen zuordnen und eine Rundreise planen. Die erste bleibt auch bei großen Aufgaben lösbar (in der Demo bis hundert Orte), die zweite wird mit jedem weiteren Ort um ein Mehrfaches aufwendiger. Diese Seite erklärt zuerst ohne Formeln, was „schwer“ (fachlich: NP-schwer) dabei wirklich heißt, und danach für Fachleute mit Modell, Formeln, Messwerten und Grenzen.

Zuletzt aktualisiert: 28. Oktober 2026

Ein Wort unbekannt? Das Begriffsverzeichnis erklärt es in wenigen Sätzen.

Eine Tabelle, zwei Aufgaben

Stellen Sie sich eine Tabelle vor, die für jedes Paar von Orten angibt, was die Fahrt vom einen zum anderen kostet, zum Beispiel zwischen Hafen, Werk, Lager und Markt. Fachleute nennen das eine Kostenmatrix. Aus dieser Tabelle lassen sich zwei Aufgaben machen, die sich ähnlich anhören.

Aufgabe eins, die Zuordnung: Vier Lieferwagen stehen an vier Orten. Jeder Wagen soll zu einem anderen Ort fahren als dem, an dem er steht, und an jedem Ort soll genau ein Wagen ankommen. Welcher Wagen fährt wohin, damit die Fahrtkosten zusammen möglichst klein sind? Jede Fahrt zählt für sich; was die anderen Wagen tun, spielt keine Rolle.

Aufgabe zwei, die Rundreise: Ein einziger Wagen soll alle Orte nacheinander besuchen und am Ende zum Start zurückkehren, und zwar in der Reihenfolge mit den geringsten Gesamtkosten. Hier hängen die Kosten einer Fahrt davon ab, woher der Wagen kommt und wohin er danach fährt.

Beide Aufgaben suchen eine Anordnung der Orte, und für beide führt ein sicherer Weg zum Ziel: alle denkbaren Anordnungen aufschreiben und die billigste nehmen. Das Problem ist, dass die Zahl der Möglichkeiten mit jedem weiteren Ort schnell wächst. Zu dieser Seite gehört eine Demo, ein Programm zum Ausprobieren. Sie zählt, wie oft ein Verfahren in die Tabelle schauen muss, statt Sekunden zu messen; so hängt das Ergebnis nicht vom Rechner ab. Bei zwölf Orten muss das Durchprobieren der Rundreisen dort mehrere hundert Millionen Mal in die Tabelle schauen, das der Zuordnungen noch öfter, weil bei der Rundreise der Startort feststeht.

Der Unterschied: Für eine Aufgabe gibt es eine Abkürzung

Für die Zuordnung hat man eine Abkürzung gefunden, die Ungarische Methode. Sie baut die Zuordnung Schritt für Schritt auf und ändert frühere Paarungen, wenn es sich lohnt, ohne je alle Möglichkeiten anzusehen. Bei zwölf Orten braucht sie in der Demo höchstens wenige Tausend Blicke in die Tabelle. Dahinter steht eine Obergrenze für den schlimmsten Fall, keine Messung: Der Aufwand wächst höchstens so, als würde man die Zahl der Orte dreimal mit sich selbst malnehmen. Verdoppelt man die Orte, steigt er also höchstens auf das Achtfache.

Für die Rundreise ist keine solche Abkürzung bekannt. Es gibt aber ein besseres Verfahren als das Durchprobieren, das ebenfalls sicher die billigste Rundreise findet: Held–Karp. Es merkt sich die billigsten Teilstrecken zu jeder Gruppe von Orten und baut darauf auf. Bei zwölf Orten liest es in der Demo nur etwa den achttausendsten Teil dessen, was das Durchprobieren liest. Eine echte Abkürzung ist es trotzdem nicht: In der Demo macht ein zusätzlicher Ort das Verfahren mehr als doppelt so aufwendig, gemessen beim Schritt von elf auf zwölf und von fünfzehn auf sechzehn Orte.

Am deutlichsten sieht man den Unterschied, wenn die Demo einen tausendmal schnelleren Rechner annimmt. Beim Durchprobieren der Rundreisen schafft er drei Orte mehr, bei Held–Karp acht. Bei der Zuordnung wächst die lösbare Aufgabe nach der Obergrenze auf das Zehnfache, in der Demo von hundert auf tausend Orte. Bei der einen Aufgabe kauft man mit Rechenleistung also einige Orte, bei der anderen ein Vielfaches.

Was „schwer“ hier heißt

Der Unterschied liegt also nicht darin, dass eine Aufgabe zu viele Möglichkeiten hätte; die haben beide. Er liegt darin, ob es eine Abkürzung gibt. Das Durchprobieren ist bei beiden gleich schlecht, ob eine Aufgabe schwer ist, hängt deshalb an der Aufgabe und nicht am Verfahren. Eine Aufgabe mit Abkürzung nennen Fachleute leicht, auch wenn sie groß ist. Eine Aufgabe wie die Rundreise, für die man trotz langer Suche keine solche Abkürzung kennt, nennen sie NP-schwer. Die Kürzel dahinter müssen Sie sich nicht merken.

NP-schwer bedeutet: Trotz langer Suche kennt man für die Aufgabe keine Abkürzung. Dass es keine gibt, wird angenommen, ist aber nicht bewiesen. Es heißt deshalb weder „unlösbar“ noch „jede Aufgabe ist hoffnungslos“: Kleine Rundreisen löst die Demo exakt. Es heißt: Mit wachsender Größe ist nach heutigem Wissen mit stark wachsendem Aufwand zu rechnen.

Was die beiden Aufgaben verbindet

Jede Rundreise ist auch eine Zuordnung, aber eine Zuordnung darf in mehrere kleine Runden zerfallen. Wer mehr erlaubt, findet mindestens so billige Lösungen: Die billigste Zuordnung ist eine Untergrenze für die Rundreise, und der Abstand zeigt, was die Bedingung „nur eine einzige Runde“ kostet (Zahlen im Fachteil).

Wie ernst ist das Modell zu nehmen?

Die Demo arbeitet mit erzeugten Beispielen: Entfernungen zwischen zufälligen Orten auf einer Karte oder eine Tabelle mit Zufallszahlen. Sie zählt Blicke in die Tabelle statt Sekunden und zeigt nur exakte Verfahren, also solche, die sicher die billigste Lösung finden, keine schnellen Näherungsverfahren für die Rundreise. Sie zeigt, wie sich der Aufwand mit der Größe verhält, nicht wie lange ein bestimmter Rechner für Ihre echte Tourenplanung braucht.

Was Sie mitnehmen: Fragen Sie bei einer Planungsaufgabe, ob die Kosten an der einzelnen Paarung hängen (dann ähnelt sie einer Zuordnung) oder daran, was vorher und nachher kommt (dann ähnelt sie einer Rundreise). Bei Aufgaben vom zweiten Muster lohnt die Frage an Planer oder Anbieter, ob das Ergebnis nachweislich das billigste ist oder nur ein gutes. Eine gute Antwort lautet nicht unbedingt „das billigste“: Näherungsverfahren sind üblich, aber es sollte benannt werden, wie gut das Ergebnis ist, zum Beispiel im Vergleich zu einer bekannten Untergrenze. Das gilt, solange die Aufgabe in dieser reinen Form vorliegt; echte Aufgaben mit Zeitfenstern oder Kapazitäten kommen in der Demo nicht vor.

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.

Modell und Annahmen

Dieser Teil ist eigenständig lesbar. Er fasst die formale Beschreibung der Demo zusammen; die vollständige Fassung steht im Expander „📐 Mathematische Formulierung“ der Demo.

• Matrix: \(n \times n\)-Kosten \(c_{ij}\), Diagonale gesperrt (kein Fahrzeug fährt zu sich selbst, keine Rundreise bleibt am Ort). Zwei Arten: Karte (Entfernungen zwischen zufälligen Orten in [0, 100]², auf ganze Zahlen gerundet, symmetrisch) und Zufallsmatrix (ganze Zahlen 1 bis 100, in jede Richtung anders). Beide sind Instanzfamilien, keine Naturgesetze.
• Zuordnung: Permutation \(\sigma\) ohne Fixpunkt, die \(\sum_i c_{i\,\sigma(i)}\) minimiert. Das Ziel zählt je Position, der Nachbar spielt keine Rolle.
• Rundreise: zyklische Reihenfolge ab Ort 1, die die Summe über aufeinanderfolgende Paare minimiert. Das Ziel hängt vom Nachbarn ab.
• Beziehung: Jede Rundreise ist eine Zuordnung mit einem einzigen Kreis. Daher \(\text{OPT}_{\text{Zuordnung}} \le \text{OPT}_{\text{Rundreise}}\), mit Gleichheit, wenn die billigste Zuordnung selbst ein einziger Kreis ist. Die Zuordnung ist also eine Relaxation der Rundreise: Sie darf in mehrere Teilkreise zerfallen.
• Aufwand: Gezählt wird der Zugriff auf die Kostenmatrix, nicht die Laufzeit. Jedes Verfahren hat ein Budget und bricht ab, bevor es mehr Zugriffe ausgibt; die App zeigt dann „bisher beste“ Werte, nie „optimal“.
• Verfahren: Aufzählen aller Zuordnungen (n · n! Zugriffe, exakt), Ungarische Methode (Potenziale und kürzeste Verbesserungswege, Schranke n³, exakt), Aufzählen aller Rundreisen (n · (n−1)! Zugriffe, Reihenfolgen ab Ort 1, exakt) und Held–Karp (Teilmengen-DP, (n−1)(n−2) · 2^(n−3) + 2(n−1) Zugriffe, exakt).
• Klassen: Sie werden an Ja/Nein-Fragen definiert („Gibt es eine Zuordnung mit Kosten höchstens K?“ bzw. „Gibt es eine Rundreise mit Kosten höchstens K?“); die Optimierung ist die Suche nach dem kleinsten K. Polynomial heißt: wie n² oder n³ (Klasse P). Exponentiell heißt: wie 2ⁿ oder n!.

Die Formeln

Die Zuordnung sucht eine Permutation \(\sigma\) ohne Fixpunkt mit minimalen Kosten. Als lineares Programm mit Zeilen- und Spaltensummen gleich 1 liegen die Ecken des zulässigen Bereichs bei ganzen Zahlen (Satz von Birkhoff und von Neumann); deshalb ist das Problem polynomial lösbar, die Ungarische Methode kommt mit höchstens \(O(n^3)\) Schritten aus.

\[\min_{\sigma} \sum_{i=1}^{n} c_{i\,\sigma(i)}\]

Die Rundreise sucht eine zyklische Reihenfolge \(\pi\) aller Orte:

\[\min_{\pi} \sum_{i=1}^{n} c_{\pi(i)\,\pi(i+1)} \quad (\pi(n+1) = \pi(1))\]

Verlangt man nur „jeder Ort hat einen Nachfolger und einen Vorgänger“, bleibt die Zuordnung übrig, die mehrere Kreise haben darf. Daraus folgt:

\[\text{OPT}_{\text{Zuordnung}} \;\le\; \text{OPT}_{\text{Rundreise}}\]

Held–Karp: \(D(S, j)\) sei der billigste Weg von Ort 1 über alle Orte der Menge \(S\), der in \(j \in S\) endet. Die Rekursion lautet

\[D(\{j\}, j) = c_{1j}, \qquad D(S, j) = \min_{k \in S \setminus \{j\}} \big( D(S \setminus \{j\}, k) + c_{kj} \big)\]

und die Rundreise kostet \(\min_j \big( D(\{2, \dots, n\}, j) + c_{j1} \big)\). Die Demo zählt jeden Lesezugriff auf \(c_{ij}\):

\[\text{Aufzählen (Zuordnung)}: n \cdot n! \qquad \text{Aufzählen (Rundreise)}: n \cdot (n-1)! \qquad \text{Held–Karp}: (n-1)(n-2)\,2^{\,n-3} + 2(n-1)\]

Beide Aufzählungen wachsen faktoriell; die Klasse trennt also nicht das Aufzählen, sondern das beste bekannte Verfahren. Die Zählformeln gelten für diese Implementierungen.

Befunde

Alle Zahlen stammen aus der README der Demo (jede steht in deren Tests, tests/test_claims.py). Medianwerte sind über 20 feste Instanzen je Größe gebildet, das Wachstum der Ungarischen Methode über fünf feste Zufallsmatrizen. Die Zahlen aus den Voreinstellungen sind Einzelinstanzen und als solche ausgewiesen. Die Lücke ist der Anteil, um den die billigste Zuordnung unter der Rundreise liegt.

Frage	Befund
Wie viel liest das Aufzählen, wie viel das beste Verfahren? (n = 12)	Aufzählen aller Zuordnungen 5.748.019.200 Zugriffe, Ungarisch höchstens 1.728 (Schranke n³, gemessen im Median 238). Aufzählen aller Rundreisen 479.001.600, Held–Karp 56.342, also rund 8.502-mal weniger.
Wie wächst Held–Karp?	Jeder zusätzliche Ort verteuert Held–Karp um den Faktor 2,44 (n = 11 → 12) bzw. 2,31 (n = 15 → 16), das Aufzählen der Rundreise um den Faktor n. Exponentiell bleibt beides.
Wie weit kommt man in 10⁶ Zugriffen?	Aufzählen aller Zuordnungen bis n = 8, aller Rundreisen bis n = 9, Held–Karp bis n = 15, Ungarisch (nach der Schranke n³) bis n = 100.
Was bringt tausendfache Hardware?	Das Aufzählen der Rundreisen gewinnt 3 Orte (9 → 12), Held–Karp 8 Orte (15 → 23): additiv. Die Ungarische Methode wächst nach der Schranke auf das Zehnfache (100 → 1.000): multiplikativ. Bei 10⁸ und 10⁹ Zugriffen dieselbe Struktur.
Wie weit liegt die billigste Zuordnung unter der Rundreise? (Karte)	Median der Lücke 12,5 / 16,8 / 18,1 / 22,0 / 24,9 % bei n = 4 / 6 / 8 / 10 / 12, Median der Teilkreise 2 / 3 / 4 / 4 / 5. In 0 von 100 Karten (5 Größen × 20) ist die billigste Zuordnung schon eine Rundreise; Maximum der Lücke 53,1 % (Einzelwert bei n = 4). Eine unabhängige Prüfung mit anderen Karten fand etwa 15 bis 21 % (nicht Teil der Tests); belastbar ist die Größenordnung 15 bis 25 %, nicht die Dezimalen.
Und bei Zufallsmatrizen?	Median der Lücke 0,0 / 5,3 / 6,7 / 3,7 / 7,1 %, Median der Teilkreise 1 / 2 / 2 / 2 / 2. Die Zuordnung ist bei n = 4 in 16, bei n = 6, 8, 10 in je 4 und bei n = 12 in 2 von 20 Fällen schon eine Rundreise. Die Lücke ist hier klein, aber nicht monoton.
Erreicht die Ungarische Methode ihre Schranke n³?	Nicht auf diesen Matrizen. Gemessen wächst sie auf Zufallsmatrizen etwa wie n^2,4 (Ausgleichsgerade über n = 10 bis 160; bei n = 160 im Median 181.650 Zugriffe gegen 4.096.000), auf Karten etwa wie n^2,2 (78.726 bei n = 160). Die Schranke gilt für den schlimmsten Fall, der hier nicht gebaut wurde.
Lehrbeispiel von Hand (4 Orte)	Billigste Zuordnung 4 in zwei Teilkreisen, beste Rundreise 22, Lücke 81,8 %.
Voreinstellung (Einzelinstanz: n = 8, Karte, Zufalls-Seed 35)	Zuordnung 190 (71 Zugriffe, 4 Teilkreise), Rundreise 316 (1.358 Zugriffe), Lücke 39,9 %; ausdrücklich eine Einzelinstanz und deutlich über dem Median 18,1 %.

Zur Absicherung: Ungarisch gegen scipy.optimize.linear_sum_assignment und Aufzählen, Held–Karp gegen Aufzählen und gegen CP-SAT, Relaxation (Zuordnung ≤ Rundreise, Gleichheit bei einem Kreis). Ein großer Prüflauf (je 60 bis 400 Instanzen) fand 0 Abweichungen.

Grenzen

• Zugriffe sind keine Laufzeit: Speicher, Python-Aufwand und Cache fehlen; die Zählung vergleicht Verfahren, nicht Rechner. Die Zählformeln gelten für diese Implementierungen.
• „NP-schwer“ ist eine Aussage unter P ≠ NP: Sie ist unbewiesen; „kein polynomiales Verfahren bekannt“ heißt nicht „unmöglich“. Dass n! und 2ⁿ die Rundreise kennzeichnen, sagt die Demo nur über Aufzählen und Held–Karp.
• Der schlimmste Fall der Ungarischen Methode wird nicht gezeigt: Die Messung belegt, dass die Schranke n³ auf Zufallsmatrizen und Karten weit unterschritten wird, nicht, dass sie nie erreicht wird.
• Zwei Matrixarten: Die Lücke zwischen Zuordnung und Rundreise ist eine Aussage über diese Familien. Die Karten-Medianwerte hängen an 20 festen Instanzen je Größe (gemessen n = 4 bis 12), die Zufallswerte schwanken nicht monoton mit n.
• Karten sind gerundet: Entfernungen werden auf ganze Zahlen gerundet; Gleichstände zwischen verschiedenen Reihenfolgen sind dadurch häufiger als bei reellen Zahlen.
• Nur exakte Verfahren für die Rundreise: Heuristiken (2-opt, Lin–Kernighan) gehören nicht zu dieser Demo.
• In P heißt nicht schnell: Die Klasse sagt etwas über das Wachstum, nicht über die Geschwindigkeit bei einer bestimmten Größe. Die Entscheidungsfrage „Kosten höchstens K?“ wird in der App erklärt, aber nicht als Ja/Nein-Anzeige ausgespielt; der Beweis der Härte (Reduktionen, NP-Vollständigkeit) ist nicht Teil dieser Demo.

Quellen

• Kuhn, H. W. (1955): The Hungarian method for the assignment problem. Naval Research Logistics Quarterly 2, 83–97.
• Munkres, J. (1957): Algorithms for the assignment and transportation problems. Journal of the Society for Industrial and Applied Mathematics 5.
• Bellman, R. (1962): Dynamic programming treatment of the travelling salesman problem. Journal of the ACM 9, 61–63.
• Held, M., Karp, R. M. (1962): A dynamic programming approach to sequencing problems.
• Karp, R. M. (1972): Reducibility among combinatorial problems. In: Miller, R. E., Thatcher, J. W. (Hrsg.): Complexity of Computer Computations, Plenum, 85–103 (NP-Vollständigkeit des Hamiltonkreises und damit die Härte der Rundreise-Entscheidung).
• Quelltext, Messreihen und Tests der Demo: github.com/sebastian-hanisch/zuordnung-vs-rundreise-demo.

Die genannten Arbeiten wurden für diese Seite nicht nachgeschlagen; die Literaturangaben stammen aus der README der Demo, die sie als anhand der Quellen geprüft ausweist. Der Satz von Birkhoff und von Neumann ist dort nur genannt, nicht nachgeschlagen. Die Erklärung der Klassen P und NP-schwer, des exponentiellen Wachstums und der Entscheidungsfrage ist Standardwissen der Komplexitätstheorie bzw. stammt aus dem Expander der App; sie wurde für diese Seite nicht an Lehrbüchern geprüft.