Forums » 30. BwInf
Lösungen Aufgabe 1
-
Meine Erweiterung besteht darin, dass es immer zwei Straßenseiten (also letztendlich einen gerichteten Graphen) gibt, den man streuen muss.
Die Länge der Kanten ist bei mir auch variabel (eine natürliche Zahl), genauso wie die Kapazität (was ja eigentlich noch in die "normale Aufgabe" gehört).
-
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.
This post was edited by Maximilian J at 22. April 2012 22:36:34 CEST -
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.