Der Startpunkt bezeichnet wie üblich bei Rätselcaches nur einen beliebigen Punkt in der Nähe des Caches, ist ansonsten aber nicht relevant.
Der Geocacher A. Nonymous (Name frei erfunden :-)) wohnt in Schmidham bei Bad Griesbach in Niederbayern. Er hat sich vorgenommen, im Rahmen einer Cachingtour durch einige Orte bisher noch nicht von ihm gefundene Caches zu suchen. Da A. Nonymous umweltbewusst lebt, möchte möglichst wenige Kilometer mit seinem Cachemobil zurücklegen und will daher seine Cachingtour folgendermaßen durchführen:
- Wenn er einen Ort anfährt, parkt er zentral und sucht die in der Nähe befindlichen Caches zu Fuß auf.
- Er möchte von seinem Heimatort aus alle Orte in derjenigen Reihenfolge anfahren, so dass er, wenn er nach der Cachingtour wieder zu seinem Heimatort zurückkehrt, möglichst wenige Kilometer mit seinem Cachemobil zurückgelegt hat.
Im Rahmen der geplanten Cachingtour will A. Nonymous folgende Orte besuchen:
- 1. Fürstenzell
- 2. Jägerwirth
- 3. Bad Höhenstadt
- 4. Neuburg a. Inn
- 5. Ruhstorf
- 6. Pocking
- 7. Bad Griesbach
- 8. Ortenburg
- 9. Aldersbach
- 10. Seestetten
- 11. Bad Birnbach
Die für die Fahrt mit dem Cachemobil relevanten Entfernungen zwischen diesen Orten sowie dem Heimatort (Nr. 0) sind wie folgt:
|
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
| 0 |
|
7 |
12 |
6 |
20 |
9 |
11 |
6 |
9 |
23 |
19 |
16 |
| 1 |
|
|
5 |
3 |
13 |
13 |
18 |
14 |
10 |
25 |
12 |
24 |
| 2 |
|
|
|
8 |
16 |
18 |
22 |
18 |
7 |
20 |
8 |
26 |
| 3 |
|
|
|
|
14 |
9 |
13 |
13 |
10 |
24 |
15 |
22 |
| 4 |
|
|
|
|
|
13 |
18 |
27 |
23 |
38 |
21 |
34 |
| 5 |
|
|
|
|
|
|
7 |
14 |
18 |
33 |
32 |
21 |
| 6 |
|
|
|
|
|
|
|
16 |
20 |
34 |
30 |
20 |
| 7 |
|
|
|
|
|
|
|
|
12 |
21 |
23 |
10 |
| 8 |
|
|
|
|
|
|
|
|
|
15 |
12 |
20 |
| 9 |
|
|
|
|
|
|
|
|
|
|
19 |
19 |
| 10 |
|
|
|
|
|
|
|
|
|
|
|
31 |
| 11 |
|
|
|
|
|
|
|
|
|
|
|
|
(Da die Entfernung zwischen Ort X und Ort Y unabhängig davon ist, ob man von X nach Y oder von Y nach X fährt, sind die Werte auch nur einmal in der Tabelle angegeben.)
Gesucht ist nun also eine Folge der Ortsnummern (beginnend mit Nr. 0 und endend mit Nr. 0), die diese Bedingungen erfüllt:
- jeder Ort wird einmal besucht (Tour-Eigenschaft) und
- die Gesamtlänge der Tour ist minimal unter den Längen aller möglichen Touren (Optimalitäts-Eigenschaft).
| Start |
A |
B |
C |
D |
E |
F |
G |
H |
J |
K |
L |
Ende |
| 0 |
|
|
|
|
|
|
|
|
|
|
|
0 |
Beispiel: Eine Tour wäre etwa
| Start |
A |
B |
C |
D |
E |
F |
G |
H |
J |
K |
L |
Ende |
| 0 |
3 |
1 |
2 |
8 |
7 |
11 |
9 |
10 |
4 |
5 |
6 |
0 |
mit einer Länge von 133 km. Aber es gibt noch kürzere Touren ...
Es gibt genau zwei optimale Touren. Verwendet diejenige, bei der als erstes der weiter westlich liegende Ort angefahren wird. Ihr erhaltet dann gemäß obiger Tabelle Werte für die Zahlen A, ..., L. Daraus könnt ihr dann die Koordinaten der Dose folgendermaßen berechnen:
N 48° 32. (22*A + B*D + 6*F + 5*K - C)
E 13° (D+E+G+H). (A*D + 9*E + C*K + 17*L - G)
Die Dose selber ist ein Drive-In!
Lösung prüfen: geochecker.com