Ich habe das Problem vereinfacht, in dem ich mir den symmetrischen Graphen angeschaut habe. Da die rechte Seite immer kürzere Strecken als die linke hatte, habe ich die Seiten getrennt betrachtet und konnte so zahlreiche Wege sparen.
Ich habe zunächst einmal für alle 6 Städte die Summe der beiden kleinsten Strecken addiert (wenn man bei einer Stadt nicht beginnt oder anfängt, dann muss man in die Stadt rein und wieder raus, daher diese Summe).
Es ergibt sich:
A 28 B 24 C 20 D 23 E 25 F 21
Wenn man also weder bei A noch E beginnt oder endet, dann "kassiert" man schon einmal 28 + 25 = 53 Längeneinheiten.
Daher ist es optimal mit A zu beginnen und mit E zu Enden oder umgekehrt (da das Problem eh nicht von der Durchlaufrichtung abhängt, ist als A (der Anfang) und E (das Ende) der Route. Somit sind schon einmal die 19 + 18 = 37 LE fix. Wählt man jetzt das Minimum um A zu verlassen und in E anzukommen, dann hat man mindestens noch 13 + 12 = 25 womit wir bei 62 wären. Jetzt sind die übrigen 4 Städte also Durchgangsstädte. Wir benötigen also noch 3 Strecken. Da die 13 bei A gewählt wurde muss C die zweite Station sein. Wählt man die 9 um nach F zu gelangen, d.h. F ist die 3. Stadt. Von F benötigt man mindestens 12 (somit ist enweder B oder D die 4.Stadt). Im Fall B folgt der Weg nach D mit 13 und dann mit 14 (statt 12) zu E. Somit haben wir 13 + 9 + 12 + 13 + 14 + 37 = 98.
Wenn man zuerst nach D und dann nach B geht hat man von B nach E sogar eine 16 ==> Summe ist dann 100.
Um das Problem zu vereinfachen, habe ich mir folgende Gedanken gemacht:
Eigentlich gesucht ist ein Rundweg der jeden Knoten genau einmal betritt im Graphen, der einen weiteren Knoten (Werkstatt des Weihnachtsmanns) beinhaltet, die Kanten zu diesem Knoten haben den Wert, der auf dem jeweils anderen Knoten steht.
Mir ist aufgefallen, dass alle Kanten schonmal 9 kosten, und dann möglicherweise etwas mehr. Da ich einen Rundweg suche, der jeden Knoten genau einmal betritt, muss ich also schonmal 7*9=63 mindestens nutzen, kann von allen Kanten 9 abziehen und im resultierenden Graphen einen kürzesten Rundweg finden, und muss dessen Kosten dann noch hinzufügen.
Ich bin dann darauf gekommen, dass ich das gleiche eigentlich auch pro Knoten machen kann - wenn ich die Kosten aller Kanten inzident an einen bestimmten Knoten um x reduziere, kann ich einen kürzesten Rundweg suchen und zu diesem 2*x hinzufügen und habe das richtige Ergebnis, da ich ja in jedem Rundweg genau zwei Kanten nutzen muss, die diesen Knoten als einen der zwei Knoten haben.
Mit ein wenig umherschaufeln von Gewichten (ich habe anfangs x für alle Knoten auf 5 gesetzt, musste nur für einen Knoten x kleiner machen, damit die Kante mit Gewicht 9 nicht negativ wurde) bin ich auf eine Verteilung von Gewichten gekommen, in der keine negativen Kanten Gewichte vorhanden waren, aber es einen Rundweg gab, der nur 0-Gewicht Kanten nutzte. Dieser ist dann offensichtlich optimal und ich musste nur 2*x pro Knoten zusammenrechnen, um das Ergebnis zu erhalten. Die Verteilung ist:
A: 9, B: 7, C: 4, D: 6, E: 8, F: 5, Werkstatt: 10
Die Summe dieser Werte ist 49, womit ich auch auf das Ergebnis von 98 komme.
Ich mochte den Prozess, mit dem ich hier auf ein Ergebnis gekommen bin. Am Ende ist die Methode eine Art Discharging, das berühmterweise für den Beweis des vier Farben Satzes durch Appel und Haken genutzt wurde. Hier discharge ich Gewichte von Kanten auf Knoten und gelange dadurch zu einer trivial lösbaren Konfiguration. Für mich ist das sehr hübsch!
1 und 2 habe ich vollständig verstanden. Klingt logisch und interessant. Nur Punkt 3 verstehe ich nicht ganz. Magst du ihn nochmal erklären? Ich schreibe morgen meine Lösung mit dem Symmetrieprinzip nochmal auf. Die rechte Seite ist per-se kleiner als die linke. Ich vermute, dass die offizielle Lösung das auch beinhaltet.
(01-01-2024, 08:53 PM)Fanbusfahrer schrieb: 1 und 2 habe ich vollständig verstanden. Klingt logisch und interessant. Nur Punkt 3 verstehe ich nicht ganz. Magst du ihn nochmal erklären? Ich schreibe morgen meine Lösung mit dem Symmetrieprinzip nochmal auf. Die rechte Seite ist per-se kleiner als die linke. Ich vermute, dass die offizielle Lösung das auch beinhaltet.
Ok, genauer erklärt:
Wir betrachten einen Graphen mit Kanten- und Knotengewichten. Wir suchen einen Rundweg, der alle Knoten besucht und dessen erweitertes Gesamtgewicht (Summe Kantengewichte plus Knotengewichte) minimal ist. Wenn wir unseren Graphen hernehmen, die gleichen Gewichte auf die Kanten tun, und jeweils Null Gewicht auf die Knoten, dann ist der gesuchte Weg mit minimalem erweitertem Gesamtgewicht gleich dem Weg mit minimalem normalen Gesamtgewicht, und diese Gesamtgewichte sind gleich.
Wir können jetzt auf dem neuen Graphen Gewichte auf eine bestimmte Art hin und her schieben, ohne das erweiterte Gesamtgewicht von Rundreisen zu verändern. Dafür betrachten wir einen Knoten und alle benachbarten Kanten. Reduzieren wir das Gewicht von jeder dieser Kanten um x und erhöhen das Gewicht des Knotens um 2x, so bleibt das erweiterte Gesamtgewicht jedes Rundweges gleich - der Weg muss den Knoten und genau zwei der benachbarten Kanten benutzen, in der Summe reduzieren wir das Gesamtgewicht also zweimal um x, addieren aber einmal 2x.
Wenn wir genau diesen Prozess mit meinen oben genannten Gewichten machen - als x wählen wir für A: 9, B: 7, C: 4, D: 6, E: 8, F: 5, Werkstatt: 10 - dann bleibt ein Graph, in dem jeder erweiterte Rundweg schon mal Gewicht 98 haben muss, da er eben durch jeden Knoten gehen muss und gleichzeitig alle Kantengewichte nicht-negativ sind. In diesem Graphen finden wir schnell einen Rundweg, der nur Kanten nutzt, die alle Gewicht Null haben, also ist das erweiterte Gesamtgewicht hier 98 und wir haben gleichzeitig eine obere (den Rundweg) und untere (die Summe der Knotengewichte) Grenze von 98 für den minimalen Rundweg.
Hi,
vielen Dank. Ich habe es mir aufgemalt und dann einen neuen Graphen erhalten, der ander Knotengewichte und keine Kantengewichte hatte. Dadurch hast du das Problem irgendwie geschickt transformiert.
Die Knoten und Kanten auf der rechten Seite sind in jeder Kante/in jedem Knoten kleiner als auf der linken Seite.
Die rot markierten sind die kleinsten Werte auf der linken Seite.
Von F und C aus könnten die orangenen Wege von der linken auf die rechte Seite führen.
Von A aus ist der kürzeste Weg zu C und dann zu F (Summe: 19+13+9=41).
Von C gestartet wäre der kürzeste Weg über F zu A (Summe: 15+9+15=39)
Von F gestartet wäre der kürzeste Weg zu C zu A (Summe: 16+9+13=38).
Der kürzeste Weg weg von A zu D wäre 16 und damit um 4 teurer als von F wegzukommen.
Die Wege von A zu F zu C (Summe: 19+15+9=43), von F zu A zu C (Summe: 16+15+13=34) und von C zu A zu F (Summe: 15+13+15=43) sind alle länger.
Der kürzeste Weg ergibt sich damit unmittelbar:
WDW-A-C-F-B-D-E-WDW: 19+13+9+12+13+14+18=98
Korrekt ist Antwort 7.
Lösungsvorschlag A11 Reisender Weihnachtsmann Problem
