Das Rush Hour Puzzle
Klaus Reinhardt
Universität Tübingen
Übersicht:
Das Puzzle
Komplexitätsklassen
Fix Parameter Komplexität
Resultate
von H. Fernau, T. Hagerup, N. Nishimura, P. Ragde, K. Reinhardt
Weitere Verallgemeinerungen und Probleme
>
Das Puzzle:
Viele Applets in Internet zu finden:
Erfinder des Spiels: Nob Yoshigahara
>
Gegeben: Autos auf diskreten Gitterpositionen (Parkplatz):
Frage: Kann das rote Auto entfernt werden? Wieviele Züge?
Wie komplex ist das Problem?
>
Komplexitätsklassen
Komplexitätsklassen enthalten die Probleme für die der Zeit- bzw. Platzbedarf eines Algorithmus durch eine Funktion von der Größe der gegebenen Probleminstanz beschränkt ist.
EXPTIME
: exponentielle Zeit
enthält
PSPACE
: polynomieller Platz
enthält
P
: polynomielle Zeit (gilt als effizient)
Offenes Problem
: Gibt es ein Problem in
PSPACE
, das nicht in
P
ist?
Gibt es ein Problem in
EXPTIME
, das nicht in
PSPACE
ist?
>
Vollständigkeit
Ein Problem in
PSPACE
heißt
PSPACE-vollständig
wenn sich jedes andere Problem in
PSPACE
in polynomieller Zeit darauf reduzieren lässt.
EXPTIME-vollständig
analog.
Beispiele für
EXPTIME-vollständige
Probleme
: Schach, Go, Dame
Beispiele für
PSPACE-vollständige
Probleme
: Amazons, Othello (Reversi), Sokoban,
Rush Hour
(gezeigt von Flake, Baum 2001)
>
Fix Parameter Komplexiät
Idee:
Man beschränkt sich auf Probleminstanzen, bei denen ein Parameter
k
klein ist.
Definition (Downey und Fellows):
Ein Problem ist in
FPT
(fixed parameter tractable), wenn Instanzen der Größe
n
in der Zeit
O(f(
k
)
p(n)
)
gelöst werden können für ein
Polynom
p
.
Resultat (H. Fernau, T. Hagerup, N. Nishimura, P. Ragde, K. Reinhardt):
Das verallgemeinerte Rush Hour Problem ist in
FPT
mit Laufzeit
O((2
k
3
)
2
k
p(n)
)
für
k
= Anzahl der Autos und
2
O(
b
2
3
b
)
p(n)
für
b
= Anzahl der Bewegungen.
>
Verallgemeinerte Definition
Gegeben:
Autos als axenparallele Rechtecke
auf beliebigen Positionen in der Ebene (
R
2
)
mit beliebigen Längen und Breiten (in
R
)
mit einem Richungsvektor in
{(1,0),(0,1),(0,0)}
Gesucht:
Eine Folge von legalen Bewegungen, die ein (oder jedes) Auto auf eines seiner Zielpositionen bringt.
>
Problem:
Unendlich viele Positionen für ein Auto möglich.
Idee:
Identifiziere bestimmte Positionen für jedes Auto, die genügen um jede erfolgreiche Bewegungsequenz durch eine diskretisierte Bewegungsequenz zu ersetzen.
Erster Versuch:
Verlängere jede Bewegungen bis zum Erreichen der nächsten Spur oder eines Autos.
Dies führt zu exponentiell vielen Positionen
>
Besser:
Verlängere jede Bewegungen soweit bis ein Auto an die Spur eines anderen geschoben wird (
< k
Einzelbewegungen).
Die Position eines Autos hängt nun ab von
- dem "schiebenden" Auto (
<
k
Möglichkeiten)
,
- dem Auto, das den Stop verursachte (
<
k
Möglichkeiten)
und
- der Spur oder Zielposition, die den Stop verursachte (
<2
k
Mögl.) .
Damit sind
< 2
k
3
diskretisierte Positionen pro Auto zu berücksichtigen.
>
Dies ergibt
<(2
k
3
)
2
k
diskretisierte Konfigurationen und damit eine Laufzeit von
O((2
k
3
)
2
k
p(n)
)
.
Führen
t
Bewegungen zum Ziel, so auch
<
k
t
diskretisierte Bewegungen.
>
Parameter:
b
= Anzahl der Bewegungen.
Höchstens
3
b
Autos sind relevant.
Es sind
2
O(
b
2
)
diskretisierte Positionen pro Auto zu berücksichtigen.
Dies ergibt eine Laufzeit von
2
O(
b
2
3
b
)
p(n)
.
>
Weitere Verallgemeinerungen
Der Ansatz für den Parameter
b
= Anzahl der Bewegungen lässt sich auf folgende Verallgemeinerungen übertragen:
Autos als konvexe Polygone
>
Autos als allgemeine Polygone
Beliebige Richtungen
>
Offene Probleme
Gibt es für die obigen Verallgemeinerungen auch einen Fix Parameter algorithmus für
k
= Anzahl der Autos?
Weitere mögliche Verallgemeinerungen:
Autos können sich entlang individuellen gekrümmten Linien bewegen.
Simultane Bewegungen mit individuellen Geschwindigkeiten.
