Wegfindung (sehr einfach)

Er wird wohl die Anzahl der zu überquerenden Kacheln meinen. Was einige sich hier aus den Fingern saugen, ist ja wohl leicht krass.

Ponto

Optimizer schrieb:

Er wird wohl die Anzahl der zu überquerenden Kacheln meinen. Was einige sich hier aus den Fingern saugen, ist ja wohl leicht krass.

Er hat nicht geschrieben was er meint. Meine Lösung berechnet, das was scrub beschrieben hat. Ich wüsste nicht, was daran krass ist.

TGGC

scrub schrieb:

mit diagonale wird wohl die eines einzelnen kästchens gemeint sein- satz des pytagoras also nur anwendbar, wenn vertikal- und horizontaldifferenz gleich sind. wenn das nicht gegeben ist, fängt man trotzdem damit an und addiert dann das letzte horizontale oder vertikale stück.

Ich sagte ja auch, das man Pythagoras nur für die Diagonale braucht...

Bye, TGGC

scrub

Optimizer schrieb:

Er wird wohl die Anzahl der zu überquerenden Kacheln meinen. Was einige sich hier aus den Fingern saugen, ist ja wohl leicht krass.

jo, hast recht; weils nicht dabeistand, habe ich instinktiv an die "normale" länge (also einfach in mm z.b.) gedacht. war natürlich käse, weil seine lösung natürlich völlig richtig für den fall ist, daß die einheit "kästchen" ist. dann scheint er das auch zu meinen.
dann ist auch pytagoras für die diagonale blödsinn.

TGGC

MisterX schrieb:

Erlaubt sind horizontal vertikal und diagonales gehen.
Ich bin nur an der Länge des kürzesten Weges interessiert.

Lernt lesen.

Bye, TGGC

scrub

ja, aber mit der einheit "kästchen" wirst du wohl nicht zurechtkommen, wenn du den satz des pytagoras verwendest. die gesuchte länge des kürzesten wegs ist also das maximum(horizontaldifferenz,vertikaldifferenz). also ist Optimizers vorschlag völlig richtig.

TGGC

Das ist keine Länge.

Bye, TGGC

Trotzdem war das gemeint, wie ich mit meiner Kristallkugel sehen konnte.

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.