Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > de.comp.lang.java > #13158

Re: Dijkstra-Implementierung mit theoretischer Fehlerquelle

Show all headers | View raw

Ich bin mir nicht sicher, ob ich genügend Verwirrung gestiftet habe.
Also mache ich mal die Ingrid:

Am 04.01.2018 um 18:44 schrieb Christian H. Kuhn:
> TreeMap<Knoten, Knoten> nichtBesuchteKnoten;
> TreeMap<Double, Knoten> warteSchlange;

Ursprünglicher Ansatz war: nichtBesuchteKnoten und warteSchlange sind
dieselbe Struktur. Zur Implementierung habe ich TreeMap benutzt; TreeSet
oder irgendeine Implementierung von List gibt mir kein get(knoten). Ich
habe darauf zwei Arten von Zugriff:

1. Ich entnehme den Knoten mit kleinster Distanz time, also
pollFirstEntry().

2. Ich habe für einen betrachteten Knoten eine Liste gerade erzeugter
Folgeknoten. Für die brauche ich: contains(knoten), get(knoten),
remove(knoten), add(knoten) (oder put).

Für 1. brauche ich eine Sortierung nach time. Java’s TreeMap gibt mir
firstEntry() mit O(1) und remove(knoten) mit O(log n). Aber dann kann es
in 2. z.B. passieren, das der neu erzeugte Folgeknoten eine andere time
hat als der bisher enthaltene und an einer ganz anderen Stelle gesucht
wird. Ich müsste also linear suchen mit O(n). Damit wäre 2. ziemlich
langsam.

Für 2. brauche ich eine Sortierung nach id[]. Damit bekomme ich alle in
2. benötigten Operationen mit O(log n), dafür finde ich das kleinste
Element nur mit linearer Suche mit O(n). Das firstEntry() von 1. wird
langsam, das folgende remove geht aber wieder in O(log n).

2. wird öfter ausgeführt als 1., daher würde ich bei EINER Struktur nach
id[] sortieren und für firstEntry() in den sauren Apfel beißen.

Wie beschrieben bei getrennten Strukturen laufen alle Operationen mit
O(log n), und zweimal O(log n) ist schneller als einmal O(n) (jedenfalls
im Grenzwert, und um den geht es ja bei Landau).

Eine Idee ist, warteSchlange als zusätzlichen Index auf
nichtBesuchteKnoten zu nehmen. Der Index müsste dann aber bei jeder
Änderung aktualisiert werden, und das kann dauern. Also richte ich
warteSchlange nicht als Index, sondern als eigene Struktur ein.

Im bisher angewandten Verfahren kenne ich für schon in
nichtBesuchteKnoten enthaltene Knoten nicht nur den neuen, sondern auch
den alten Wert von time. Ich kann also bei benötigtem Update in O(log n)
das entsprechende Element aus warteSchlange entfernen und mit korrektem
Wert wieder einsetzen.

Allerdings kann es beim Einfügen dazu kommen, dass warteSchlange schon
einen anderen Knoten mit genau gleicher time enthält, der überschrieben
wird. TreeMap.remove(key) gibt value zurück, ich müsste den entfernten
Knoten mit knapp veränderter time wieder einfügen. Das Einfügen dürfte
für Zeitbetrachtungen zu vernachlässigen sein, aber die Überprüfung bei
jedem Einfügen dürfte die ohnehin nicht überwältigende Laufzeit nicht
verbessern.

Back to de.comp.lang.java | Previous | Next — Previous in thread | Next in thread | Find similar

Thread

Dijkstra-Implementierung mit theoretischer Fehlerquelle "Christian H. Kuhn" <qno-news@qno.de> - 2018-01-04 18:44 +0100
  Re: Dijkstra-Implementierung mit theoretischer Fehlerquelle "Christian H. Kuhn" <qno-news@qno.de> - 2018-01-05 00:23 +0100
    Re: Dijkstra-Implementierung mit theoretischer Fehlerquelle "Christian H. Kuhn" <qno-news@qno.de> - 2018-01-05 12:02 +0100
      Re: Dijkstra-Implementierung mit theoretischer Fehlerquelle Patrick Roemer <sangamon@netcologne.de> - 2018-01-05 12:57 +0100
        Re: Dijkstra-Implementierung mit theoretischer Fehlerquelle "Christian H. Kuhn" <qno-news@qno.de> - 2018-01-07 20:57 +0100

csiph-web