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

ist entscheidbar.

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



Johannes Waldmann 2007-01-23