Übung 6 - Zielgerichtete Suche

[sge]

Hallo,
wie heute in der Vorlesung angesprochen gibt es doch das Problem, dass die Konsistenz-Bedingung der unteren Schranke (in den Beispielgraphen) nicht immer erfüllt ist.
Dadurch entstehen negative Kantengewichte c'.
Das Problem bei der Dial-Implementierung (mit Modulo) ist dann folgendes:
Durch die negativen Kantengewichte werden die Knoten in falsche Buckets eingefügt. (Obersavtion 47 ist ja verletzt)

Wie sollen wir jetzt mit diesem Problem umgehen?

Ps(zu einem anderen Thema): Wie sieht das jetzt mit den Messpunkten für die Zeitnahmen aus? Welche Transformationen sollen bei der Zeitnahme eingeschlossen sein?

[Stille]

Hallo,

ich kann gerade nicht genau sagen, was an den Daten falsch ist. Benutzen Sie für's erste in der Umrechnung (vorletzte Zeile)

Code: Alles auswählen

dist*=7.3;

anstatt

Code: Alles auswählen

dist*=10.0;

.

Damit wird zumindest nichts mehr negativ. Falls ich noch mehr herausfinde, melde ich mich noch einmal.

Was die Zeitmessung angeht, so würde ich sagen, daß alles ausser Eingabe, Ausgabe und Tranformation der Kantengewichte in die Zeitmessung eingehen sollte. Dies sind einmalige Operationen, die man im Normalfall ins Pre- bzw. Postprocessing packen würde.

[sge]

Danke für die Infos.

Ich habe gerade mal einen Test auf dem Graphen FLA.sp von Knoten 0 nach Knoten 42 ausgeführt, bei dem alle Varianten 20mal ausgeführt wurden. Dabei sind sie Abweichungen der Laufzeiten enorm, auch wenn mein PC nicht anderweitig belastet wurde.
Ich hab' die Ausgabe mal per Hand etwas modifiziert und den Worst- und Best-Case eingefügt:

Code: Alles auswählen

     d(s,t) | bestCase   time(ms) | worstCase  time(ms) |              PQ-ops | params
-----------------------------------------------------------------------------------------------
    4256215 |           71,987503 |          807,218248 |              187368 | heap
    4256215 |          127,336777 |         1045,023322 |              278006 | heap, bidir
    4256215 |           29,819641 |          657,735977 |               67196 | heap, goaldir
    4256215 |           78,258413 |          226,502453 |              187368 | dial
    4256215 |          428,925120 |         1149,923319 |              278006 | dial, bidir
    4256215 |           33,729709 |           54,484646 |               67196 | dial, goaldir
    4256215 |          485,297711 |         2716,874911 |                   - | JGraphT
-----------------------------------------------------------------------------------------------

(Anmerkung: Ausführung auf einem 2x2.0GHz Intel Core 2 Duo | Java 1.6.0.15)

Kann mir jemand die Anzahl der PQ-ops bestätigen und evtl. mal sagen, ob die Zeiten ähnlich sind(zumindest im Verhältnis untereinander)?
Es sollte doch, so wie in der Aufstellung oben zu erkennen, auch immer die gleiche Anzahl an delete-min Operationen ausgeführt werden, egal ob MinBinHeap, oder Dial verwendet wird, oder?

[v0id]

Hm... also bei mir kommt komplett was anderes raus.
Allerdings stimmen ja die Größenverhältnisse und ich habe nur die
extractMin-Operationen gezählt, also nicht decreaseKey oder containsKey,
weil das ja so auf dem Blatt stand.
Bei der bidirektionalen Suche hängt die Anzahl auch von der Auswahl der Suchrichtung in der nächsten Iteration ab.
Mich wundert auch sehr, dass deine bidirektionale Suche mehr Operationen benötigt als die einfache Suche.
Wer weis, ob das bereits so stimmt was wir da gebastelt haben.
Mich würde auch mal ein Beispiel interessieren, für einen tatsächlichen kürzesten Weg,
um mal die eigenen daran Algorithmen überprüfen zu können.
Könnten Sie uns vielleicht so etwas zurverfügungstellen, Herr Stille?

Code: Alles auswählen

  d(s,t) |runtime(ms) |PQ-Ops |                               params |
---------------------------------------------------------------------
5122525 |       1094 |808361 |      standard dijkstra, leftist heap |
5122525 |        797 |808361 |     standard dijkstra, dials buckets |
5122525 |        703 |204298 |                     A*, leftist heap |
5122525 |        625 |204298 |                    A*, dials buckets |
5122525 |        594 |374166 | bidirectional dijkstra, leftist heap |
5122525 |        532 |374166 |bidirectional dijkstra, dials buckets |
5122525 |        734 |143608 |       bidirectional A*, leftist heap |
5122525 |        516 |143608 |      bidirectional A*, dials buckets |

Edit:
Beim Suchlauf mit NYC.sp -s 1 -t 9990 -a reicht der Faktor 7.3 bei mir zumindestens bei bidirektionaler zielgerichteter Suche zum Herstellen der Zulässigkeit nicht aus.
Es stimmt dann erst mit dist*=7.03 oder kleiner...

[sge]

Sorry, mein Fehler!
Hatte den falschen Graphen angegeben... Hatte das auf COL ausgeführt.
auf FLA sieht es hingegen folgendermaßen aus:

Code: Alles auswählen

                                             d(s,t) |            time(ms) |              PQ-ops | params
-------------------------------------------------------------------------------------------------------
                                            5122525 |         1554,964877 |              808360 | heap
                                            5122525 |         1557,172704 |              374166 | heap, bidir
                                            5122525 |         1076,134672 |              204297 | heap, goaldir
                                            5122525 |          381,244743 |              808360 | dial
                                            5122525 |          737,789447 |              374165 | dial, bidir
                                            5122525 |          120,567002 |              204297 | dial, goaldir
                                            5122525 |         7029,312382 |                   - | JGraphT
---------------------------------------------------------------------------------------------------------------------------------

[v0id]

Dann siehts doch schon mal gut aus

[v0id]

Trotz des Faktors 7.3 werden immer noch Kanten überschätzt.
Das betrifft die folgenden Kanten:

Code: Alles auswählen

Lese Graphdatei 'NYC.sp'  ...
Edge(64654,64665) - edgeLength: 1 estimateLength: 1,020
Edge(64665,64654) - edgeLength: 1 estimateLength: 1,020
Edge(83195,83185) - edgeLength: 1 estimateLength: 1,021
Edge(83185,83195) - edgeLength: 1 estimateLength: 1,021

Lese Graphdatei 'COL.sp' ...
Edge(167820,166516) - edgeLength: 1 estimateLength: 1,031
Edge(166516,167820) - edgeLength: 1 estimateLength: 1,031
Edge(278264,278256) - edgeLength: 1 estimateLength: 1,038
Edge(278256,278264) - edgeLength: 1 estimateLength: 1,038
Edge(286908,286906) - edgeLength: 1 estimateLength: 1,017
Edge(286906,286908) - edgeLength: 1 estimateLength: 1,017
Edge(421857,421858) - edgeLength: 1 estimateLength: 1,020
Edge(421858,421857) - edgeLength: 1 estimateLength: 1,020

Lese Graphdatei 'FLA.sp' ...
Edge(2563,2997) - edgeLength: 1 estimateLength: 1,074
Edge(2997,2563) - edgeLength: 1 estimateLength: 1,074
Edge(148359,148324) - edgeLength: 1 estimateLength: 1,077
Edge(148324,148359) - edgeLength: 1 estimateLength: 1,077
Edge(149985,149984) - edgeLength: 1 estimateLength: 1,077
Edge(149984,149985) - edgeLength: 1 estimateLength: 1,077
Edge(164773,164776) - edgeLength: 1 estimateLength: 1,077
Edge(164776,164773) - edgeLength: 1 estimateLength: 1,077
Edge(210914,230111) - edgeLength: 1 estimateLength: 1,072
Edge(230111,210914) - edgeLength: 1 estimateLength: 1,072
Edge(334054,334055) - edgeLength: 1 estimateLength: 1,082
Edge(334055,334054) - edgeLength: 1 estimateLength: 1,082
Edge(543141,543142) - edgeLength: 1 estimateLength: 1,077
Edge(543142,543141) - edgeLength: 1 estimateLength: 1,077
Edge(543142,543141) - edgeLength: 1 estimateLength: 1,077
Edge(543141,543142) - edgeLength: 1 estimateLength: 1,077
Edge(557250,557260) - edgeLength: 1 estimateLength: 1,085
Edge(557260,557250) - edgeLength: 1 estimateLength: 1,085
Edge(632285,604652) - edgeLength: 1 estimateLength: 1,092
Edge(604652,632285) - edgeLength: 1 estimateLength: 1,092
Edge(657159,653325) - edgeLength: 1 estimateLength: 1,070
Edge(653325,657159) - edgeLength: 1 estimateLength: 1,070
Edge(784992,784993) - edgeLength: 1 estimateLength: 1,081
Edge(784993,784992) - edgeLength: 1 estimateLength: 1,081
Edge(814433,814434) - edgeLength: 1 estimateLength: 1,082
Edge(814434,814433) - edgeLength: 1 estimateLength: 1,082
Edge(918980,918981) - edgeLength: 1 estimateLength: 1,070
Edge(918981,918980) - edgeLength: 1 estimateLength: 1,070
Edge(926754,926690) - edgeLength: 1 estimateLength: 1,085
Edge(926690,926754) - edgeLength: 1 estimateLength: 1,085
Edge(1001666,1001665) - edgeLength: 1 estimateLength: 1,076
Edge(1001665,1001666) - edgeLength: 1 estimateLength: 1,076
Edge(1013612,994651) - edgeLength: 1 estimateLength: 1,078
Edge(994651,1013612) - edgeLength: 1 estimateLength: 1,078

[Stille]

Oh, hatte ich vergessen: ich habe auf die nächst kleinere ganze Zahl abgerundet, da die Kantenlängen ja auch ganzzahlig sind. Dann passt es.

[Stille]

Könnten Sie uns vielleicht so etwas zurverfügungstellen, Herr Stille?

Na klar. Die Weglängen in den Beispielen oben sind sowohl auf COL als auch aus FLA korrekt.

Das in der Vorlesung präsentierte Beispiel war: NYC, von 96008 nach 172944, Länge 900041 dm

Die Laufzeitschwankungen sind in der Tat verwunderlich. Bei mir betragen sie im Einzelfall vielleicht mal 5%, im Normalfall aber <1%. Versuchen Sie es mal auf einer anderen Maschine oder schicken Sie mir ihren Code.