1. Diese Seite verwendet Cookies. Wenn du dich weiterhin auf dieser Seite aufhältst, akzeptierst du unseren Einsatz von Cookies. Weitere Informationen

Optimalen Weg berechnen ohne A*?

Dieses Thema im Forum "Main Forum" wurde erstellt von Satana, 21. Dezember 2018.

  1. Satana

    Satana New Member

    Registriert seit:
    15. Dezember 2018
    Beiträge:
    13
    Zustimmungen:
    4
    Punkte für Erfolge:
    3
    Geschlecht:
    männlich
    Hey zusammen,

    ich habe eine "Sprachen"-unabhängige Frage zur Berechnung eines optimalen Weges zwischen Punkten.

    • Keine Hindernisse
    • Immer (auch diagonal) mit der Entfernung 1 zum nächsten Feld (2D-Koordinatensystem)
    • Es gibt einen Punkt, von dem man startet und zu dem man nach dem Besuch von x Punkten wieder zurück muss
    • Es gibt y Ziele, zu denen die Entfernung zum "zu Hause" bekannt ist
    • Die Entfernung zwischen den Zielen selber lässt sich auch berechnen
    • Es geht darum, möglichst wenig Entfernung zurückgelegt zu haben, um z der x Ziele abgelaufen und wieder "zu Hause" zu sein

    Ich habe verschiedene Ansätze und erhoffe mir einen Impuls in die richtige Richtung ;)...
    • A* wäre wahrscheinlich die beste Variante, ist aber auch recht komplex glaube ich, auch wenn ich Beispielcode in der Sprache finden kann und es ja keine Hindernisse gibt -> Da mit steigender Zahl z (abzulaufende Ziele) unwahrscheinlicher wird, dass das Ergebnis beständig ist und weiterhin passt, fühlt sich das zu komplex an, sich da reinzuarbeiten (bin eher nur Hobby-Programmierer)
    • Einfachste Lösung: Einfach immer von der aktuellen Position das Ziel ansteuern, das am nächsten dran ist -> kann echt schief gehen, wenn die Punkte schlecht liegen, da der Rückweg immens ist
      • Erweiterbar durch eine "Gewichtung" hin zum "zu Hause", die mit der Entfernung vom "zu Hause" steigt -> ist kein Optimum, der 1. Punkt ist vllt. genau in die falsche Richtung zu allen anderen Punkten
    • Ich iteriere jeden Schritt durch, also fange beim nähsten Punkt an und schaue von dem aus den nähsten Punkt an, etc. und baue das so, dass jede mögliche Bewegung versucht wurde und schaue dann, was den geringsten Distanzwert insgesamt hat -> bei steigender Zahl z der Ziele könnte das sehr lastaufwendig werden, auch wenn die Berechnungen an sich ja Pippifax sind
    • Einfache Lösung: Ich nehme die nähsten Punkte (z. B. Entfernung 1-3) und schaue in Tiefe 1 und 2 nach, was davon das nähste Ziel wäre und gehe dann in dem Wissen los, dass ich zumindest die nächsten 3 Punkte gut gewählt habe und überlasse den Rest dem Schicksal ^^ -> Berechnet auch den Rückweg nicht ein und bezieht halt nur wenige Punkte ein
    • ...

    Mir hilft es immer sehr, darüber zu sprechen / schreiben, vllt. habt ihr noch Ansätze, Feedback und/oder Impulse für mich, bevor ich mich in einer Lösung verstricke (ich hoffe, das Problem ist gut beschrieben^^).

    Zur Verdeutlichung eine kleine Skizze im Anhang.
     

    Anhänge:

    • Bild.png
      Bild.png
      Dateigröße:
      7,2 KB
      Aufrufe:
      5
    krusty gefällt das.
  2. krusty

    krusty Moderator Mitarbeiter Moderator

    Registriert seit:
    1. Juli 2017
    Beiträge:
    86
    Zustimmungen:
    33
    Punkte für Erfolge:
    18
    Geschlecht:
    männlich
    Ort:
    Wadiya
    Hmmm, ich hab leider nicht wirklich viel Zeit, um mich mit dem Problem zu beschäftigen.
    Falls du sehr viele Objekte hast, würde ich dir einen KD-Baum ans Herz legen, damit kannst du sehr schnell die "nächsten Nachbarn" finden.
    Generell suchst du ja immer drei Objekte, die du nacheinander abgrast. Du suchst also Cluster der Größe 3.
    Vlt mal K-Means anschauen?

    Sorry, dass ich dir nicht großartig helfen kannst.
    Lg Krusty
     

Diese Seite empfehlen

Die Seite wird geladen...