Ankündigung

Einklappen
Keine Ankündigung bisher.

kürzester Weg im Gitter

Einklappen

Neue Werbung 2019

Einklappen
X
  • Filter
  • Zeit
  • Anzeigen
Alles löschen
neue Beiträge

  • kürzester Weg im Gitter

    Hi Leute,

    Ich zerbreche mir schon den ganzen abend den Kopf über folgendes Problem:

    ich habe ein Gitter (zur Anschaung sage ich mal ein Schachbrett mit 9*9 feldern).

    - - : - - - : - -
    - - - - - - - - -
    - : - - - : - - -
    - - - - - - - - :

    Auf diesem Schachbrett stehen nun Figuren. hier durch ':' makiert.
    Nun gehe ich von der ersten Figur aus (koordinate 1;3).

    Wie bekomme ich nun raus welche Figur den kürzesten Abstand zu der Ausgangsfigur hat, wenn die Figuren waagerecht, senkrecht und diagonal zwischen den feldern laufen können.

    In meinem Beispiel logischerweise die Figur auf 3;2

    Wenn jemand einen Forschlag hätte oder vtl einen Algorithmus für derartige Probleme kennt würde mich das sehr freuen.

  • #2
    Du musst zuerst ne Variable setzen, wo du den kürzesten gefundenen Weg speicherst. Dann musst du halt alle möglichen Richtungen ablaufen und sobald du auf eine Figur triffst, vergleichst du die Distanz mit dem Wert in der Variable. Wenn der Wert grösser ist, versuchst du eine andere Richtung, ansonsten speicherst du den neuen Wert in die Variable und versuchst die nächste Richtung, bis du alle durch hast.

    Oder du liest alle Figuren mit ihren Positionen aus und wenn du dann eine Figur als Startpunkt festgelegt hast, probierst du alle anderen Figuren durch und schaust zuerst, ob sie überhaupt waagerecht, senkrecht oder diagonal zur Startfigur ist und wenn ja, kannst du die Distanz ja einfach aus den Koordinaten berechnen. Der Rest mit der Variable ist dann gleich wie beim ersten Ansatz.

    Kommentar


    • #3
      Wenn Du in jedem Durchlauf die bekannten Pfade um jeweils einen Schritt (jeweils in alle möglichen Richtungen) erweiterst, ist der erste Pfad, mit dem Du das Ziel erreichst auch der kürzeste; es gibt keinen kürzeren Pfad.
      Breitensuche - Wikipedia

      Kommentar


      • #4
        thx für die schnelle Antwort, da kann ich doch schonmal was mit anfangen.

        Kommentar

        Lädt...
        X