Maximale Tagesstrecke minimieren |
mseye
Grünschnabel
Dabei seit: 13.07.2015
Beiträge: 2
|
|
Maximale Tagesstrecke minimieren |
|
Hallo zusammen,
ich habe eine Programmieraufgabe bekommen, die angeblich in 3-4 Stunden lösbar sein soll:
Für eine Wanderung sind die Etappen (also z.B. die Strecken zwischen zwei Hütten) vorgegeben und die Anzahl der Tage, in der die Gesamtwanderung durchgeführt werden soll. Die Hütten sollen nun so gewählt werden, dass die maximal Tagesstrecke minimal wird.
Ein Beispiel: Die Distanzen zwischen den Hütten betragen:
Start - 11 km - Hütte1 - 16 km - Hütte2 - 5 km - Hütte3 - 5 km - Hütte4 - 12 km - Hütte5 - 10 km - Ziel
Die Gesamtstrecke soll in 3 Tagen geschafft werden. Dann wäre die optimale Einteilung:
1. Tag: Start bis Hütte1, 11 km
2. Tag: Hütte1 bis Hütte4, 26 km
3. Tag: Hütte4 bis Ziel, 22 km
Mir fällt als Lösung für dieses Problem nur die Brut-Force-Methode ein, also einfach alle Möglichkeiten durchprobieren. Das ist aber natürlich extrem ineffizient. Gibt es für das Problem eine bessere Lösung? Bzw. ist das Problem in der Informatik unter einem anderen Namen bekannt, unter dem ich Literatur dazu finde?
Vielen Dank für eure Hilfe!
Schöne Grüße
mseye
|
|
13.07.2015 11:00 |
|
|
mseye
Grünschnabel
Dabei seit: 13.07.2015
Beiträge: 2
|
|
Hallo eulerscheZahl,
danke für deine Antwort und die Bestätigung, dass es wohl keine bessere Methode gibt. An ein paar kleine Optimierungen hatte ich auch schon gedacht.
Mit dem Ansatz, Strecken immer so zu kombinieren, dass sie möglichst nah am Durchschnitt liegen, ließe sich ein sehr netter und einfacher Greedy-Algorithmus bauen. Aber zumindest so wie ich mir den überlegt habe, würde der nicht für alle Beispiele das korrekte Ergebnis liefern. Und ich habe keinen Weg gefunden, ihn zu retten.
Aber als Optimierung für die Brute-Force-Methode ist das eine gute Idee, finde ich!
Schöne Grüße
mseye
|
|
14.07.2015 10:32 |
|
|
|
Ich habe noch eine andere Idee:
du legst eine zulässige maximale Tagesstrecke fest (als Startwert eignet sich der Durchschnitt) und versuchst die Strecke entsprechend aufzuteilen. Das geht in linearer Zeit.
Wenn du scheiterst, wird die maximale Strecke erhöht (z.B. verdoppelt). Sobald eine Aufteilung möglich ist, ermittelst du mit binärer Suche das Optimum.
__________________ Syntax Highlighting fürs Board (Link)
|
|
14.07.2015 22:53 |
|
|
|