Wegfindung (sehr einfach)

Hallo,

ich habe ein Feld gegeben (sieht aus wie Rechenkästchenpapier).
Nun Bekomme ich ein Feld gegeben z.b (4,7) welches der Startpunkt ist und ein Feld z.b (9,13) welches das Ziel ist.

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.

Wenn das Diagonale nicht erlaubt wäre, wäre es ja kein Problem:
von (a,b) zu (d,e) währe dann |a-d| + |b-e| (stimmt doch oder?)

Aber wie berechne ich den kürzesten Weg mit erlaubter Diagonale?

MfG
MisterX

max(a-d, b-e)

TGGC

Optimizer schrieb:

max(a-d, b-e)

Unsinn.

Diagonale geht ganz einfach mit Satz des Pythagoras, passt doch bitte mal in der Schule auf...

Bye, TGGC

Dijkstra

Bye, TGGC

Ponto

Seien die beiden Punkte (x1, y1) und (x2, y2).

Falls |x1-x2| > |y1-y2|, dann
D = |x1-x2| + (sqrt(2)-1)|y1-y2|
ansonsten
D = |y1-y2| + (sqrt(2)-1)|x1-x2|

TGGC

MisterX schrieb:

Es gibt KEINE Hindernisse.
Ich bin nur an der Länge des kürzesten Weges interessiert.

Lernt lesen.

Bye, TGGC

scrub

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.

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