Bachelorarbeit
PSPACE-Vollständigkeit von Rushhour und Reduktionen mit NCL
- Verfasser/in:
- Christian Komo
- Betreuer/in:
- Prof. Dr. André Schulz
- Status:
- abgeschlossen
- Jahr:
- 2016
- Beschreibung:
- Rushhour ist ein Logikpuzzle, bei dem es darum geht, auf einem Rechtecksgitter Gitter 1x2 und 1x3 Blöcke so zu navigieren, dass sich der auf dem Spielbrett simulierte "Stau" auflöst. Die Spielsteine können nur entlang ihrer Ausrichtung vertikal bzw. horizontal verschoben werden. Von diesem Problem ist bekannt, dass es PSPACE-vollständig ist. Für die Reduktion wird von Nondeterministic-Constrained Logic (NCL) reduziert - ein Problem(Framework) das sich für viele Rekonfigurations- und Spielprobleme nutzen lässt. Stellen Sie das NCL Framework vor (inkl. Beweisskizzen) und erklären Sie die Reduktion auf Rushhour. Versuchen Sie dann die PSPACE-Vollständigkeit von Rushhour-Varianten zu beweisen. Solche Varianten können andere Spielsteine oder andere Regeln zulassen.
Beschreibung:
Rushhour ist ein Logikpuzzle, bei dem es darum geht, auf einem Rechtecksgitter Gitter 1x2 und 1x3 Blöcke so zu navigieren, dass sich der auf dem Spielbrett simulierte "Stau" auflöst. Die Spielsteine können nur entlang ihrer Ausrichtung vertikal bzw. horizontal verschoben werden. Von diesem Problem ist bekannt, dass es PSPACE-vollständig ist. Für die Reduktion wird von Nondeterministic-Constrained Logic (NCL) reduziert - ein Problem(Framework) das sich für viele Rekonfigurations- und Spielprobleme nutzen lässt. Stellen Sie das NCL Framework vor (inkl. Beweisskizzen) und erklären Sie die Reduktion auf Rushhour. Versuchen Sie dann die PSPACE-Vollständigkeit von Rushhour-Varianten zu beweisen. Solche Varianten können andere Spielsteine oder andere Regeln zulassen.
