Hi,
ich würde gerne eine Lösungsdiskussion über Aufgabe 1 anstoßen.
Also ich habe folgendes herausgefunden:
Bei der Aufgabenstellung handelt es sich um ein Problem aus der kantenorientierten Tourenplanung, das man auch als "Capacitated Arc Routing Problem" (CARP) kennt (die Aufgabenstellung weicht von der Urform dieses Problems geringfügig ab).
Das CARP ist NP- vollständig (vgl. Lenstra und Rinnooy, sogar eine Lösung zu finden, die 1,5 mal besser ist als die optimale Lösung ist NP-vollständig).
Aufgrund der NP-Vollständigkeit habe ich mir eine Heuristik gebastelt.
Beim ersten Graphen fährt mein Fahrzeug 60km, beim 2. Graphen insgesamt 80km.
Greets
Programmer
Das Straßennetz stellt bei mir einen Graphen dar. Ganz im Groben:
Ich hab den Graphen zu einem eulerschen Graphen erweitert, dann eine Eulertour dadurch gelegt und diese Eulertour in kleinere, für Konrad machbare, Routen aufgeteilt.
Ergebnis: Beispiel1: 60km, Beispiel2: 80km
Ich habe das Problem auch als CARP interpretiert und dann mit Ant Colony Optimization gelöst, die 60/80 hatte ich auch raus. Für den ersten Aufgabenteil, bei dem nur irgendeine Tour gefunden werden sollte, habe ich einen einfachen Greedy-Algorithmus geschrieben, der immer die jeweils nächste, ungestreute Kante auswählt.
Mich würde interessieren, wie ihr in euren Programmen die Lösungen repräsentiert habt. Ich blende einmal rechts eine Liste mit den einzelnen Teilrouten ein (also immer einmal vom Depot los bis wieder dort hin), wenn der Benutzer die anklickt wird auf der Karte jeweils farblich hervorgehoben, welche Kanten gestreut, bzw. überquert werden müssen. Falls die Darstellung zu unübersichtlich ist, wird zusätzlich eine Wegbeschreibung im Stil von "[Streuen an] 3 Osten [Streuen aus] 2 Norden ..." ausgegeben.
Mein Quellcode ist hier: https://bitbucket.org/Wey/bwinf30-2_ned/src
Habt ihr Programme/Quellcode irgendwo hochgeladen?
p. s.:
>>...sogar eine Lösung zu finden, die 1,5 mal besser ist als die optimale Lösung ist NP-vollständig
Widerspruch?
Felix B. said:
p. s.:
>>...sogar eine Lösung zu finden, die 1,5 mal besser ist als die optimale Lösung ist NP-vollständig
Widerspruch?
Ja, habe ich im Eifer des Gefechts wohl übersehen. Also ich habe gemeint, dass wenn man das Ziel hat eine Lösung zu finden, deren Kosten (also insgesamt gefahrene Kilometer) 1,5 mal größer sind als die optimale Lösung, ist das immer noch NP-vollständig.
Ich habe das Netzwerk auch als Graphen interpretiert. Ob eine Kante gestreut ist, oder nicht, habe ich durch ein boolsches Array repräsentiert. Die Ausgabe ist also dann beispielsweise:
Streue Kilometer 1,2,3 der Kante 0-4
In der Doku habe ich die Ausgaben gekürzt und vereinfacht, da es relativ anstrengend ist, solche Ausgaben durchzulesen.
Mich würde noch interessieren, ob und wenn ja wie ihr die Aufgabe erweitert habt.
Ich habe
1. Straßen mit beliebigen (ganzzahligen) Längen (=Salzbedarf) zugelassen
2. Mehrere Depots zum Nachladen, an beliebigen Stellen im Straßennetz, zugelassen
3. Straßennetze die nicht dem Raster folgen zugelassen
Ich habe den Graphen wie Lukas zu einem euler'schen erweitert und dann für einen Eulerzyklus mittels DP die beste Möglichkeit ihn abzufahren ermittelt. Um den Graphen zu einen euler'schen zu erweitern, wollte ich die Summe der hinzugefügten Kanten minimieren, was ein matching-Problem ist. Leider habe ich das nicht mehr geschafft, weswegen ich einen effektiven (vermutlich optimalen) aber verteufelt ineffizienten Algorithmus habe.
Erweiterungen sind, dass man den Startpunkt und die Punkte (es können mehrere sein) an denen man nachladen kann frei wählen darf (der Startpunkt muss kein solcher sein).
Zudem kann man die Kapazität verändern, falls das eine erweiterung ist.
Maximilian J said:
Um den Graphen zu einen euler'schen zu erweitern, wollte ich die Summe der hinzugefügten Kanten minimieren, was ein matching-Problem ist. Leider habe ich das nicht mehr geschafft, weswegen ich einen effektiven (vermutlich optimalen) aber verteufelt ineffizienten Algorithmus habe.
Das ist interessant, ich hatte exakt dasselbe Problem wie du beim Erweitern :D. Habe mich schließlich dazu entschlossen, falls die Anzahl Knoten ungeraden Grads dies zulässt (<18), alle Möglichkeiten auszuprobieren und ansonsten Simulated Annealing verwendet.