Praktikum 2

Moderator: Effiziente Graphenalgorithmen

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

Praktikum 2

Beitrag von zimpfer »

Ich habe nun die erste Variante Dijkstra (binärer Heap) implementiert und wollte mal fragen, ob ihr auch diese Ergebnisse habt

Für s=1 t=200 auf den 3 großen Testgraphen:
COL.sp: Pfadkosten: 128010, 18 Kanten
NYC.sp: Pfadkosten: 88037, 46 Kanten
FLA.sp: Pfadkosten: 56408, 12 Kanten


Kann das jemand bestätigen?


edit:
Werte waren falsch, nun sollte es passen

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

Re: Praktikum 2

Beitrag von zimpfer »

Eine Frage zur Zeitmessung:

Inwieweit soll das Erstellen des Graphen in die Laufzeit mit eingehen?
Ich erstelle den Graphen direkt beim Einlesen der Datei, da es sich dor ganz gut anbietet, weil ich dort über alle Kanten und Knoten iteriere.

Als Graph nutze ich nicht JUNG, sondern mein Graph ist eine HashMap, die für jeden Knoten alle von ihm ausgehenden Kanten speichert.
Diese HashMap erstelle ich wie gesagt beim Einlesen und übergebe sie sowie Start- und Endknoten schließlich dem Dijkstra().
Als Laufzeit messe ich momentan nur die Ausführung der jeweiligen Dijkstravariante, die einen fertiges Graphenobjekt übergeben bekommen.
Ist das so in Ordnung?



Und noch eine Frage zur Ausgabe:
Der kürzeste Pfad selbst muss nicht ausgegeben werden oder in einer Datei gespeichert werden?

nekoh
Neuling
Neuling
Beiträge: 5
Registriert: 28. Dez 2010 23:43

Re: Praktikum 2

Beitrag von nekoh »

zimpfer hat geschrieben:...
Für s=1 t=200 auf den 3 großen Testgraphen:
COL.sp: Pfadkosten: 128010, 18 Kanten
NYC.sp: Pfadkosten: 88037, 46 Kanten
FLA.sp: Pfadkosten: 56408, 12 Kanten

Kann das jemand bestätigen?
...
Vielleicht etwas spät, aber yep, habe die gleichen Werte raus ;)

Zu der Laufzeit Messung: so war es auch in der ersten Programmieraufgabe, also wird es auch hier so gedacht sein. Außerdem steht in der Aufgabenbeschreibung: "time(ms): die Dauer der Berechnung in Millisekunden (ohne Einlesen des Graphen und Ausgabe!)".
zimpfer hat geschrieben:...
Der kürzeste Pfad selbst muss nicht ausgegeben werden oder in einer Datei gespeichert werden?
Die Antwort auf diese Frage würde mich aber auch interessieren. Bisher gebe ich mehr oder weniger nur im dem Tabellenformat aus, wie es in der Aufgabenstellung gezeigt ist.

Außerdem würde mich interessieren ob jemand die Kombination von bidirektionaler und zielgerichteter Suche implementiert hat. In der Aufgabenstellung steht zwar, dass diese sich nicht kombinieren lassen müssen, aber eventuell hat es trotzdem jemand gemacht.
Ich habe es implementiert und bin auf ein komischen Phänomen gestoßen. Dieser rechnet nämlich (bei mir zumindest) meistens das richtige Ergebnis aus, wie zB. bei dem Testfall oben mit s=1 und t=200 auf allen drei Graphen. Allerdings gibt es Testfälle, wie zB. das aus dem Auszug in den Vorlesungsfolien auf Seite 37 mit s=96008 und t=172944 auf NYC.sp, bei denen die Distanz und dann auch die Hop-Anzahl abweichen. Ausserdem weichen bei mir die Anzahl der PQ-Operationen teilweise ein wenig von denen in den Folien ab:

Code: Alles auswählen

Loaded Graph 'NYC.sp' in 2856ms
Graph has 264346 nodes and 733846 edges (36946 max length).
Path from #96008 to #172944:

    d(s, t) |   Hops |  Time (ms) |   PQ-Ops | Data Structure, Variant
------------+--------+------------+----------+-------------------------
     900041 |    813 |        175 |   248912 | heap,                  
     900041 |    813 |         92 |   248912 | dial,                  
     900041 |    813 |        114 |   162250 | heap, bidirectional    
     900041 |    813 |         66 |   162250 | dial, bidirectional    
     900041 |    813 |        176 |   170353 | heap, goal-directed    
     900041 |    813 |        116 |   170353 | dial, goal-directed    
     902048 |    768 |         98 |    90159 | heap, bidirectional goal-directed
     902048 |    768 |         67 |    90159 | dial, bidirectional goal-directed
Wollte mal nachfragen ob das bei jemand anderem auch aufgetreten ist und ob eine Lösung gefunden wurde. Falls nicht werde ich diese Variante wohl wieder entfernen müssen :|.

Irgendwie wundert mich auch ein wenig, wieso hier so wenig diskutiert wird, vor allem wenn man sich den Thread mit der anderen Programmieraufgabe ansieht ^^. Sind schon alle fertig und hatten keine Probleme oder wollen es alle auf den letzten Drücker machen? ;)

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

Re: Praktikum 2

Beitrag von MisterD123 »

wir sind ziemlich fertig, sind aber die kombination aus zielgerichtet und bidirektional nicht angegangen ;P

die genannten weglängen kann ich auch bestätigen.

hat mal wer größere wege ausprobiert? sowas wie 1 nach 900 000 auf FLA.sp? :>

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

Re: Praktikum 2

Beitrag von zimpfer »

Ich wollte eine Kombination aus bidirektional und zielgerichtet machen, aber dann ist mir nach einigen falschen Ergebnissen aufgefallen, dass es garnicht funktionieren kann. (Zumindest nicht, wenn man von Start- und Zielknoten aus bidirektional zielgerichtet zum Ziel- bzw. Startknoten navigiert und abbricht, sobald irgendein Knoten in der forward und der backward-Menge ist)

Die 2-3 Stunden die ich dafür investiert habe, hätte ich mir echt sparen können, des es ist doch ziemlich offensichtlich, dass es nicht immer korrekt funktioniert...

Bei den PQ-OPs hatte ich nur bei bidirektionaler Suche eine Abweichung gegenüber den Folien

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

Re: Praktikum 2

Beitrag von MisterD123 »

die exakt gleiche anzahl der PQ ops ist nichtmal aussagekräftig. Unsere Buckets zB funktionieren stack-artig, das heißt wenn du 5 elemente reinpackst mit gleicher priorität kommen sie rückwärts wieder raus. unser heap macht das nicht, das heißt je nach dem welche von den beiden PQs du verwendest kommen verschiedene verarbeitungsreihenfolgen raus und damit verschieden mengen an pq operationen.

Antworten

Zurück zu „Effiziente Graphenalgorithmen“