07-05-2008, Wednesday-20:59:18
Ich seh im Wesentlichen erstmal 2 möglichkeiten.
1. Simutrans wird auf abstand optimiert. Sprich Leute suchen sich den Kürzesten km technischen weg.
Dann wärn alles mit abstand etc. relativ einfach. um auf nen A* baum zu kommen
2. Simutrans wird auf umsteigezeiten + fahrplanhalte optimiert. Wobei es irgendnen faktor > 1 gibt der umsteige * f in fahrplanhalteinheiten umrechnet.
Soweit (wikipedia) brauchen wir kantenlängen. (die lassen sich bei der "verbindung zum nächsten knoten" berechnung aus den fahrplänen der beteiligten konvois errechnen).
Ich müsste noch mehr lesen um zu wissen ob die Kantenlänge von a nach b = der kantenlänge von b nach a sein muss. Was wir in unserem Fall ja nicht haben. (Ein fahrplan mit 3 eintragungen, ermöglicht ne fahrt von a nach b in 1 aber von b nach a brauchts 2 ). Sowie addieren wir zu ner Kantenlänge den globalgleichen Umsteigemalus (der sich aus der Verzögerung beim umsteigen ergibt).
So nun brauchen wir ne Heuristik die berechenbar ist. Das einzige was mir da einfällt ist eben den knotenabstand zu verwenden und mit dem Umsteigemalus zu multiplizieren.
Die Frage ist mehr ob wir so wie A* sucht, es schaffen den Knotenabstand vorrauszuberechnen.
Sonst hätten wir als Notlösung immer noch 0 für den zielpunkt 1 für alle damit verbundenen stationen und 2 für alle anderen, was die Bedingung erfüllt das A* den optimalen Weg findet.
(ich fürchte nur das sowas die Laufzeit ordentlich verhagelt)
Nachtrag:
Ne kleine verbesserung.
herutistik am ziel auf 0
alle mit ziel verbundenen auf 1
evtl start auf 4 (bzw 5 und mit dem start verbundenen auf 4 wobei wir da den A* analysieren müssen wenn wir ihn so betrügen wollen)
A* loslaufen lassen.
alle knoten die mit jemanden mit 1 verbunden sind auf 2
alle anderen auf 3
(hmm ein wenig suboptimal fällt mir gerade auf ich verstecke nur die laufzeit O(k^2) k verbindungen pro knoten in O(k*l) l durchsuchte knoten)
Wieviel Stationen hat so ein Riesenspiel spiel? sonst liesse sich ne n^2 Tabelle mit den Knotenlängen zwischeneinander einführen. Woraus die Heuristik in der passenden Zeile einfach ablesbar ist.
1. Simutrans wird auf abstand optimiert. Sprich Leute suchen sich den Kürzesten km technischen weg.
Dann wärn alles mit abstand etc. relativ einfach. um auf nen A* baum zu kommen
2. Simutrans wird auf umsteigezeiten + fahrplanhalte optimiert. Wobei es irgendnen faktor > 1 gibt der umsteige * f in fahrplanhalteinheiten umrechnet.
Soweit (wikipedia) brauchen wir kantenlängen. (die lassen sich bei der "verbindung zum nächsten knoten" berechnung aus den fahrplänen der beteiligten konvois errechnen).
Ich müsste noch mehr lesen um zu wissen ob die Kantenlänge von a nach b = der kantenlänge von b nach a sein muss. Was wir in unserem Fall ja nicht haben. (Ein fahrplan mit 3 eintragungen, ermöglicht ne fahrt von a nach b in 1 aber von b nach a brauchts 2 ). Sowie addieren wir zu ner Kantenlänge den globalgleichen Umsteigemalus (der sich aus der Verzögerung beim umsteigen ergibt).
So nun brauchen wir ne Heuristik die berechenbar ist. Das einzige was mir da einfällt ist eben den knotenabstand zu verwenden und mit dem Umsteigemalus zu multiplizieren.
Die Frage ist mehr ob wir so wie A* sucht, es schaffen den Knotenabstand vorrauszuberechnen.
Sonst hätten wir als Notlösung immer noch 0 für den zielpunkt 1 für alle damit verbundenen stationen und 2 für alle anderen, was die Bedingung erfüllt das A* den optimalen Weg findet.
(ich fürchte nur das sowas die Laufzeit ordentlich verhagelt)
Nachtrag:
Ne kleine verbesserung.
herutistik am ziel auf 0
alle mit ziel verbundenen auf 1
evtl start auf 4 (bzw 5 und mit dem start verbundenen auf 4 wobei wir da den A* analysieren müssen wenn wir ihn so betrügen wollen)
A* loslaufen lassen.
alle knoten die mit jemanden mit 1 verbunden sind auf 2
alle anderen auf 3
(hmm ein wenig suboptimal fällt mir gerade auf ich verstecke nur die laufzeit O(k^2) k verbindungen pro knoten in O(k*l) l durchsuchte knoten)
Wieviel Stationen hat so ein Riesenspiel spiel? sonst liesse sich ne n^2 Tabelle mit den Knotenlängen zwischeneinander einführen. Woraus die Heuristik in der passenden Zeile einfach ablesbar ist.