Narses - Fr 26.12.08 01:45
Titel: AGS 2008 - Paranuss 3 (WLAN-Kabel): Lösung

---

Moin!

Hier die Lösung zur WLAN-Kabel-Frage. Im Wesentlichen ging es darum, den minimalen Spannbaum eines Graphen [http://de.wikipedia.org/wiki/Minimaler_Spannbaum] zu bestimmen. Dazu kann man z.B. den Algorithmus von Kruskal [http://de.wikipedia.org/wiki/Algorithmus_von_Kruskal] anwenden.

Summiert man die Kanten des Spannbaums, kommt man auf eine Länge von ca. 3.325 - 3.327 km, je nach verwendetem Geo-Modell. Damit landet man bei einem Gesamtpreis von etwas über 10 Millionen Euro :arrow: abgerundet also 10.000.000 Euro. ;)

In der anhängenden Musterlösung wird wie oben beschrieben vorgegangen. Kleines Gimmik: Der gefundene Spannbaum wird als Radialprojektion eingezeichnet. :)

Allen Mitspielern viel Glück bei der Auswertung!

cu
Narses

Martok - Fr 26.12.08 01:59

---

Das war einfach ;)

Ich hab eine Abwandlung von Prim verwendet, die schon fast als selbsterfunden durchgeht. Als kleines Gimmick gibts eine Schwarz-Weiß-Grafik mit roten Punkten, die entfernt an eine Map erinnert^^

Übrigens wird hardgecodet die orte.txt-Datei gelesen, sollte man zum Testen also mit auspacken ;)

EDIT: Timing eingefügt, 6-8ms mit allem drum und dran.

jaenicke - Fr 26.12.08 02:21

---

Mein Algorithmus ist auch der von Prim, nur nicht ganz so schön wie ich den eigentlich in der Graphentheorie gelernt hatte. :D

Das Programm zeigt die Gesamtkosten abgerundet auf 25000er und genau an, außerdem alle Verbindungen im MST und deren Entfernungen.
Selbstverständlich durfte eine graphische Darstellung nicht fehlen, auch wenn die wohl noch Macken hat. :gruebel:



(Der Knopf links sollte eine richtige Karte laden und deren Koordinaten sollten auch einstellbar sein, aber das ist "not implemented yet" ;-))

GTA-Place - Fr 26.12.08 11:34

---

Hab einen eigenen Algorithmus entwickelt: Berechne alle Distanzen, sortiere nach kürzerster Distanz. Fange an [0] mit [1], [1] mit [2], etc. verbinden, falls diese Verbindung (rekursiv geprüft) nicht schon besteht. Laufzeit mit Sortieren, ohne Zeichnen: 0,5 Millisekunden, mit Zeichnen: 1,0 Millisekunden.

Screenshot im Anhang, Programm folgt.

Gausi - Fr 26.12.08 11:42

---

@GTA-PLace: Das ist eigentlich die Idee, die hinter dem Algorithmus von Kruskal steckt. Kannst das also nicht als Patent anmelden, weil wegen Prior-Art. ;-)

GTA-Place - Fr 26.12.08 11:44

---

Nein ist es nicht :bawling: (mach halt alles kaputt :bawling: )

Boldar - Sa 27.12.08 14:15

---

mmh ich hab mich mit prim versucht und heute endlich den Glaitkomazalärror gefundne...

Fiete - So 28.12.08 13:12
Titel: Re: AGS 2008 - Paranuss 3 (WLAN-Kabel): Lösung

---

Moin,
ich habe unter TP7 1990 schon einen Spannbaum nach Kruskal programmiert. Es fehlte nur die Entfernungstabelle.
Lösung rausgeholt und mit der Paranuß2 2007 kombiniert, fertig. :wink:
Gruß
Fiete

jfheins - So 04.01.09 14:57

---

Etwas spät, aber beim Snowboarden hatte ich kein Internet ;)

Anbei auch mal mein Programm - es erlaubt nicht nur die Graphische Darstellung mit Karte (Mercator-Projektion benutzen, für eine lineare Abbildung) sondern auch die Auswahl des Ellipsoids.

"gerade" benutzt den Satz des Phytagoras und schätzt immerhin noch die Größenordnung reichtig ein - aber vernachlässigt die Krümmung der Erde ...

Benutzt den Algo von Prim (erschien mir einfacher zu implementieren, Laufzeit ist ja nicht so wichtig ...)