Praktikum 2

Moderator: Effiziente Graphenalgorithmen

Benutzeravatar
bier
Windoof-User
Windoof-User
Beiträge: 39
Registriert: 4. Sep 2009 16:58

Praktikum 2

Beitrag von bier »

Hallo,
Dürfen wir im aktuellen Praktikum auch make_heap, push_heap, sort_heap etc aus algorithm verwenden, oder sollen wir das selbst implementieren?
Ist für die Ausgabe irgendein Format gefordert, oder können wir das nach Belieben machen?

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

Re: Praktikum 2

Beitrag von Stille »

bier hat geschrieben:Hallo,
Dürfen wir im aktuellen Praktikum auch make_heap, push_heap, sort_heap etc aus algorithm verwenden, oder sollen wir das selbst implementieren?
Meinen Sie die STL Algorithms? Meinetwegen ja.
bier hat geschrieben: Ist für die Ausgabe irgendein Format gefordert, oder können wir das nach Belieben machen?
Es sollte in etwa so aussehen wie in der Aufgabenstellung bzw. der Vorlesungsfolie. Hauptsache ist dass es übersichtlich ist.
Wolfgang Stille
UKP Lab - FB Informatik
http://www.ukp.informatik.tu-darmstadt.de

dk1001
Mausschubser
Mausschubser
Beiträge: 44
Registriert: 14. Okt 2008 12:30

Re: Praktikum 2

Beitrag von dk1001 »

Stille hat geschrieben:
bier hat geschrieben:Hallo,
Dürfen wir im aktuellen Praktikum auch make_heap, push_heap, sort_heap etc aus algorithm verwenden, oder sollen wir das selbst implementieren?
Meinen Sie die STL Algorithms? Meinetwegen ja.
Begeisterung klingt anders… ;) Aber ja, mein Kollege meinte tatsächlich die STL Implementierungen in <algorithm>, wie http://www.cplusplus.com/reference/algorithm/make_heap/ , für den Fall, dass es noch andere (verlorene) c(++)-liebende Seelen geben sollte.
Java hat dafür sicherlich eine Collection (oder wie sich das schümpft), nur klingt der Header <algorithm> nunmal verdächtig nach "besser fragen bevor es verboten ist…".
Stille hat geschrieben:
bier hat geschrieben:Ist für die Ausgabe irgendein Format gefordert, oder können wir das nach Belieben machen?
Es sollte in etwa so aussehen wie in der Aufgabenstellung bzw. der Vorlesungsfolie. Hauptsache ist dass es übersichtlich ist.
Gemeint ist hier vor allem:
In Praktikum 1. war für die Einzelalgorithmen ein Ausgabeformat vorgegeben, dass alle im MST enthaltenen Kanten angab - in eine neue Datei. Ist dies auch diesmal erwünscht?


Die Aufgabenstellung spricht auf Seite 3 im ersten Satz auch von Testcases, die durchlaufen sollen. Nur, sind damit die weiter oben vorgeschlagenen eigenen Testcases gemeint - für die alles andere recht sinnfrei wäre - oder sind Testcases gegeben und wir habe sie nur nicht gefunden?
MfG. David Kalnischkies
"Sprächen die Menschen nur von Dingen, von denen sie etwas verstehen, die Stille wäre unerträglich."
"If Java had true garbage collection, most programs would delete themselves upon execution." -- Robert Sewell

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

Re: Praktikum 2

Beitrag von Stille »

Guten Abend,

meine Begeisterung hält sich nach diversen eigenen Erfahrungen mit der STL durchaus in Grenzen: es gibt sicherlich Dinge, die ganz gut funktionieren. Ich hoffe der Heap gehört dazu. Den hatte ich bislang noch nicht verwendet. Der Name der Lib <algorithm> ist allerdings etwas irreführend.

Die Kanten des Pfades (in eine Datei) auszugeben ist tatsächlich sinnvoll, nicht aber obligatorisch für dieses Praktikum. Eine korrekte Pfadlänge ist normalerweise auf diesen Daten kein Zufall. :)

Zum Thema Testcases: Ich stelle Ihnen die nächsten Tage ein paar Werte zusammen, anhand derer sie die Korrektheit Ihrer Implementierung validieren können, ok?
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 2

Beitrag von Stille »

Hallo,

wie versprochen ein paar Distanzen zur Verifikation anbei. Grundlage ist der NYC-Datensatz.

FROM TO DISTANCE
96008 172944 900041
1 100 114015
500 170000 707022
100000 150000 506442
5000 100000 820921
142674 123876 406508
3424 43214 923412
8797 145784 461545
75849 164985 739783
98748 2347 847551
Dateianhänge
NYC_Results.txt
Ergebnisse s-t-Pfade auf dem NYC-Dataset
(206 Bytes) 68-mal heruntergeladen
Wolfgang Stille
UKP Lab - FB Informatik
http://www.ukp.informatik.tu-darmstadt.de

Christian_
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 178
Registriert: 10. Apr 2009 16:30

Re: Praktikum 2

Beitrag von Christian_ »

können wir davon ausgehen, dass die Knotennummer immer von 0 bis n-1 gehen, oder kann es sein, dass manche Zahlen gar nicht vergeben sind und somit Nummern größer n existieren können?
Omnium rerum principia parva sunt. -Cicero

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

Re: Praktikum 2

Beitrag von Stille »

Code: Alles auswählen

edmonds:Graphs stille$ cat -n NYC.sp | grep 264347
264347	v 264345 73714376 41004205
Ihre Annahme sollte also in Ordnung gehen.
Wolfgang Stille
UKP Lab - FB Informatik
http://www.ukp.informatik.tu-darmstadt.de

Christian_
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 178
Registriert: 10. Apr 2009 16:30

Re: Praktikum 2

Beitrag von Christian_ »

Ich habe für den bidirektionalen und den gerichteten Dijkstra eine andere Anzahl an PQ-Ops als das Bild in Folie IV.39
Da Dijkstra aber deterministisch (bis auf idtentische Distanzlabels) ist verwundert mich das ein bisschen. Kann jemand meine oder die Werte der Folie betätigen?

Code: Alles auswählen

|---------|-----------|---------|----------------------------------------|
|  d(s,t) | Time (ms) |  PQ-OPs |         Variant, data structure        |
|=========|===========|=========|========================================|
| 900.041 |    405,15 | 248.912 |         standart dijkstra, binary heap |
|---------|-----------|---------|----------------------------------------|
| 900.041 |   380,843 | 162.250 |    bidirectional dijkstra, binary heap |
|---------|-----------|---------|----------------------------------------|
| 900.041 |   372,856 | 170.353 |         directed dijkstra, binary heap |
|---------|-----------|---------|----------------------------------------|
Omnium rerum principia parva sunt. -Cicero

Romeo
Erstie
Erstie
Beiträge: 12
Registriert: 16. Nov 2011 10:03

Re: Praktikum 2

Beitrag von Romeo »

Hallo,
Ich habe folgende Ergebnisse, die sich teilweise mit denen von den Folien decken (Standard- und bidirektionale Variante). Bei A* habe ich etwas mehr (siehe unten)

Viele Grüße
Roland

Code: Alles auswählen

File: ../../prog02/NYC.sp with n=264346 m=733846
Query: s=96008, t=172944
Running comparison tests with 1 runs per configuration...
d(s,t)    |time(ms)  |PQ-ops    |params                                        |
--------------------------------------------------------------------------------
900041    |80        |248912    |heap                                          |
900041    |60        |162783    |heap, bidirectional                           |
900041    |220       |170353    |heap, A*                                      |
900041    |50        |248912    |dial                                          |
900041    |60        |162783    |dial, bidirectional                           |
900041    |200       |170354    |dial, A*                                      |

Christian_
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 178
Registriert: 10. Apr 2009 16:30

Re: Praktikum 2

Beitrag von Christian_ »

Ich habe jetzt herausgefunden woher der Unterschied der bidirektionalen Suche zwischen 162783 und 162250 PQ-OPs kommt.
Bei ersterem wird der Knoten mit kleinstem Abstand aus Q_f und Q_b in jedem Schritt ausgewählt.
Bei letzterem wird strikt abwechselnd aus Q_f und Q_b gewählt

Da hatte ich wohl die Folie falsch interpretiert
Omnium rerum principia parva sunt. -Cicero

Kai.S
Windoof-User
Windoof-User
Beiträge: 38
Registriert: 10. Apr 2010 22:22

Re: Praktikum 2

Beitrag von Kai.S »

Hi, wie soll A* mit Dial funktionieren? Also ich meine die Dial Version mit nur C+1 buckets... Gibt es da irgendwie einen Trick, einen Hinweis? Da man ja mod C+1 rechnet, allerdings beim key ja die Heuristik drinstecken hat ist die Reihenfolge in den C+1 buckets wohl nicht unbedingt optimal :/


EDIT:
Es funktioniert (immer? relativ zuverlässig?), wenn ich (C+1)*1.1 buckets nehme... Ich vermute mal aber, dass dies dann ein bisschen mit Glück zu tun hat. Aber damit bin ich auf die Idee gekommen, dass ein bestimmter Faktor (nicht 1.1^^) notwendig ist, dass diese Version mit A* (garantiert) funktioniert, liege ich da richtig?

Und zur bidirektionalen Suche... eigentlich müsste es doch vollkommen egal sein, wie man alterniert. Wobei deine Version (kleinsten Abstand aus beiden wählen) einen Haken hat... Sind entweder am Start oder am Ziel alle Kanten riesengroß und die restlichen ganz klein hast du praktisch wieder einen Standard Dijkstra.
Zuletzt geändert von Kai.S am 28. Dez 2011 19:09, insgesamt 1-mal geändert.

Kai.S
Windoof-User
Windoof-User
Beiträge: 38
Registriert: 10. Apr 2010 22:22

Re: Praktikum 2

Beitrag von Kai.S »

Sorry double post...

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

Re: Praktikum 2

Beitrag von zimpfer »

Kai.S hat geschrieben:Hi, wie soll A* mit Dial funktionieren? Also ich meine die Dial Version mit nur C+1 buckets... Gibt es da irgendwie einen Trick, einen Hinweis? Da man ja mod C+1 rechnet, allerdings beim key ja die Heuristik drinstecken hat ist die Reihenfolge in den C+1 buckets wohl nicht unbedingt optimal :/


EDIT:
Es funktioniert (immer? relativ zuverlässig?), wenn ich (C+1)*1.1 buckets nehme... Ich vermute mal aber, dass dies dann ein bisschen mit Glück zu tun hat. Aber damit bin ich auf die Idee gekommen, dass ein bestimmter Faktor (nicht 1.1^^) notwendig ist, dass diese Version mit A* (garantiert) funktioniert, liege ich da richtig?

Und zur bidirektionalen Suche... eigentlich müsste es doch vollkommen egal sein, wie man alterniert. Wobei deine Version (kleinsten Abstand aus beiden wählen) einen Haken hat... Sind entweder am Start oder am Ziel alle Kanten riesengroß und die restlichen ganz klein hast du praktisch wieder einen Standard Dijkstra.

Deine Kanten modifizierst du wohl wie in den Folien angegeben:
c'(u, v) := c(u, v) - b(u, t) + b(v, t)

Beim A*-Dial musst du nun diese modifizierten Kanten als Queuegröße verwenden, damit er funktioniert.

Kai.S
Windoof-User
Windoof-User
Beiträge: 38
Registriert: 10. Apr 2010 22:22

Re: Praktikum 2

Beitrag von Kai.S »

Danke für den Hinweis auf die Folien... Ich hatte es leicht anders :/

Wobei die Idee mit dem Faktor ja auch nicht falsch ist... die transformierten Gewichte können ja maximal zu 2C werden! Ist die Frage, ob ich meinen Code umschreiben muss, oder ob es auch einfach okay ist von 2C auszugehen... ändert ja nichts in GroßO

Antworten

Zurück zu „Effiziente Graphenalgorithmen“