Algorithmus gesucht

numbo

Das Programm soll ermitteln , ob es möglich ist, dass der Spieler von seiner Startposition aus, jedes andere Feld erreichen kann , ohne dabei 2 mal über dasselbe zu gehen.
Der Hamilton-Algo funktioniert so:

ALGORITHMUS eulerkreis:
    Übergabe: Graph, dargestellt mit einer Nachbarschaftstabelle
    kreisExistiert = True
    FÜR alle Knoten des Graphen:
        bestimme die Anzahl der Nachbarn des Knoten
        WENN diese Anzahl ungerade ist:
            kreisExistiert = False
    Rückgabe: kreisExistiert

Ein Beispiel, dass diese Methode bei mir nicht funktioniert:

+++++++ 
+S  + +
+     +
+++++++

Der Punkt unten rechts , hat 3 Nachbarn: Laut dem Algo ist es dem Spieler also nicht möglich alle Felder zu überqueren, ohne eins doppelt zu besuchen.Das heißt der Algo funtkioniert nur bei Karten, die "EinzelFeldWege" haben.

Hat noch jemand eine andere Idee?

SG1

Der Punkt unten rechts hat 2 Nachbarn: das Feld dadrüber und das Feld links davon. *edit* ausserdem verwechselst Du gerade Hamilton- und Eulerkreise.

Dein Algo ist für den Eulerkreis (steht auch oben drüber...) und nicht für den Hamiltonkreis. Der Hamiltonkreis ist ein deutlich schwierigeres Problem! Unabhängig gibt es in deinem Beispiel auch gar kein Pfad wie du suchst.

numbo

Ups, da war ich wohl zu schnell...
Zu dem Pfad: Der muss auch erstmal durch eine Routine erstellt werden.

Das bedeutet der Hamilton-Algo fällt raus...
Hat jemand noch eine Idee, wie man das lösen könnte?

sebi707 schrieb:

Unabhängig gibt es in deinem Beispiel auch gar kein Pfad wie du suchst.

OK ne gibts doch. Ich dachte da wäre vom Start aus nur ein Feld rechts bis zur Wand.

Wieso fällt der jetzt schon wieder aus? Wenn man an dem Pfad interessiert ist muss man den logischerweise konstruieren aber dafür findet man schon Code im Internet z.B. hier (habe ich nur auf die schnelle gefunden, keine Ahnung ob der was taugt). Der kann auch Pfade und nicht nur Kreise. Eventuell kann man den Code mal auf Neighbour-Lists statt Adjazenzmatrix umstellen. Bei deinem 2D Gitter ist das wohl sinnvoller.

5cript

Muss es effizient sein?
Ich würde es mit (speziellem) flood fill machen.

EDIT: nur einmal habe ich überlesen. -.- Ob das trotzdem geht? *grübel*

5cript schrieb:

Muss es effizient sein?
Ich würde es mit (speziellem) flood fill machen + dann über alles rüber gehen und prüfen.

EDIT: nur einmal habe ich überlesen. -.- Ob das trotzdem geht? *grübel*

Ich wollte schon gerade was sagen... Ich dachte auch erst das Problem wäre einfach aber die allgemeine Version davon ist NP-vollständig. Ich habe verschiedene Artikel gefunden die beweisen, dass das Problem auf speziellen Graphen (planar, kubisch) auch NP-vollständig ist. Ich gehe also mal davon aus, dass das Problem auf Rechteckgittern auch nicht gerade einfacher ist.

5cript

Ok Frage:

Soll geprüft werden ob jedes Feld für sich selbst, also einzeln, mit einem Pfad zum Startpunkt verbunden werden kann, oder ob es einen Pfad gibt, der über jedes Feld geht?

Mit jeweils der Einschränkung, dass jedes Feld nur einmal beschritten werden darf.
...Für ersteres ist diese Einschränkung ziemlich sinnlos oder?

Ja ok, dann ist es ein schwer lösbares, aber leicht überprüfbares Problem.

EDIT: In dem Fall wäre Backtracking die hirnlos Lösung.

sebi707 schrieb:

Ich gehe also mal davon aus, dass das Problem auf Rechteckgittern auch nicht gerade einfacher ist.

Korrekt. Siehe Itai et al.: Hamilton Paths in Grid Graphs.
https://www.google.de/url?sa=t&rct=j&q=&esrc=s&source=web&cd=1&ved=0CCAQFjAAahUKEwjllLTCnbHIAhUSmYgKHZxnDpg&url=http%3A%2F%2Fwww.cs.technion.ac.il%2F~itai%2Fpublications%2FAlgorithms%2FHamilton-paths.pdf&usg=AFQjCNE7MMmyG2_1LzOeqs8YcUHoDJa4fA&bvm=bv.104615367,d.eXY&cad=rja

Jester

Für solid grid graphs (keine löcher) gibt es wohl einen polynomiellen Algorithmus. Zumindest die bisher gezeigten Beispiele erfüllen das.

numbo

Es soll geprüft werden, ob der Spieler von seiner Startposition aus JEDEN block erreichen kann (egal auf welchem Weg), ohne dabei einen Block doppelt zu überqueren.

Für solid grid graphs (keine löcher) gibt es wohl einen polynomiellen Algorithmus.

Meinst du mit Löchern sowas? :

+++++++++++
+S        +
+   +     +
+         +
+++++++++++

Das enthalten die Karten sehrwohl.

Hast du dir jetzt schonmal einen Algorithmus geschnappt und geguckt wie weit du damit kommst? Wie groß sind deine Karten maximal? Wie schnell soll die Berechnung fertig sein?

numbo

Wie schnell die Berechnung geht ist relativ egal.

Aber Algorithmen finde ich keine brauchbaren dazu(Hab ca. ne Stunde gesucht).

Die größe der Karten ist auf 100x100 begrenzt(Dazwischen sind sie aber variabel groß, also zb. 40x45 oder 78x64).

Was ich schon habe:
-Begehbare Felder zählen
-Map aus .txt Datei einlesen
-Eine Flood Fill Methode, um zu prüfen, ob alle Felder zusammen hängen

Was ich noch brauche:
-Einen Pfad Generator , der auf keinen Block 2 mal geht, und alle möglichen Wege der Reihe nach durchgeht.

numbo schrieb:

Wie schnell die Berechnung geht ist relativ egal.

Dann mach Backtracking. Gibt ja nur ca. N! Möglichkeiten zum testen. Bei N=100*100 und wenn du 10^12 Pfade pro Sekunde testest dauert es auch nur 2,8*10^35629 mal das aktuelle Alter des Universums und du bist auch schon fertig. Ich denke mit "relativ egal" meinst du irgendwas in der Größenordnung von maximal ein paar Tagen. Da ich noch keinen der Algorithmen getestet habe kann ich dir noch nicht sagen ob damit ein 100x100 Feld in absehbarer Zeit machbar ist. Da du ja keinen Algorithmus zu finden scheinst: Ich hatte hier doch schon einen verlinkt. Haste dir den mal angeschaut?

numbo

Haste dir den mal angeschaut?

Ja habe ich, werde daraus aber nicht schlau...

Gibts für das auch ein Codebeispiel?
Oder einen anderen Ansatz?

Ich kann ja nicht der einzige sein , der sowas versucht...

Ja gibt es. Steht dort doch auch:

The algorithm is implemented in C++ and the program is demonstrated with several examples [Download].

Ich habe gerade mal selbst mit dem Algorithmus rumgespielt. So ganz überzeugt bin ich davon noch nicht. In meinen zufälligen generierten Maps findet er irgendwie nur Pfade wenn recht wenig gesperrte Felder vorhanden sind. Kann so natürlich stimmen aber ich würde es gerne mal mit realistischeren Maps testen. Kannst du mal einige der Maps hochladen wenn die nicht geheim sind?

win8789

das klingt aber alles sehr nach der ersten Aufgabe vom bundeswettbewerb-informatik

ist das überhaupt erlaubt? Immerhin soll man das Ganze nach Möglichkeit selbst lösen.

win8789 schrieb:

das klingt aber alles sehr nach der ersten Aufgabe vom bundeswettbewerb-informatik

ist das überhaupt erlaubt? Immerhin soll man das Ganze nach Möglichkeit selbst lösen.

Danke für den Hinweis. Ich werde also schonmal nicht meinen Code hier posten. Allerdings spricht der TO von 100x100 Feldern und die bwinf Beispiele sind alle sehr klein. Die müsste man auch schnell mit Backtracking lösen können.