Discussion:
Dijkstra-Implementierung mit theoretischer Fehlerquelle
(zu alt für eine Antwort)
Christian H. Kuhn
2018-01-04 17:44:50 UTC
Permalink
Hallo Gemeinde (oder was davon noch übrig ist),

Nach längerem Rumprobieren habe ich meinen Dijkstra-Algorithmus
implementiert. Es gibt eine Stelle, an der es zufällig noch nicht zu
(erkennbaren) Fehlern gekommen ist. Ich kann aber nicht garantieren,
dass das so bleibt. Vielleicht hat ja jemand ne Idee ...

Beschreibung in Pseudo, echter Code auf
http://www.qno.de/gitweb/?p=qtraviancornoptimator.git;a=snapshot;h=1a18c3c9a93a90fdb4be347e070f68b5c117652a;sf=tgz

int iMax, int sMax identifizieren das konkrete Problem, sind also quasi
die Kommandozeilenparameter und in einem konkreten Durchlauf für alle
Knoten gleich.

Knoten:
int[iMax] id mit der Randbedingung, dass die Summe aller Einträge sMax
nicht überschreiten darf.
double time übernimmt die Rolle des Abstands.
Zur späteren Ermittlung der Lösung wird auch der Vorgänger sowie die vom
Vorgänger herführende Kante gespeichert.

Die Menge der Kanten wird nicht explizit dargestellt. Jeder Knoten kennt
die von ihm ausgehenden Kanten über eine Funktion List<Kante>
getErlaubteKanten().

Jeder Knoten hat eine „Produktivitätsfunktion“, die von id abhängt. Sie
gibt an, wieviele Kosteneinheiten (siehe Kante) pro Zeiteinheit erzeugt
werden. double prod().

Erlaubte Kanten: 0 <= index < iMax mit id[index] != 0.

Kante:
int index
static final double Kante.kosten(index) die vorher bekannten Kosten
einer Kante.

Berechnung der Nachfolgeknoten:
id_neu = id_alt.clone(); id_neu[index]--; id_neu[index+1]++;
time_neu = time_alt + kosten(index)/prod_alt;

Soweit das Modell. Jetzt Dijkstra:

TreeMap<Knoten, Knoten> besuchteKnoten;
TreeMap<Knoten, Knoten> nichtBesuchteKnoten;
TreeMap<Double, Knoten> warteSchlange;

Solange warteSchlange nicht leer ist, wird der erste Knoten (mit
minimaler time) als knoten entnommen und über remove(knoten.time)
gelöscht. Der Knoten wird aus nichtBesuchteKnoten über remove(knoten)
gelöscht. Er wird mit put(knoten, knoten) in besuchte Knoten eingetragen.

for (kante : knoten.getErlaubteKanten) {
Ich iteriere über die erlaubten Kanten. Für die jeweils betrachtete
Kante berechne ich den Folgeknoten folgeKnoten. Ist der in besuchte
Knoten enthalten, continue;

Ist er in nichtBesuchteKnoten nicht enthalten, wird er dort mit
put(folgeKnoten, folgeKnoten) und in warteSchlange mit
put(folgeKnoten.time, folgeKnoten) eingetragen.

Ist er in nichtBesuchteKnoten enthalten, wird sein dortiger Zustand
alterFolgeKnoten = nichtBesuchteKnoten.get(folgeKnoten) abgefragt. Ist
folgeKnoten time >= alterFolgeKnoten.time, continue. Ansonsten
nichtBesuchteKnoten.remove(alterFolgeKnoten),
warteSchlange.remove(alterFolgeKnoten.time). Neuer Knoten wird wie oben
eingetragen.
}

Funktioniert. Die Rechenzeit ist erträglich, schneller wäre besser.
Komisch, das Navi kann das bei mehr Knoten und mehr Kanten schneller ;-)
Theoretisch könnten aber zwei Knoten, die noch in der Warteschlange
sind, beide die gleiche time haben, und wenn ich den zweiten eintrage,
ist der erste dort gelöscht. Der erste wird folglich niemals besucht.
Das kann fatal sein, wenn er Teil der Lösung ist. Ich könnte den
zurückgegebenen Knoten abfragen und bei fehlender Identität mit
unwesentlich veränderter time wieder einfügen (wie toggelt man denn das
least significant bit eines double?).

Ich würde gerne eine Implementation finden, in der nichtBesuchteKnoten
und warteSchlange dieselbe Datenstruktur sind. Ich muss Knoten in dieser
Struktur sowohl über id als auch über time zugreifen können.
Baumstrukturen können nur nach einem von beiden sortiert sein, wo ich
Zugriffszeit von O(log n) habe, nach dem anderen muss ich in O(n)
suchen. Eine Datenstruktur, in der ich sowohl in der natürlichen Ordnung
als auch nach Comparator in O(log n) suchen kann gibt es nicht zufällig? :-)

Ein anderer Ansatz wäre eine Struktur für warteSchlange, die gleiche
time erlaubt. Z.B. aus JavaFX eine SortedList<Knoten> mit einem
passenden Comparator. Die hat aber kein eigenes remove(Knoten), das
läuft auf die darunterliegende ObservableList, also eine ArrayList, und
die braucht lineare Zeit. Damit komme ich sehr schnell in unrealistische
Rechenzeiten.
Christian H. Kuhn
2018-01-04 23:23:21 UTC
Permalink
Ich bin mir nicht sicher, ob ich genügend Verwirrung gestiftet habe.
Post by 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.
Christian H. Kuhn
2018-01-05 11:02:04 UTC
Permalink
Bei mir hat sich die Verwirrung gelegt. Daher die Doppel-Ingrid.
Post by Christian H. Kuhn
Ich bin mir nicht sicher, ob ich genügend Verwirrung gestiftet habe.
Post by Christian H. Kuhn
TreeMap<Knoten, Knoten> nichtBesuchteKnoten;
TreeMap<Double, Knoten> warteSchlange;
Map<Knoten, Knoten> besuchteKnoten;

Da gehts schon los: Ich wollte (zu Recht) den Graphen nicht vorher
komplett berechnen und habe dabei den Überblick verloren. Ich glaubte,
nichtBesuchteKnoten und warteSchlange seien beides die
Prioritätswarteschlange. Sind sie nicht. besuchteKnoten und
nichtBesuchteKnoten bilden gemeinsam den Graphen, warteSchlange die
Warteschlange. Nachdem das klar war:

TreeMap<Knoten, Knoten> graph;
PriorityQueue<Knoten> warteSchlange;

Zum anderen war mir nicht an jeder Stelle klar, dass beide Strukturen
nicht unabhängige Elemente, sondern Zeiger auf das jeweils gleiche
Element erhalten.

Jetzt habe ich eine saubere Trennung von Graph und Warteschlange sowie
einige unnötige remove-add-Kombinationen entfernt, das hat der Laufzeit
gut getan. Dem Code und meinem Hirn auch :-)

lg
QNo
Patrick Roemer
2018-01-05 11:57:49 UTC
Permalink
Responding to Christian H. Kuhn:

Ich habe dieses mehrteilige Epos nur überflogen, kann also gut sein,
dass ich was übersehen und/oder falsch verstanden habe...
Post by Christian H. Kuhn
TreeMap<Knoten, Knoten> graph;
Was soll das denn darstellen?

Die Kanten doch wohl eher nicht, oder hat jeder Knoten nur eine
ausgehende Kante?

Die Menge aller Knoten? Da gibt's mit Set einen passenderen Typ.
Post by Christian H. Kuhn
PriorityQueue<Knoten> warteSchlange;
Mit einer PriorityQueue hast Du aber doch kein gezieltes #remove()...?
Mit unveränderlichen Knoten wahrscheinlich nicht dramatisch - man
bekommt halt Duplikate, aber da eh nur der Eintrag mit der kürzesten
Distanz interessiert, stören die nicht, abgesehen davon, dass sie
Speicher fressen. Aber es klang so, als ob Deine Knoten mutable seien,
und dass Du ein O(n)-Traversal zwecks Removal vermeiden wolltest. Wie
passt das denn zusammen?

Viele Grüße,
Patrick
Christian H. Kuhn
2018-01-07 19:57:43 UTC
Permalink
Post by Patrick Roemer
Ich habe dieses mehrteilige Epos nur überflogen, kann also gut sein,
dass ich was übersehen und/oder falsch verstanden habe...
Scheint alles zu passen.
Post by Patrick Roemer
Post by Christian H. Kuhn
TreeMap<Knoten, Knoten> graph;
Die Menge aller Knoten? Da gibt's mit Set einen passenderen Typ.
Set<E> hat kein get(E e). Daher (kam die Idee von Michael oder hab ichs
ergoogelt?) Map<E, E>, einfügen von e mit put(e,e), und schon kann ich
ein E mit get(e) bekommen. Ok, ist von der Semantik her schräg, weils
einmal Key und einmal Value ist. Ich bin offen für besseres.
Post by Patrick Roemer
Post by Christian H. Kuhn
PriorityQueue<Knoten> warteSchlange;
Mit einer PriorityQueue hast Du aber doch kein gezieltes #remove()...?
Mit unveränderlichen Knoten wahrscheinlich nicht dramatisch - man
bekommt halt Duplikate, aber da eh nur der Eintrag mit der kürzesten
Distanz interessiert, stören die nicht, abgesehen davon, dass sie
Speicher fressen. Aber es klang so, als ob Deine Knoten mutable seien,
und dass Du ein O(n)-Traversal zwecks Removal vermeiden wolltest. Wie
passt das denn zusammen?
Die Duplikate stören halt wirklich nicht. Objekte SIND mutable. Das
Sortierkriterium kann sich aber nur verringern. Ich füge dann das neue
Objekt (es ist ja nur der Zeiger darauf, das ist nicht viel Speicher)
ein. Es wird auf jeden Fall VOR dem alten Eintrag eingefügt (kann auch
sein, dass der alte Eintrag durch das Einfügen nach vorne gespült wird
und beide jetzt direkt hintereinander stehen) und als besucht
gekennzeichnet. Beide Einträge zeigen aufs richtige Objekt, haben die
aktuell richtige Distanz. Sobald der erste drankommt, wird das Objekt
als besucht gekennzeichnet. Das wird beim zweiten Eintrag erkannt, der
wird dann ohne weitere Bearbeitung verworfen. Dirty, aber quick genug.

Einzige Lösung, die bei Änderung mutabler Objekte umsortiert, ist mW die
SortedList von JavaFX. Hab jedenfalls nichts anderes gefunden. Getestet.
Laufzeit erhöht sich um Faktor 10. Verworfen. Auch hier bin ich offen
für besseres.

lg
QNo

Lesen Sie weiter auf narkive:
Loading...