Algorithmus gesucht



  • Ich bin auf der Suche nach einem Algorithmus, der eine Map (als Array vorliegend), danach absucht, ob der Spieler alle Blöcke erreichen kann , dabei aber nur einmal auf jeden Block gehen darf.

    Hat da jemand eine Idee? 😃





  • Es bringt mich auf jeden Fall schonmal weiter , aber das , was ich suche ist es noch nicht ganz , da der Hamiltonkreis-Algorithmus nur auf "1-Block-breiten"-Maps funktioniert, also auf zb sowas:

    S : Spieler
    + : Nicht überquerbare Blöcke
    ' ' : Bewegungsraum

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

    Ich mache am besten mal ein Bsp meiner Map:

    S : Spieler
    + : Nicht überquerbare blöcke
    ' ' : Bewegungsraum

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


  • Nein das Hamiltonkreisproblem ist nicht auf 1-Block breite Pfade beschränkt. Jedes freie Feld ist ein Knoten im Graph, bzw. nicht begehbare Felder sind nicht im Graph. Die Kanten verbinden ein Feld mit allen freien Nachbarfeldern. Aber ich nehme an du möchtest keine geschlossenen Pfade oder? Brauchst du nur die Entscheidung Ja/Nein ist möglich oder auch mindstens einen Pfad wenn es möglich ist?



  • Er braucht den Pfad, genauer, in welche Himmelsrichtungen man von der Startposition aus gehen muss. Der Pfad muss nicht geschlossen sein.



  • Mir sind gerade noch passende Transformationen eingefallen wenn du nur Algorithmen für das Hamiltonkreisproblem findest aber der Pfad wie gefordert offen sein soll. Du fügst einen zusätzlichen Knoten in deinen Graph ein, der mit allen anderen Knoten verbunden ist. Über diesen Zusatzknoten wird dann der Pfad geschlossen. Wenn der Startpunkt fest ist dann fügst du keinen Knoten hinzu sondern verbindest alle anderen Knoten mit dem Startknoten.



  • 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? 🙂



  • 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.



  • 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.



  • 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.



  • 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.





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



  • 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?



  • 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.


Log in to reply