Path: csiph.com!fu-berlin.de!uni-berlin.de!individual.net!not-for-mail From: "Christian H. Kuhn" Newsgroups: de.comp.lang.java Subject: Dijkstra-Implementierung mit theoretischer Fehlerquelle Date: Thu, 4 Jan 2018 18:44:50 +0100 Lines: 92 Message-ID: Mime-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: 8bit X-Trace: individual.net 2P+F00GOgU1wBc0+bhBlbgMiT55BDcu7J8nClD77INassEl9U= Cancel-Lock: sha1:OGu+VYowU6jecUNOal/S5FW6tyk= X-Mozilla-News-Host: snews://news.individual.net:563 User-Agent: Mozilla/5.0 (Windows NT 10.0; WOW64; rv:52.0) Gecko/20100101 Thunderbird/52.5.0 Xref: csiph.com de.comp.lang.java:13157 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 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 besuchteKnoten; TreeMap nichtBesuchteKnoten; TreeMap 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 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.