Constraints

Stell dir vor, du planst einen Stundenplan für eine Schule. Kein Lehrer kann in zwei Räumen gleichzeitig unterrichten. Eine Klasse hat höchstens sechs Stunden am Tag. Der Chemieraum ist nur vormittags frei. Solche festen Bedingungen nennt man Constraints, auf Deutsch Nebenbedingungen. Sie legen nicht fest, welcher Stundenplan der beste ist. Sie legen fest, welche Pläne überhaupt erlaubt sind. Alles, was eine Bedingung verletzt, fällt sofort raus.

Warum Regeln oft wichtiger sind als die beste Lösung

Viele Aufgaben in der Praxis haben unfassbar viele mögliche Lösungen. Bei zwanzig Klassen und dreißig Lehrern gibt es mehr Stundenpläne als Atome in einem Stück Kreide. Ein Computer kann sie unmöglich alle durchprobieren. Constraints machen die Aufgabe erst lösbar, weil sie riesige Teile dieser Möglichkeiten mit einem Schlag ausschließen.

Dazu kommt ein zweiter Punkt: Eine rechnerisch optimale Lösung ist wertlos, wenn sie gegen Regeln verstößt. Ein Lieferplan, der Fahrer zwölf Stunden am Stück fahren lässt, ist nicht clever, sondern illegal. In der Wirtschaft und in der Technik sind Constraints deshalb oft Gesetze, Sicherheitsvorschriften oder physikalische Grenzen. Man verhandelt nicht über sie.

Fachleute unterscheiden harte und weiche Bedingungen. Harte Bedingungen müssen erfüllt sein, sonst zählt die Lösung nicht. Weiche Bedingungen sind Wünsche: Freistunden möglichst vermeiden, Sport nicht in der ersten Stunde. Weiche Bedingungen werden mit Punkten bewertet, harte mit einem einfachen Ja oder Nein.

Wie ein Programm den Suchraum einengt

Technisch beschreibt man solche Aufgaben mit drei Zutaten. Erstens die Variablen, also die offenen Entscheidungen, etwa der Termin für jede Unterrichtsstunde. Zweitens die Wertebereiche, also welche Termine überhaupt in Frage kommen. Drittens die Constraints, die festlegen, welche Kombinationen zusammenpassen. Diese Kombination heißt Constraint-Satisfaction-Problem, kurz CSP.

Ein Löser arbeitet dann ähnlich wie ein Mensch beim Sudoku. Er setzt einen Wert probeweise ein und schaut, was daraus folgt. Trägt er in ein Feld eine Sieben ein, verschwindet die Sieben aus allen Feldern derselben Zeile. Dieses Weiterreichen von Folgen nennt man Constraint-Propagation. Es schrumpft die Auswahl, ohne dass ein einziger Fall vollständig durchgerechnet wird.

Führt ein Weg in eine Sackgasse, geht das Programm einen Schritt zurück und probiert eine andere Belegung. Das heißt Backtracking. Ein häufiger Irrtum ist, das für stumpfes Durchprobieren zu halten. Tatsächlich erkennt ein guter Löser Widersprüche sehr früh und spart sich dadurch Milliarden von Versuchen.

Von Sitzplänen bis zu Sperren im Chatbot

Constraints stecken in vielen Systemen, die man täglich nutzt. Fluggesellschaften verteilen damit Crews auf Flüge, Bahnbetreiber legen Gleisbelegungen fest, Fabriken planen Maschinenzeiten. Auch Navigationsdienste rechnen mit Bedingungen, etwa mit einer Brücke, die für Lastwagen gesperrt ist. In Tabellenprogrammen und Datenbanken sorgen Constraints dafür, dass niemand ein Geburtsdatum in der Zukunft speichert.

In der aktuellen KI-Berichterstattung taucht das Wort in einer zweiten Bedeutung auf. Dort meint es Grenzen, die ein Sprachmodell einhalten soll: keine Anleitung für Waffen, eine Antwort nur im JSON-Format, höchstens 200 Wörter. Solche Vorgaben sind allerdings weniger verlässlich als eine echte mathematische Nebenbedingung. Ein Sprachmodell kann sie ignorieren, ein Constraint-Löser kann das nicht.

Deshalb kombinieren Firmen zunehmend beides. Das Sprachmodell macht einen Vorschlag, ein nachgeschaltetes Programm prüft ihn gegen harte Regeln. Wenn du in News liest, ein Assistent liefere garantiert gültige Ausgaben, steckt meist genau so eine Prüfschicht dahinter.