Wegfindung (sehr einfach)

Optimizer: Lern lesen.

Bye, TGGC

*plonk*

Ja, ich habe die Anzahl der überquerten Kästchen gemeint.
Sorry wenn ich mich etwas missverständlich ausgedrückt habe!

Andreas XXL

Wenn ihr schon auf Dijkstra kommt und MisterX die Anzahl der Kästchen meint, dann wäre dies eine gute Vorhersage des kützesten möglichen Weges um daraus A* zu machen! (oder liege ich falsch) Das würde dann auch mit Hindernissen funktionieren.

Wenn das eine UNI Aufgabe ist, dann könnte genau das gemeint sein!

Da ich auch schon einmal vorhatte A* selbst zu proggen, habe ich dazu eine Frage.
Was meint ihr mit max(a-d, b-e).

(a,b) und (d,e) sind doch zwei vorgegebene Punkte in 2d in diesen "Kästchenkoordinaten".
Wie ist das denn mit dem max gemeint?

Wenn ich z.B von (2,2) nach (5,3) gwhen will, ist ein kürzester Weg:

(2,2) -> (3,2) -> (4,3) -> (5,3)
Kürzester Weg hat Länge 3 (wenn der Startpunkt nicht zählt)

wobei der Weg von (3,2) -> (4,3) ein Diagonaler ist.

Könnt ihr mir eure Rechnung mal an dem Beispiel demmonstrieren, denn ich steh irgendwie auf'm Schlauch!

Solange der Graph dicht ist, die kantengewichte zu jeden Knoten gleich sind und es absolute keine Hindernisses gibt, sind DijkstraSP oder A* ineffektiv.

findShortestPath(Point sp, Point ep)
  currentPos <- sp
  Let path be an array of points
  i <- 0
  while sp != ep do
     if currentPos.x != ep.x then
            currentPos.x <- currentPos.x + 1
     fi
     if currenntPos.y != ep.y then
            currentPos.y <- currentPos.y + 1
     fi
     path[i] <- currentPos
     i <- i+1
   od
   return path

O(n)
n...Länge des gefunden Pfades.

Cu

Andreas XXL

Da hast du mich missverstanden.
A* braucht eine Vorhersagefunktion, die sehr schnell die Länge des kürzesten Weges vorraussacht, wenn es keine Hindernisse gibt. A* selbst berechnet dann einen Weg, bei dem es Hindernisse geben kann.

Ich wollte den Alhgorithmus, nach dem ich gefragt habe als Vorhersagefunktion für den A* Algoritmus nehmen.

Gibt es eine Direkte Funktion, die von einem Punkt (a,b) zu einem 2. Punkt (c,d) den Weg(in "Kästchen") berechnet, wenn es keine Hindernisse gibt und diagonal vertikal und horizontal erlaubt ist.

Dieser Algorithmus muss als Vorhersagefunktion sehr schnell sein!
Die Antwort hierzu habe ich immer noch nicht verstanden!

Der von dir gezeigte Algoritmus muss den Weg entlanggehen und berechnet die Entfernung nicht direkt!

Andreas XXL schrieb:

Da hast du mich missverstanden.
A* braucht eine Vorhersagefunktion, die sehr schnell die Länge des kürzesten Weges vorraussacht, wenn es keine Hindernisse gibt. A* selbst berechnet dann einen Weg, bei dem es Hindernisse geben kann.

Die Heuristik muss nicht die Luftlinie sein. Es können auch vorberechnete Werte oder alles mögliche sein, es muss nur ungefähr stimmen und möglichst nicht unterschätzen.

Gibt es eine Direkte Funktion, die von einem Punkt (a,b) zu einem 2. Punkt (c,d) den Weg(in "Kästchen") berechnet, wenn es keine Hindernisse gibt und diagonal vertikal und horizontal erlaubt ist.

Ähm genau das wollte der Thread-Ersteller doch auch und die Lösung wurde auch (von mir) schon genannt.[/quote]

Das Ziel ist es einen Weg vom Start zum Ziel zu berechnen. Erlaubt sind horizontal vertikal und diagonales gehen. Es gibt KEINE Hindernisse.
Ich bin nur an der Länge des kürzesten Weges interessiert.

So das ist die Frage. Es heisst misterx will einen weg finden und nicht die distanz
zwischen zwei kästchen.
weg ist ein satz von kästchen, nicht mehr, nicht weniger.

schätzfunktion:
eucl. Distanz (kartesisches Kooridnaten System)
orthodrom -> weltkugel
cu

grenouille unreg schrieb:

[...]
Ich bin nur an der Länge des kürzesten Weges interessiert.

So das ist die Frage. Es heisst misterx will einen weg finden und nicht die distanz

Lern lesen.

Bye, TGGC

Oh sorry,
somit ist mein Lösung fürn arsch :-).

@tgcc
lern du erstmal respekt vor deinen mitmenschen zu haben.
leider hab ich am tag nicht die zeit mich auf 100 foren beiträge zu konzentrieren.
aber naja viel spass noch auf arbeit.

TGGC

grenouille_unreg schrieb:

@tgcc
lern du erstmal respekt vor deinen mitmenschen zu haben.

Hab ich schon.

Bye, TGGC

Jester

Optimizer schrieb:

Die Heuristik muss nicht die Luftlinie sein. Es können auch vorberechnete Werte oder alles mögliche sein, es muss nur ungefähr stimmen und möglichst nicht unterschätzen.

Unterschätzen ist das kleinere Problem. Wenn sie aber überschätzt, dann ist nicht mehr gesagt, daß Du den kürzesten Weg findest.

Also: auf keinen Fall überschätzen. Und um so weniger unterschätzt wird, umso schneller ist die Suche.

Ähm richtig, ich wollte es umgekehrt sagen.

TGGC

Wobei es natürlich genial wäre auch eine Funktion zu haben, die eine möglichst gute obere Schranke für den kürzesten Weg abgibt.

Bye, TGGC

Follow the mighty ant.

TGGC schrieb:

Wobei es natürlich genial wäre auch eine Funktion zu haben, die eine möglichst gute obere Schranke für den kürzesten Weg abgibt.

Bye, TGGC

Tja, bei n * n Knoten n^2 und jeden Knoten gehen(ist natürlich nicht die beste Abschätzung)

TGGC

Das ist im Allgemeinen keine gültige obere Schranke. Es gibt auch unendlich lange Wege.

Bye. TGGC

Ja Theoretisch, aber praktisch wirst du keine Kreise einbauen!

Und Kreise sind nötig um bei endlich vielelen Knoten einen unendlich langen weg zu erzeugen. Außerdem ist dann auch die Summe der "Kosten" der Kanten unendlich, was ja nicht besonder wirlichkeitsnah ist.

Und außerdem verbietet A* und Dijkstra Kreise! Also ist es ne obere Schranke!

Erstens braucht man eine möglichst günstige obere Schranke, also einen Wert, der den tatsächlichen Weg nicht wahnsinnig (am besten gar nicht) überschätzt, denn die Qualität des gefundenen Weges leidet darunter. Man kann auch leicht einsehen, dass diese Methode meistens überschätzt. Der Weg, den du so bekommst, ist also unbrauchbar.
Zweitens sind Kreiswege keineswegs "verboten", sie werden von den Algorithmen nur nicht erstellt. Wie du aber deine Heuristik so aufbaust, ist u.U. nicht trivial. Nicht zuletzt ist ein Weg auch unendlich lang, wenn es keine Verbindung gibt.