Mathesis Wiki

Die Simulation arbeitet mit mehreren Schleifen, die wie folgt agieren:

1. Für jeden Zug wird überprüft, wie viel Platz vor ihm ist, den er einnehmen darf (Zugfolgeabstand!)
   1. Dies übernimmt die Funktoin streckefrei(), die den freien Weg oder -1 für eine freie Strecke zurückliefert
2. Dementsprechend wird die Geschwindigkeit angepasst: Es wird so dicht aufgefahren wie möglich und dann die Geschwindigkeit an den Vordermann angepasst
3. Nachdem alle Geschwindigkeiten angepasst wurden, werden die Züge eine Zeiteinheit weiter nach vorne gesetzt
4. Dies wird wiederholt, bis alle Züge das Streckenende erreicht haben
5. 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

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<streckenlaenge-EPSILON:
             trajectory_new.extend( kombiniere( zug, t, trajectory, abstand=abstand, streckenlaenge=streckenlaenge ) )
 
    elif abs( position( trajectory, anfangszeit ) - (zug['ort'] + abstand) ) <= EPSILON:
        ind = index( trajectory, anfangszeit )
        #print "= ", trajectory, zug, anfangszeit, ind
        if ind < len( trajectory ) - 1:
            t0, x0 = trajectory[ind] 
            t1, x1 = trajectory[ind + 1]
            v= (x1-x0)/(t1-t0)
            if zug['vavg']>=v:
                trajectory_new = [(t1, x1 - abstand)]
                zug['ort'] = x1 - abstand
                trajectory_new.extend( kombiniere( zug, t1, trajectory, abstand=abstand, streckenlaenge=streckenlaenge ) )
            else:
                t, x, i0 = trifft( anfangszeit+EPSILON, zug['ort'], zug['vavg'], trajectory, abstand, streckenlaenge )    
                trajectory_new = [(t, x)]
                zug['ort'] = x
                if x<streckenlaenge-EPSILON:
                    trajectory_new.extend( kombiniere( zug, t, trajectory, abstand=abstand, streckenlaenge=streckenlaenge ) )
        else:
            trajectory_new = [(anfangszeit + (streckenlaenge - zug['ort']) / zug['vavg'], streckenlaenge)]
    elif position(trajectory, anfangszeit)>= streckenlaenge:
        trajectory_new=[]
        print "DAS SOLLTE NICHT PASSIEREN"
    return trajectory_new
 
 
def berechnen(optimum, abstand=1500, streckenlaenge=20000):
    '''Setzt voraus, dass die Orte zur Reihenfolge kompatibel sind,
	d.h.  für optimum = [... zug1 ... zug2 ... ]
	ist zug1['ort']>= 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