Christian H. Kuhn
2018-01-04 17:44:50 UTC
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.
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.