Tagesetappen einer Rundreise

[hauer85]

Hallo!
Wollte fragen ob wer einen Ansatz für folgendes Problem hat:

Für eine längere Rundreise stehen schon die Strecken, die Dauer, aber noch nicht die Übernachtungsmöglichkeiten fest. Diese sollen so gewählt werden, dass die längste Tagesetappe möglichst kurz ist.

Beispiel: Bei Distanzen 11, 16, 5, 5, 12, 10 die in 3 Tagen zurückgelegt werden sollen, ist die richtige Antwort 26, mit den Tagesetappen 11, 16+5+5, 12+10

[Schorsch]

Ich würde eine Adjazenzliste erstellen mit jeweils der definierten Strecke. Knoten sind die Übernachtungsmöglichkeiten.

Das Gewicht der Strecken würde ich dynamisch berechnen lassen und zwar nach Stunden die benötigt werden um die Strecke zu fahren. (max möglichen km/h / Strecke).

Mit dem Algo von Djikstra kannst du dann nach dem passenden Weg suchen.

Anstatt dann nach der schnellsten Strecke zu suchen suchst du im ersten Schritt nach dem Hotel das max 1/3 der Gesamtstrecke entfernt ist. Ab diesem Punkt wird neu gerechnet mit der Reststrecke als Grundlage. Das dürfte allerdings dazu führen das die letzte Strecke immer die längste wird.

[Mr.Homm]

Hallo!
Wollte fragen ob wer einen Ansatz für folgendes Problem hat:

Für eine längere Rundreise stehen schon die Strecken, die Dauer, aber noch nicht die Übernachtungsmöglichkeiten fest. Diese sollen so gewählt werden, dass die längste Tagesetappe möglichst kurz ist.

Beispiel: Bei Distanzen 11, 16, 5, 5, 12, 10 die in 3 Tagen zurückgelegt werden sollen, ist die richtige Antwort 26, mit den Tagesetappen 11, 16+5+5, 12+10
Du bildest drei Tagesetappen aus den ersten drei Strecken.Ich nenne die Etappen A, B und C. Danach kommt zur letzten Etappe (C) immer die nächste noch nicht verwendete Strecke dazu und die Etappen müssen "ausgeglichen" werden. D.h. wenn sich die Differenz zweier benachbarter Etappen durch das Verschieben einer Strecke verkleiner lässt, dann wird es getan. Es kommen aber immer nur die Strecken in Frage, welche direkt an die jeweils andere Etappe angrenzen.Als Beispiel deine Aufgabenstellung:

A B C
1)------+--------+--------+------------
|+5 |-11 |
11 | 16 | 5 | 5 12 10
2)------+--------+--------+------------
|+5 |-6 |
11 | 16 | 5 5 | 12 10
3)------+--------+--------+------------
|+5 |+6 |
11 | 16 | 5 5 12 | 10
4)------+--------+--------+------------
|+10 |-4 |
11 | 16 5 | 5 12 | 10
5)------+--------+--------+------------
|+10 |+6 |
11 | 16 5 | 5 12 10|
6)------+--------+--------+------------
|+15 |-4 |
11 | 16 5 5 | 12 10 |
--------+--------+--------+------------
Bei Schritt 1) ist A=(11), B=(16) und C=(5). Die Differenzen stehen in der Tabelle über den Strecken der Etappen.Bei 2) wird zu C die zweite fünf hinzugefügt. Die Differenz von B zu C ist nicht groß genug, um von C etwas nach B zu verscheiben.Im 3) Schritt ist C groß genug, um eine Strecke (die erste fünf) von C nach B zu verschieben. Bei 5) passiert das Gleiche nochmal.Duch eine Verschiebung kann natürlich auch eine weitere Verschiebung provoziert werden. In deinem Beispiel kommt die Situation allerding nicht vor.

[hauer85]

danke war sehr hilfreich!!