jfheins - So 15.12.13 21:21
Titel: Rätsel: WeihnachtsNET

---

Hallo und einen fröhlichen dritten Advent. Da es ja bereits einen Kalender mit gefälligen Rätseln gibt, möchte ich gerne den Anspruch etwas heben :D

Vorgeschichte:
Der Weihnachtsmann hat genug. Nachdem er bereits zahlreiche Lager und Versandzentren errichten ließ häufen sich die Kommunikationsprobleme. Nicht nur dass diverse Medien verwendet werden (Wichtel auf Motorrädern, Feen auf Drachen, Rauchzeichen, Flaggenalphabet, Morsecodes) nein, manche Standorte sind nur aus der Luft mit dem Schlitten erreichbar!

Zum Glück hat der Weihnachtsmann 2008 von einem externen Dienstleister probeweise Deutschland vernetzen lassen. Das hat auch ganz gut geklappt: Die WLAN-Kabel warten teuer aber immerhin geht die Übertragung der Geschenkedaten flott. Die Kommunikation mit dem Nordpol muss aber dennoch über langsames Lametta erfolgen und dann ist da ja noch die Befürchtung, dass die NSA das ganze abhört.

Ein ähnliches Netz möchte er nun global aufspannen. (Der Weihnachtsmann hat ja auch international viel zu tun)

Problemstellung:
Im Anhang findest du die Stadt und ungefähren Koordinaten von den Weihnachtslagern dieser Welt. Der Weihnachtsmann möchte nun ein Programm haben, mit dem er diese optimal untereinander vernetzen kann. (Die genauen Standorte sind selbstverständlich geheim!)
Dabei gilt es folgendes zu beachten:
1. Jeder Standort sollte mit mindestens zwei weiteren vernetzt sein. Der Osterhase knabbert gerne mal ein Kabel durch, das WeihnachtsNET muss trotz eines Kabel-Ausfalls noch funktionieren und alle Standorte anbinden. (Es dürfen durch den Ausfall also auch keine Inseln entstehen!)
2. Die Kabel sind immer noch verdammt teuer. Insgesamt ist natürlich möglichst wenig Kabel zu verlegen.
3. Ein Kabel verbindet immer genau zwei Standorte.
4. Der Hauptsitz am geographischen Nordpol muss selbstverständlich ebenfalls angebunden werden, hier sind jedoch vier Kabel zu legen. Nichts ist schlimmer, als wenn die Geschenkezentrale offline geht!
5. Dank seiner begeisterten Helfer hat der Weihnachtsmann zwei Möglichkeiten zur Kabelverlegung:
a) Engel berechnen 1€ pro Kilometer und verlegen das Kabel überirdisch entlang der Erdkrümmung (Der Weihnachtsmann murmelt verdammte Gewerkschaft in seinen Bart)
b) Kobolde haben angeboten die Kabel unterirdisch auf direktem Weg zu verlegen, verlangen dafür jedoch 1,01€ pro Kilometer Kabellänge.
(Die Materialkosten sind in beiden Angeboten bereits eingepreist)

Schreibe ein Programm, welches die Datei einliest und dem Weihnachtsmann sagt, welche Standorte verbunden werden müssen, wie die Verbindung gelegt werden soll und was der ganze Spaß kostet. Der Weihnachtsmann kann sich zwar Geld leihen, aber er möchte seine Bonität beim Christkind ja auch nicht zu sehr strapazieren :wink:

Zu Gewinnen gibt es leider nichts außer der Ehre. Aber der Weihnachtsmann ist natürlich besonders stolz auf denjenigen der die richtige Lösung in der kürzesten Zeit errechnet. Und das Christkind findet Gefallen daran, die Lösung auch visuell begutachten bevor die den Kredit bewilligt.

Dann mal fröhliches Programmieren - der Weihnachtsmann wartet :)


Edit 19.12.: "mindestens" hinzugefügt

jfheins - Mi 18.12.13 21:01

---

Also falls ihr Fragen habt, könnt ihr die gerne jederzeit stellen. ;-)

Zur Lösung: Ich werde nicht dazu kommen, eine Musterlösung zu programmieren. Ich hoffe mal darauf dass sich für diesen Job kompetente Mitglieder finden 8)

Mathematiker - Mi 18.12.13 23:08

---

Hallo,

jfheins hat folgendes geschrieben :

Also falls ihr Fragen habt, könnt ihr die gerne jederzeit stellen. ;-)

Ich grüble nun schon die ganze Zeit und versuche es mir vorzustellen.

Sehe ich das Folgende richtig?
Wenn jede Station genau(!) mit zwei anderen verbunden sein soll und vom Nordpol aber genau vier Kabel ausgehen, so geht es darum, alle Orte in zwei Rundreisewege (jeweils ausgehend vom Nordpol) einzubinden und die Zerlegung der Gesamtmenge zu finden, die minimale Kosten erzeugt. Anders würde es ja den Aufgabenbedingungen nicht entsprechen.
Oder habe ich jetzt schon zu viel gesagt?

Beste Grüße
Mathematiker

jfheins - Mi 18.12.13 23:41

---

Hi,
gedacht war es eigentlich mit "mindestens zwei". Wenn eine dritte Verbindung an einem Knoten insgesamt Kosten einspart ist dagegen ja eigentlich nichts einzuwenden.
Zwei Rundwege sind dann wahrscheinlich nicht mehr optimal - spätestens wenn die Punkte so angeordnet sind: Φ wird ein Rundweg nicht optimal sein.

Grüße,
jfheins

Mr_Emre_D - Do 19.12.13 07:37

---

Edit: --

Xion - Do 19.12.13 10:27

---

Dann möchte ich die Schlacht mal eröffnen. Ich habe 223163km WLAN-Kabel, das von den Engeln verlegt wird. Macht also

223.163€

(es geht garantiert besser, aber ich hab grad nicht die Zeit extra was zu programmieren)

Um nochmal klarzustellen, was dieses Netz kann:
- Es toleriert einen Kabelausfall, ohne dass der Zusammenhang verloren geht
- Der Nordpol ist mit 4 Kabel angebunden, toleriert also 3 Kabelausfälle direkt am Nordpol.

jfheins - So 29.12.13 17:32

---

Okay,also von Schlacht kann wohl noch keine Rede sein. :P
ich habe leider keine Zeit, das durchzuprogrammieren, aber ich hatte mir folgendes überlegt:
1. Wichtel vs. Kobolde fließt ja nur in die Kostenfunktion ein, somit für die Koimplexität wenig relevant.
2. Einen minimalen Spannbaum konstruieren, der alle Knoten verbindet.
3. Da damit ja keine Ausfallsicherheit herrscht, einen zweiten minimalen Spannbaum konstruieren. Alle Kanten, die bereits im ersten enthalten sind, bekommen Kosten von unendlich. Eine Kante ist also in höchstens einem Spannbaum enthalten.
4. Ggf. noch 1-2 Verbindungen zum Nordpol herstellen (natürlich die biligsten)

Ich habe aber keine Ahnung, wie teuer das dann wird. Vielleicht könnte man da noch ein paar Iterationen machen um unnötige Kanten zu entfernen.

Xion - Di 31.12.13 12:43

---

Also da bin ich auf jeden Fall schonmal nicht schlechter (vermutlich sehr viel besser) als die Musterlösung :mrgreen:

Beobachtungen:
- es ist nicht verboten, Kabel doppelt zu verlegen (d.h. zwei Kabel nebeneinander zu verlegen). Habe ich aber nicht weiter benutzt
- es gilt in jedem Fall die Dreiecksungleichung, es ist also immer billiger ein Kabel direkt zu verlegen, als über einen Umweg durch einen anderen Ort (lokal betrachtet)
- die Eigenschaft, dass ein Kabelausfall nicht das Netzwerk trennen darf, kann man so interpretieren, dass zwischen jeweils zwei beliebigen Städten zwei kabeldisjunkte Wege existieren, es also einen Kreis aus Kabeln gibt, auf denen beide Orte liegen. Wäre dies nicht der Fall, so würde der Ausfall des gemeinsamen Kabels die beiden Städte trennen.

Musterlösung (doppelter MST):
- dies ist wohl die naheliegendste Lösung. Man berechnet einfach zwei minimale Spannbäume (einfach zu implementieren durch Jarnik/Prim-Algorithmus). Fällt ein Kabel in dem einen Spannbaum aus, so springt der andere ein. Der Zusammenhang bleibt also immer erhalten.
- Hier klappt allerdings die Anbindung des Nordpols nicht ohne weiteres! Im nachfolgenden Bild ist ein Beispiel dargestellt, wo bei diesem Fall das Netz durch entsprechende Kabelausfälle partitioniert werden kann.

- Die Musterlösung ist also nicht korrekt (bzw. ihr fehlt der Beweis, dass die dargestellte Situation niemals auftreten kann).

Lösung: Traveling-Salesman-Rundreise aus doppeltem MST
- eine Rundreise durch alle Orte toleriert ebenfalls immer einen Kabelausfall!
- ein einfacher (2)-Approximationsalgorithmus für eine TSP-Tour läuft wie folgt ab:
:arrow: Es wird ein MST berechnet (ohne Nordpol!!)

:arrow: Die Kanten des MST werden verdoppelt
:arrow: Nun hat jeder Ort eine gerade Anzahl an Kabelanschlüssen
:arrow: Es existiert dann ein (leicht durch Tiefensuche zu bestimmender) Hamiltonkreis, welcher alle Kabel genau einmal durchläuft. Nun können wir vom Kreis doppelt durchlaufene Orte abkürzen (d.h. die benachbarten direkt verbinden). Dies erhöht die Kosten nicht, da die Dreiecksungleichung gilt.
- Wir haben also eine Rundreise, welche maximal so teuer ist wie die doppelte Länge des MST. Diese Lösung ist sehr wahrscheinlich deutlich besser als zwei MSTs zu verlegen.
- Da es sich um eine Rundreise handelt, können wir nun tatsächlich noch die vier billigsten Kabel vom Nordpol aus verlegen. Die Rundreise kann niemals partitioniert werden, der Nordpol ist immer an die Rundreise angebunden.
- als Lösung (excl. 4 Anbindungen des Nordpols) erhalte ich hier etwa 260.000 km (Engel-)Kabel, da mein Algorithmus nur die geo-Koordinaten berücksichtigt.

Lösung: bessere Algorithmen für Traveling-Salesman-Rundreise
- Nun ist der oben erwähnte Algorithmus zur Berechnung einer TSP-Rundreise nicht sehr gut. Es gibt wesentlich bessere. Für meine Lösung habe ich 3Opt verwendet (bester meiner Algorithmen für mein Hauptseminar).
- Dieser Algorithmus kommt auf etwa 208.000 km (Engel-)Kabel.

- Beweisbar gibt es keine bessere Rundreise als 191.862km (untere Schranke von Held/Karp). Die Lösung ist also schon recht gut.

Optimalität und Komplexität
- Die Traveling-Salesman-Rundreise ist nicht immer optimal, deutlich wird dies wenn (wie jfheins schon sagte) die Knoten in Form eines Φ angeordnet sind.
- Die Komplexität ist auf jeden Fall in nichtdeterminisitsch polynomiell (NP) enthalten, denn wenn man eine Lösung für das Problem hätte, kann man leicht (in polynomialzeit) überprüfen, ob die geforderten Ausfallsicherheiten gewährleistet sind. Gefühlsmäßig würde ich sagen, dass das Problem auch NP-hart ist. Ein effizienter Algorithmus zur Bestimmung einer optimalen Lösung wäre demnach eher nicht zu erwarten.