Es existieren zwei Versionen des Simulationsprogrammes. Das eine simuliert tatsächlich die einzelnen Zugbewegeungen in einzelnen Zeitschritten, ist jedoch vergleichsweise unperformant. Stefan hat freundlicherweise ein Simulationsprogramm geschrieben, dass die Züge berechnen kann (wann laufen die Züge aufeinander auf usw.) und um ein Vielfaches schneller ist:
5 Züge - Simulation:
0.04804 sec
5 Züge - Berechnen:
0.00107 sec
===== Variante von Jakob =====
Die Simulation arbeitet mit mehreren Schleifen, die wie folgt agieren:
- Für jeden Zug wird überprüft, wie viel Platz vor ihm ist, den er einnehmen darf (Zugfolgeabstand!)
- Dies übernimmt die Funktoin streckefrei(), die den freien Weg oder -1 für eine freie Strecke zurückliefert
- Dementsprechend wird die Geschwindigkeit angepasst: Es wird so dicht aufgefahren wie möglich und dann die Geschwindigkeit an den Vordermann angepasst
- Nachdem alle Geschwindigkeiten angepasst wurden, werden die Züge eine Zeiteinheit weiter nach vorne gesetzt
- Dies wird wiederholt, bis alle Züge das Streckenende erreicht haben
- Bei Ankunft eines Zuges wird die aktuelle Uhrzeit in den key "ankunft" des betreffenden Zuges geschrieben
def streckefrei(i, order): # Zug: Woerterbuch, order = Objekt wie reihenfolge
t = 0
streckebelegt = []
freivoraus = -1
if i > 0:
if order[i - 1]["ankunft"] == -1:
freivoraus = - order[i]["ort"] + order[i - 1]["ort"]
else:
freivoraus = -1
if i == 0:
freivoraus = -1
return freivoraus
def simulieren(optimum, abstand=1500, streckenlaenge=20000):
logger.error( optimum )
reihenfolge = deepcopy( optimum ) # Eingabeliste soll nicht veraendert werden
t = 0 # Abfahrtszeit ist 0
angekommen = 0
for i, zug in enumerate( reihenfolge ):
if i > 0:
zug["vist"] = min( reihenfolge[i - 1]["vist"], zug[
"vavg"] ) - 1 # Es wird vor Programmstart sichergestellt, dass kein Zug schneller ist als sein vorheriger und diesen im ersten Schritt ggf. überholen kann.
while 1 == 1:
for i, zug in enumerate( reihenfolge ):
if zug["ankunft"] == -1: # and t>=zug["abfahrt"]: # Wenn nicht angekommen und abfahrtszeit erreicht
if streckefrei( i, reihenfolge ) == -1:
zug["vist"] = zug["vavg"] # vavg beschreibt die maximale geschwindigkeit des zuges
elif streckefrei( i, reihenfolge ) >= abstand:
if i != 0:
zug["vist"] = min( reihenfolge[i - 1]["vist"], zug["vavg"] )
else:
zug["vist"] = 0
for zug in reihenfolge:
if zug["ankunft"] == -1:
zug["ort"] += zug["vist"]
logger.debug( str( zug["nummer"] ) + " fährt von " + str( zug["ort"] - zug["vist"] ) + " nach " + str(
zug["ort"] ) )
if zug["ort"] > streckenlaenge:
if zug["ankunft"] == -1:
zug["ankunft"] = t
zug["ort"] = streckenlaenge
angekommen += 1
logger.warning( "Ein Zug ist angekommen" )
# print("Zug angekommen")
t = t + 1
if angekommen >= len( reihenfolge ): # simuliere, bis alle Zuege angekommen sind
return reihenfolge
break
===== Variante von Stefan =====
Nun ist es jedoch viel verschenkte Rechenzeit, die Züge Schritt für Schritt zu simulieren, wenn sie a) sehr vorhersehbar unterwegs sind (denn sie können sich ja nicht überholen) und b) nur der Endzustand interessiert, die Zwischensituationen werden nie benötigt.
Stefans Programm arbeitet mit linearer Mathematik, indem es vorausberechnet, wann sich zwei Züge treffen würden und verzichtet somit auf viele Berechungsschritte. Dies ermöglicht das Berechnen auch größerer Probleme in vertretbarer Laufzeit, was mit "Simulieren" nur bedingt der Fall war.
EPSILON = 1e-10
def passiert(trajectory, ort):
'''Gibt den Zeitpunkt und die Intervalnummer i zurück, zu dem
die Trajektorie trajectory den Ort ort passiert.'''
assert trajectory[0][1] < ort
for i, (t1, x1) in enumerate( trajectory ):
if i==len(trajectory)-1:
print " ACHTUNG " ,i, trajectory, ort
t2, x2 = trajectory[i + 1] # ergibt einen Fehler, wenn der Zug
# den Ort nie passiert; gut so.
if x2 >= ort-EPSILON:
v = (x2 - x1) / (t2 - t1)
t = t1 + (ort - x1) / v
break
#print "IN PASSIERT ", trajectory,ort
return t, i
def trifft(t, x, v, trajectory, abstand, streckenlaenge):
'''Gibt Zeitpunkt, Ort zurück, zu dem ein Zug,
der bei t an der Stelle x mit Geschw. v losfährt,
im Abstand abstand zur Trajektorie trajectory
(des vorausfahrenden Zuges) anlangt, sowie den
zugeh. Index der Trajektorie'''
#print "TRAJ", trajectory, t,x,v
for i, (t1, x1) in enumerate( trajectory ):
t2, x2 = trajectory[i + 1]
vv = (x2 - x1) / (t2 - t1)
if x + (t2 - t) * (vv-v) >= x2 - abstand and t2 >= t:
t_treffen = (x2 - abstand - x) / (vv - v) + t
x_treffen = x + (t_treffen - t) * v
#print "IN TREFFEN ", (x2 - abstand - x) / (vv - v) + t, t1,x1,t2,x2,vv,x_treffen, i
return (x2 - abstand - x) / (vv - v) + t, x_treffen, i
if i == len( trajectory ) - 2:
i = -1 ## Zug laeuft frei
## wenn er trajectory nicht
## im letzten Interval trifft.
break
return (streckenlaenge - x) / v + t, streckenlaenge, i-1
def position(trajectory, tt):
pos = trajectory[0][1]
for i, (t0, x0) in enumerate( trajectory ):
if i == len( trajectory ) - 1:
break
t1, x1 = trajectory[i + 1]
if t0 < tt <= t1:
pos = x0 + (x1 - x0) / (t1 - t0) * (tt - t0)
return pos
if tt > trajectory[-1][0]:
pos = trajectory[-1][1]
return pos
def index(trajectory, tt):
index = -1
for i, (t0, x0) in enumerate( trajectory ):
if i == len( trajectory ) - 1:
break
t1, x1 = trajectory[i + 1]
if t0 <= tt < t1:
return i
index = len( trajectory )-1
return index
def kombiniere(zug, anfangszeit, trajectory, abstand=1500, streckenlaenge=20000):
'''Bestimmt die Trajektorie eines Zugs anhand der
Trajektorie des vorausfahrenden Zugs.
Argumente:
zug Zug - Dictionary
trajectory Liste von Tupeln (Zeitpunkt, Ort),
das letzte Tupel ist (Ankunftszeit, Streckenlaenge)
das erste (0, Anfangsort)
'''
if zug['ort']>=streckenlaenge-EPSILON:
return []
elif zug['ort']+abstand>=streckenlaenge-EPSILON:
return [(anfangszeit+(streckenlaenge-zug['ort'])/zug['vavg'],streckenlaenge)]
elif (position( trajectory, anfangszeit ) < streckenlaenge) and (position(trajectory,anfangszeit) +EPSILON< zug['ort'] + abstand):
#print "EINGANG" ,position( trajectory, anfangszeit ) , zug['ort'] + abstand
t, i0 = passiert( trajectory, zug['ort'] + abstand )
x = zug['ort']
#print "< ", zug, trajectory, t, i0, anfangszeit
trajectory_new = [(t, x)]
trajectory_new.extend( kombiniere( zug, t, trajectory, abstand=abstand, streckenlaenge=streckenlaenge ) )
elif position( trajectory, anfangszeit ) > zug['ort'] + abstand + EPSILON:
#print "> EINGANG", anfangszeit, zug['ort']
t, x, i0 = trifft( anfangszeit, zug['ort'], zug['vavg'], trajectory, abstand, streckenlaenge )
#print ">", trajectory, zug, t, x, i0, anfangszeit
trajectory_new = [(t, x)]
zug['ort'] = x
if x= zug2['ort']
Setzt NICHT voraus, dass alle Züge am Ausgangsbahnhof (ort=0)
losfahren. '''
reihenfolge = deepcopy( optimum )
for i, zug in enumerate( reihenfolge ):
if i == 0:
trajectories = [[(0, zug['ort']), ((streckenlaenge - zug['ort']) / zug['vavg'], streckenlaenge)]]
zug['ankunft'] = trajectories[-1][-1][0]
zug['ort'] = streckenlaenge
else:
# trajectory.append([(0,zug['ort'])])
last_traj=trajectories[-1]
trajectories.append([(0,zug['ort'])]+kombiniere( zug, 0, last_traj, abstand=abstand, streckenlaenge=streckenlaenge ) )
zug['ankunft'] = trajectories[-1][-1][0]
zug['ort'] = streckenlaenge
#print trajectories
return reihenfolge