ED209
Anmeldungsdatum: 30.05.2005
Beiträge: 122
|
 Verfasst am: 05. Sep 2005 14:51 Titel: Sokoban und Komplexitaet |
 |
|
Hi
In den letzten Tagen habe ich Sokoban wiederentdeckt. Da das ganze Kistenschieben auf die Dauer doch etwas eintoenig wird hab ich mir Gedanken ueber ein Programm gemacht, das die Level automatisch loest und frage mich wie Komplex dieses Problem wohl ist.
Konkret: Ich habe ein Programm (oder eine Turingmaschine) und uebergebe ein Level mit Angaben ueber Kisten, Waende, Zielfelder und Startposition und will als Anwort eine Loesung fuer das Problem.
Da hier ein paar sind die sich fuer TheoInf interessieren will ich mal gucken ob sich das Problem nicht loesen laesst, ich weiss nicht ob das schonmal wo behandelt wurde.
Bisher konnte ich noch keine Komplexitaetsklasse ausschliessen und fuer mich ist noch alles offen :)
Bisher hatte ich folgende Ueberlegungen:
Das Problem die kuerzeste Loesung zu finden und zu ueberpruefen ob ein Level in s Schritten loesbar ist, ist gleichkomplex, wenn die Anzahl der noetigen Zuege nur polynomial waechst.
Beweis:
a.) Wenn ich die kuerzeste Loesung habe kann ich leicht vergleichen ob die Zahl der Schritte kleinergleich s ist.
b.) Wenn eine Maschine M hab, die sagen kann ob ein Level s Schritten loesbar ist kann ich von 1 solange raufzaehlen bis ich ein "ja" als antwort bekomme.
Anschliessend kann ich testweise einen Bewegung nach Oben (nach Rechts/nach links) machen und gucken ob das level in s-1 Schritten loesbar ist.
Dafuer brauch ich maximal 4*s*(Zeit von M).
Liegt M in P liegt auch die neue Maschine in P, liegt sie in NP liegt die neue Maschine auch in NP.
Untergrenze fuer die Zeitkomplexitaet ist die laenge der Ausgabe, also die Anzahl der Schritte.
Das ist wohl eindeutig, halte ich aber fuer wichtig :) Bisher hab ich noch keine Beschraenkung fuer die Anzahl der benoetigten Schritte gefunden, oder einen beweis dafuer das sie Exponentiell wachsen kann.
Gruss,
ED209
_________________
+++++++++++++[>++++>+<<-]>.--.>---. |
|
FAQ
Suchen
Mitgliederliste
Benutzergruppen
Registrieren
Profil
Einloggen, um private Nachrichten zu lesen
Login
