Der kürzeste Weg

Neue Frage »

wegsucher Auf diesen Beitrag antworten »
Der kürzeste Weg
Meine Frage:
Ich muß am Friedhof (20 Reihen, je 20 Gräber nebeneinander, Abstand in der Reihe = 1.5m, Reihenabstand = 2.5m) mehrere ausgewählte Gräber besuchen. Wie kann ich den kürzesten Weg errechnen? Der Anfangspunkt liegt fest.

Meine Ideen:
Ich bezeichne die Gräber der ersten Reihe mit 01/01 bis 01/20 die zweite Reihe mit 02/01 bis 02/20 usw. Der Abstand zwischen zwei Gräbern lässt sich also mit: (Differenz der ersten Zahlenhälften mal 2.5 plus Differenz der zweiten Zahlenhälften mal 1.5) errechnen. (Man geht immer rechtwinkelig, sonst müsste man über die Gräber steigen.)
Ich habe mir ein einfaches Programm gebastelt, das -ausgehend vom festgelegten Ausgangspunkt- die nähesten drei Gräber aussucht (Schritt 1) und von denen jeweils wieder die drei nähesten berechnet (Schritt 2). Dorthin, wo die Summe der Schritte 1 und 2 am kleinsten ist, geht der Weg. Ich habe also wieder einen neuen Ausgangspunkt und mache wieder die 2 bekannten Schritte, usw.
Das Ganze funktioniert in Ansätzen, allerdings bleiben immer wieder einige (am Rand liegende) Gräber zurück, die am Ende mit extrem langen Wegen nachgeholt werden müssen. Also: Kein Erfolg!
Ich habe auch schon versucht, einen dritten Schritt zu setzen, aber erstens bin ich vorläufig irgendwie gescheitert und zweitens wird das mein Problem nicht grundsätzlich lösen können. Muß man wirklich alle in Frage kommenden Möglichkeiten durchrechnen? Und wie macht man das am besten? (ohne Großrechner?)
lgrizu Auf diesen Beitrag antworten »
RE: Der kürzeste Weg
das ganze schaut nach manhatten-metrik aus.
sulo Auf diesen Beitrag antworten »
RE: Der kürzeste Weg
Ist es vielleicht eine Geocaching-Aufgabe? verwirrt
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »