Praktikum 3

Moderator: Effiziente Graphenalgorithmen

kutschke
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 112
Registriert: 16. Apr 2009 10:39

Praktikum 3

Beitrag von kutschke »

Frage zur Aufgabenstellung:

Muss die LÄNGE der Postbotentour berechnet werden oder eine tatsächliche Tour?

Benutzeravatar
Stille
Moderator
Moderator
Beiträge: 195
Registriert: 3. Jul 2008 10:11

Re: Praktikum 3

Beitrag von Stille »

Moin,

Sie sollen Lösungen für das Postbotenproblem bestimmen, dies sind Mengen von Kanten. Diese können Sie gerne in einer Datei speichern. Die Ausgabe auf der Konsole soll jedoch nur die Tourlängen und die Rechenzeiten angeben.

Viele Grüße,

Wolfgang Stille
Wolfgang Stille
UKP Lab - FB Informatik
http://www.ukp.informatik.tu-darmstadt.de

kutschke
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 112
Registriert: 16. Apr 2009 10:39

Re: Praktikum 3

Beitrag von kutschke »

Hallo! Ich glaube, ich habe es immer noch nicht verstanden, da meiner Meinung nach eine Kantenmenge nicht viel Sinn macht, da diese ja einfach die komplette Kantenmenge des Graphen wäre (jede Kante muss ja genutzt sein). Sinnvoll wäre meiner Meinung nach entweder eine Tour (Folge von Kanten) oder die in den Folien genannte Funktion, die angibt, welche Kanten mehrmals benutzt werden müssen. Oder ist mit Kantenmenge das Matching gemeint (+ Gewicht der hinzugekommenen Kanten)?

Benutzeravatar
Stille
Moderator
Moderator
Beiträge: 195
Registriert: 3. Jul 2008 10:11

Re: Praktikum 3

Beitrag von Stille »

Ja klar, sorry: eine Multimenge oder die Anzahl von Kopien pro Kante. Eine Tour (oder Kantenfolge), die man sich daraus ja einfach konstruieren kann, ist natürlich auch ok.
Wolfgang Stille
UKP Lab - FB Informatik
http://www.ukp.informatik.tu-darmstadt.de

Benutzeravatar
zimpfer
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 144
Registriert: 15. Mär 2009 01:07

Re: Praktikum 3

Beitrag von zimpfer »

Kommen noch Testcases?

Benutzeravatar
Stille
Moderator
Moderator
Beiträge: 195
Registriert: 3. Jul 2008 10:11

Re: Praktikum 3

Beitrag von Stille »

Ja, ich warte auch drauf :)

Sie können in jedem Fall die MST-Testcases verwenden. Die sind aber seeeehr grooooß (ein Postbote für ganz New York / Colorado / Florida. Der arme!). Kleinere folgen asap.

Sie können sich auch ganz einfach welche basteln, z.B. \(K_{n,n}\) für \(n\) ungerade oder \(K_{n}\) für \(n\) gerade, Haus vom Nikolaus, etc...
Wolfgang Stille
UKP Lab - FB Informatik
http://www.ukp.informatik.tu-darmstadt.de

Benutzeravatar
Stille
Moderator
Moderator
Beiträge: 195
Registriert: 3. Jul 2008 10:11

Re: Praktikum 3

Beitrag von Stille »

Testcases sind da.
Wolfgang Stille
UKP Lab - FB Informatik
http://www.ukp.informatik.tu-darmstadt.de

Benutzeravatar
zimpfer
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 144
Registriert: 15. Mär 2009 01:07

Re: Praktikum 3

Beitrag von zimpfer »

Not Found

The requested URL /lehre/graphalgo/2010ws/data/03_test_graphs.zip was not found on this server.
Scheinbar noch nicht bzw. der Link ist falsch

Benutzeravatar
Stille
Moderator
Moderator
Beiträge: 195
Registriert: 3. Jul 2008 10:11

Re: Praktikum 3

Beitrag von Stille »

Jetzt aber :)
Wolfgang Stille
UKP Lab - FB Informatik
http://www.ukp.informatik.tu-darmstadt.de

Benutzeravatar
MisterD123
Geek
Geek
Beiträge: 811
Registriert: 31. Okt 2006 20:04
Wohnort: Weiterstadt

Re: Praktikum 3

Beitrag von MisterD123 »

Mein Parser hat mich grade drüber aufgeklärt dass koenig_n.sp sowie koenig_w.sp jeweils 7 kanten enthalten obwohl der header nur 6 ankündigt. ;P

ich hab einfach mal ne 7 draus gemacht.

Benutzeravatar
Stille
Moderator
Moderator
Beiträge: 195
Registriert: 3. Jul 2008 10:11

Re: Praktikum 3

Beitrag von Stille »

Hallo. Wir verlängern die Frist bis zum Sonntag 23:59:59 GMT. Wer schon abgegeben hat, kann gerne nochmal ein Update einreichen.
Wolfgang Stille
UKP Lab - FB Informatik
http://www.ukp.informatik.tu-darmstadt.de

Antworten

Zurück zu „Effiziente Graphenalgorithmen“