Suchprobleme

Bei Lunar Lockout ist eine Folge von Zügen gesucht.

Nach jeder Folge entsteht eine bestimmte Konfiguration.

Für ein Spielfeld mit f Feldern (z. B. f = 9 ^. 10 = 90) und r Robotern (z. B. r = 7) gibt es $\le$(f + 1)^r Konfigurationen.

In kürzesten Lösungen gibt es keine Wiederholungen von Konfigurationen.

Falls eine Konfiguration überhaupt lösbar ist, dann hat sie auch eine Lösung mit $\le$(f + 1)^r Zügen.

In jeder Konfiguration gibt es $\le$4 ^. r Züge.

Der Suchraum ist ein Baum der Tiefe $\le$(f + 1)^r.

Jeder Knoten hat $\le$4 ^. r direkte Nachfolger.

Der Baum hat insgesamt $\le$(4 ^. r)^(f+1)r Knoten.

Das ist eine (große, aber) endliche Zahl.

$\Rightarrow$ Das Problem

• Eingabe: eine Lunar-Lockout-Konfiguration
• Frage: gibt es eine Zugfolge, die A nach a bewegt?

ist entscheidbar.

(D. h.: es gibt einen Algorithmus, der für jede Eingabe in endlicher Zeit die richtige Antwort ausgibt.)