Die Manhattan-Distanz-Heuristik ist wahrscheinlich die meistgenutzte Heuristik in heuristischer Suche. Informell in den 1960ern für das 15-Puzzle eingeführt, formal in der A*-Arbeit von 1968 festgehalten, bis heute das Erste, was jedes KI-Lehrbuch lehrt. Dieser Artikel handelt davon, warum sie funktioniert, was sie gut macht, und wo sie aufhört zu reichen.
Die Definition
Für ein N×N-Schiebepuzzle, für jedes Plättchen (die Lücke ignorierend) berechnen:
Distanz = | Zeile_aktuell − Zeile_Ziel | + | Spalte_aktuell − Spalte_Ziel |
Über alle Plättchen summieren. Diese Summe ist die Manhattan-Distanz des aktuellen Bretts zum Ziel.
Warum „Manhattan“? Die Straßen Manhattans sind ein reguläres Raster. Um von einer Ecke zur anderen zu kommen, läuft man so viele Blöcke Ost-West plus so viele Blöcke Nord-Süd. Man kann nicht diagonal abkürzen. Die Gesamtzahl gelaufener Blöcke ist die Manhattan-Distanz — auch Taxicab-Distanz oder L¹-Norm.
Für ein Plättchen die gleiche Logik: Es kann sich horizontal oder vertikal um eine Zelle pro Zug bewegen, aber nicht diagonal. Die Mindestzahl an Zügen, um es vom Ist- zum Soll-Ort zu bringen, ist die Zeilen-Distanz plus die Spalten-Distanz.
Zulässigkeit
A* verlangt von der Heuristik, zulässig zu sein: Sie darf die tatsächliche Anzahl verbleibender Züge nie überschätzen. Überschätzt die Heuristik, kann A* den optimalen Pfad zu früh abschneiden und eine suboptimale Lösung liefern.
Manhattan-Distanz ist zulässig, weil:
- Jedes einzelne Plättchen muss mindestens seine Zeilen- + Spaltendistanz reisen, weil Züge Einzelschritte in Zeile oder Spalte sind.
- Die Summe über alle Plättchen kann die Wirklichkeit nicht überschießen, weil jeder Zug genau ein Plättchen um genau eine Zelle voranbringt. (Er bewegt auch die Lücke, aber die zählen wir nicht.)
- Tatsächlich ist die echte Distanz mindestens die Manhattan-Distanz, weil Plättchen oft für andere zur Seite geschoben werden müssen — aber nie weniger.
Also Manhattan ≤ tatsächlich. Zulässig.
Konsistenz
Eine stärkere Eigenschaft: Konsistenz, manchmal auch Monotonie der Heuristik genannt. Eine Heuristik ist konsistent, wenn für jeden Zustand s und jeden Nachfolger s' über Zug m:
h(s) ≤ cost(m) + h(s')
Auf Deutsch: Der Heuristikwert kann durch einen Zug nicht um mehr als eins fallen.
Manhattan-Distanz ist konsistent, weil ein einzelner Zug die Manhattan-Distanz um genau +1 oder −1 ändert. (Ein Plättchen bewegt sich um eine Zelle, sein Beitrag zur Heuristik ändert sich um ±1; die Beiträge aller anderen sind unverändert.)
Konsistenz zählt, weil sie garantiert, dass A* nie einen schon geschlossenen Zustand wiedereröffnet. Implementierungen müssen den Inkonsistenz-Fall nicht behandeln, was Code und Beweise vereinfacht.
Warum sie in der Praxis so gut funktioniert
Drei konkrete Eigenschaften:
Sie ist billig zu berechnen. O(N²) pro Brett — Summe über alle Plättchen, jeder Beitrag konstante Zeit. h(s) zu berechnen dauert Mikrosekunden auf jedem modernen Computer.
Sie ist eng genug, um tief zu beschneiden. Für 15-Puzzles liegt der Manhattan-Wert im Schnitt bei 75–90 % der echten Distanz. A* mit so enger Heuristik erkundet einen winzigen Bruchteil des Zustandsraums.
Sie kombiniert gut mit Linear Conflict. Hinzufügen von 2 Zügen pro „Linear Conflict“ (zwei Plättchen in derselben Zeile, beide dazugehörend, aber in falscher Reihenfolge) ergibt eine strikt engere Heuristik bei marginalen Berechnungskosten.
Wo sie zu kurz greift
Manhattan-Distanz behandelt Plättchen, als könnten sie einander frei durchdringen. Das können sie nicht. Der tiefste blinde Fleck:
Konflikte in einer Spalte oder Zeile. Sind die Plättchen 2 und 3 beide in Zeile 1, aber in falscher Reihenfolge, gibt Manhattan ihnen ihre direkten Distanzen und bemerkt nichts. In Wirklichkeit muss eines aus der Zeile, das andere muss vorbei, und das erste muss zurück. Das sind mindestens 2 Extrazüge, die Manhattan nicht sieht. Linear Conflict flickt das.
„Walking“-Struktur. Manhattan ignoriert, wie Plättchen innerhalb einer Zeile oder Spalte zueinander stehen, wenn alle zu dieser Zeile oder Spalte gehören. Eine Zeile von vier Plättchen in falscher Permutation braucht mehrere „Zeilentausch“-Operationen — eine Struktur, die Walking Distance einfängt.
Disjunkte Teilmengen-Wechselwirkungen. Für jede disjunkte Partition der Plättchen ist die optimale Kosten, jede Partition in Position zu permutieren, eine engere Untergrenze als Manhattan (das ist die Singleton-Partition). Additive Mustertabellen nutzen das aus.
Die Progression: Manhattan → Manhattan + Linear Conflict → Walking Distance → Mustertabellen. Jede ist eine strikte Verbesserung.
Warum größere Bretter mehr brauchen
Manhattan-Distanz liegt im Schnitt bei 75–90 % der echten Distanz beim 15-Puzzle. Beim 24-Puzzle bei etwa 65 %. Beim 35-Puzzle bei etwa 55 %.
Der Grund: Mit wachsenden Brettern werden Plättchen-Konflikte und „Walking-Struktur“ relativ zu direkten Distanzen wichtiger. Manhattan-Distanz, die beides ignoriert, unterschätzt bei größeren Brettern grober.
Deshalb sind Mustertabellen für das Lösen von 24-Puzzle und 35-Puzzle im Wesentlichen Pflicht. Manhattan ist okay fürs 15-Puzzle und 8-Puzzle, verliert aber zu viel Information bei größeren Größen.
Geometrische Intuition
Eine schöne Art, über Manhattan-Distanz nachzudenken: Stellen Sie sich eine flache Ebene mit einem Plättchen darauf vor. Die Menge der Punkte, die das Plättchen in k Zügen erreichen kann, ist ein Diamant mit Seitenlänge k — Punkte mit Manhattan-Distanz ≤ k. (Das euklidische Äquivalent wäre ein Kreis mit Radius k.)
Manhattan-Distanz ist die natürliche Geometrie der Raster-Bewegung. Hat man ein Bewegungsmodell, das auf Rasterschritte beschränkt ist, ist Manhattan-Distanz die Geometrie; euklidische Distanz ist irrelevant.
Was das für App-Entwickler bedeutet
Wer eine Hinweistaste für eine Schiebepuzzle-App schreibt und sie in Millisekunden braucht:
- 3×3 — Manhattan + Linear Conflict reicht. A* erkundet Dutzende Zustände; fertig in Mikrosekunden.
- 4×4 — Manhattan + Linear Conflict ist schnell genug für einen Hinweis (ein Zug, nicht die volle optimale Lösung). Für die volle optimale Lösung ist Walking Distance die richtige Wahl.
- 5×5+ — Mustertabellen. Manhattan reicht nicht, um in das Zeitbudget einer Hinweistaste zu passen.
Slide Puzzle verwendet Manhattan + Linear Conflict für die Hinweistaste auf 3×3 und 4×4, Walking Distance für die 4×4-Schwierigkeits-Kalibrierung und eine 5+5+5+9-Mustertabelle für die 5×5- und 6×6-Kalibrierung. Die Manhattan-Heuristik ist die Grundlage all dieser.
Eine letzte Intuition
Die Manhattan-Distanz-Heuristik ist, was Schiebepuzzles überhaupt suchbar macht. Ohne sie würden A* und IDA* zu BFS entarten — und BFS endet beim 15-Puzzle nicht in der Lebensdauer des Universums.
Diese Heuristik ist die eine Codezeile, die ein unmögliches Problem in eine Millisekunden-Berechnung verwandelt. Sie zu verstehen lohnt sich.