Der kürzeste Weg |
20.10.2010, 10:54 | wegsucher | Auf diesen Beitrag antworten » |
Der kürzeste Weg 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?) |
||
20.10.2010, 10:56 | lgrizu | Auf diesen Beitrag antworten » |
RE: Der kürzeste Weg das ganze schaut nach manhatten-metrik aus. |
||
20.10.2010, 13:36 | sulo | Auf diesen Beitrag antworten » |
RE: Der kürzeste Weg Ist es vielleicht eine Geocaching-Aufgabe? |
|
Verwandte Themen
Die Beliebtesten » |
Die Größten » |
|
Die Neuesten » |