Informatiker Board | Theoretische Informatik | Maximale Tagesstrecke minimieren

Informatiker Board » Themengebiete » Theoretische Informatik » Maximale Tagesstrecke minimieren » Antwort erstellen

» Hallo Gast [Anmelden|Registrieren]

Antwort erstellen

Benutzername:

(du bist nicht eingeloggt!)

Thema:

Nachricht:

HTML ist nicht erlaubt
BBCode ist erlaubt
Smilies sind erlaubt
Bilder sind erlaubt

Smilies: 21 von 33

einfacher Modus erweiterter Modus

aktuellen Tag schließen

alle Tags schließen

Spamschutz:
Text aus Bild eingeben

URLs automatisch umwandeln: fügt automatisch [url] und [/url] in Internet-Adressen ein.
Smilies in diesem Beitrag deaktivieren.
BBCode in diesem Beitrag deaktivieren.
Bilder in diesem Beitrag deaktivieren.
Signatur anzeigen: Soll die im Profil eingestellte Signatur an den Beitrag angehangen werden?
Nachrichtenlänge überprüfen

Die letzten 4 Beiträge
eulerscheZahl	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.
mseye	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
eulerscheZahl	Spontan fällt mir auch nicht besseres ein. Bei Hütten (Start und Ziel mitgezählt) und Tagen hast du $[latex]\binom{h-1}{t-1}[/latex]$ Möglichkeiten zu testen. Bei deinem Beispiel also $[latex]\binom{5}{2} = 10[/latex]$ Du kannst versuchen, Regeln zu finden, wann du Kombinationen ausschließen kannst: wenn z.B. zwei aufeinanderfolgende Strecken in der Summe kleiner oder gleich der durchschnittlichen Tagesstrecke sind, können die Strecken nicht allein stehen (sie müssen nicht notwendigerweise am selben Tag zurückgelegt werden, aber es wird mit ihnen eine andere Strecke am selben Tag genommen). Von Hütte 2 nach 3 bzw. 3 nach 4 kann nicht die einzige des Tages sein (10 < 19.67). Das selbe gilt für Hütte 4 zu Hütte 5, da auch 17 < 19.67 ist. Aber es wird vermutlich auf Bruteforce hinauslaufen, eben mit ein paar kleinen Vereinfachungen.
mseye	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