Eine Folge zählt Klammern, Bäume und Triangulierungen

Warum ein Parser nicht alles durchprobieren kann

Die Zahl der Möglichkeiten, eine Kette von Multiplikationen zu klammern, ist eine Catalan-Zahl, und sie übersteigt eine Milliarde, bevor die Kette zwanzig Glieder erreicht. Matrizenmultiplikation ist assoziativ, jede Klammerung liefert also dasselbe Produkt — doch nicht jede kostet gleich viel, und der Unterschied zwischen bester und schlechtester Reihenfolge kann Größenordnungen an Rechenoperationen betragen. Die Möglichkeiten aufzuzählen, um die billigste zu finden, ist daher jenseits einer Handvoll Matrizen aussichtslos; die Standardlösung ist dynamische Programmierung, die das Optimum in kubischer Zeit findet, weil sie kein Teilproblem zweimal löst. Die Catalan-Zahl ist das, was dieser Algorithmus vermeidet.

Das Klammerbild erklärt die ganze Familie

Jedes dieser Probleme ist eine Schrittfolge, die nie negativ werden darf. Lies eine öffnende Klammer als plus eins und eine schließende als minus eins: Eine gültige Zeichenkette ist genau ein Weg, der bei null endet, ohne je darunter zu tauchen. Ein in Ordnung durchlaufener Binärbaum ergibt denselben Weg, eine Triangulierung ebenso, und eine Warteschlange, die nie einen noch nicht eingetroffenen Kunden bedienen darf, ebenfalls. Ist die Verkleidung ab, deckt ein einziges Abzählargument alle ab, und der Standardbeweis ist ein Spiegelungstrick, der die schlechten Wege zählt, indem er sie in eine leicht abzählbare Menge spiegelt.

Häufige Fragen

Warum beginnt die Folge mit zwei Einsen?

Weil es genau eine Art gibt, nichts zu tun, und genau eine, das Kleinstmögliche zu tun. Bei null Klammerpaaren ist die leere Zeichenkette die einzige gültige Anordnung, bei einem Paar gibt es nur eine Platzierung. Folgen, die Anordnungen zählen, beginnen sehr oft so, und die doppelte Eins zeigt, dass die Definition sinnvoll auf den leeren Fall ausgedehnt wurde, statt willkürlich beim ersten interessanten Wert zu starten. Rechnerisch zählt es auch: Die Rekursion braucht beide als Basis, bevor sie irgendetwas erzeugen kann.

Wie schnell wachsen diese Zahlen wirklich?

Etwas weniger als das Vierfache je Schritt, und das Verhältnis nähert sich mit wachsendem n langsam der Vier: vom neunzehnten zum zwanzigsten Term beträgt es 3,714, vom neunundzwanzigsten zum dreißigsten 3,807. Das stellt sie zwischen das exponentielle Wachstum der Zweierpotenzen und das weit heftigere der Fakultäten — genug, um rohe Gewalt schnell zu schlagen, nicht genug, um sie sofort zu schlagen. Praktisch liegt die Grenze bei etwa zwanzig: darunter reicht oft eine erschöpfende Suche, darüber braucht es etwas Klügeres, und der genaue Punkt hängt davon ab, was ein Fall kostet.