Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen gezeigt.

--- ws1516:logistische_probleme:simulationsprogramm [2016/02/24 15:13]
jakobfaustus angelegt
+++ ws1516:logistische_probleme:simulationsprogramm [2016/05/10 14:46] (aktuell)
@@ Zeile 22: / Zeile 22: @@
 <code python>
-t = 0
-streckebelegt = []
 def streckefrei(i, order):  # Zug: Woerterbuch, order = Objekt wie reihenfolge
+t = 0
+streckebelegt = []
     freivoraus = -1
     if i > 0:
@@ Zeile 81: / Zeile 81: @@
 ===== 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.
+<code python>
+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
+</code>

Mathesis Wiki

Benutzer-Werkzeuge

Webseiten-Werkzeuge

Unterschiede

Seiten-Werkzeuge