Beispiel: 0/1 -Integer-Linear-Programming

Zustandsraum für 0/1 Integer-Linear-Programming-Instanz

Das 0/1 -Integer-Linear-Programming-Problem läßt sich als Wegsuche im Zustandsraum wie folgt formulieren: Im Startknoten sind alle Variablen noch unbesetzt. Jeder Nonterminalknoten hat zwei Söhne, in dem eine noch nicht fixierte Variable alternativ auf 0 oder 1 gesetzt wird. Ein Knoten mit mindestens einer freien Variablen und der Eigenschaft

ist ein Nonterminalknoten, da durch weitere Fixierung noch die Möglichkeit besteht, die Randbedingung einzuhalten. Die Kanten für die Fixierung der Variablen x_i mit 1 wird mit c_i bewertet, alle anderen Kanten mit 0. Die Bewertung der Zielknoten ergibt sich aus der Summe der verwendeten Kanten.

Bei einigen Problemen ist es für Nonterminalknoten möglich, die Kosten zum Erreichen eines Zielknotens abzuschätzen. Seien g(x) die Kosten, um den Zustand x vom Startknoten zu erreichen. Sei h(x) eine heuristische Schätzung für die Kosten, um von x aus einen Zielknoten zu erreichen. Ist h(x) eine untere Schranke, so wird h zulässig genannt. Die Funktion

l (x) : = g(x) + h(x)

ist eine untere Schranke für jede Lösung, die durch Erweiterung des Wegs vom Startknoten über den Zwischenknoten x entsteht.

Für das 8-Puzzle-Problem ergibt sich eine zulässige heuristische Schätzung wie folgt: Für zwei Feldpositionen (x₁,y₁) und (x₂,y₂) sei die Manhattan-Distanz

|x₁ - x₂| + |y₁ - y₂| .

Für zwei Puzzlezustände ist

h(x) = Summe der Manhattan-Distanzen zwischen korrespondierenden Positionen aller Plättchen

eine untere Schranke für die Zahl der Verschiebeoperationen.