Ich werde vorstellen, wie man die kürzeste Route in der Grafik findet, auf der sich die Reisezeit wahrscheinlich ändert.

Erstellen Sie ein Beispieldiagramm.

python3

%matplotlib inline
import numpy as np, networkx as nx

m = 4
g = nx.Graph()
for i in range(m):
    if i==0:
        g.add_edge(i, i+m, prob=[1], time=[1.9]) # 0-> 4
    else:
        g.add_edge(i, i+m, prob=[0.8, 0.2], time=[1, 6]) #Vertikal
    if i < m-1:
        g.add_edge(i, i+1, prob=[1], time=[2]) #Seite
        g.add_edge(i+m, i+m+1, prob=[1], time=[2]) #Seite

n = g.number_of_nodes()
pos = {i:[i%m, i//m] for i in range(n)}
nx.draw_networkx_nodes(g, pos, node_color='w')
nx.draw_networkx_edges(g, pos)
nx.draw_networkx_labels(g, pos, {i:str(i) for i in range(n)});

--Finden Sie die kürzeste Route ** von Punkt 0 bis Punkt 7 oben. ――Die Nebenstraße dauert definitiv 2 Stunden. ――Die vertikale Straße dauert 1 Stunde mit einer Wahrscheinlichkeit von 80%, aber 6 Stunden mit einer Wahrscheinlichkeit von 20%. Es dauert durchschnittlich 2 Stunden.

• Die Punkte 0 bis 4 können definitiv in 1,9 Stunden erreicht werden. ――Wenn Sie einen bestimmten Punkt erreichen, wird nur die Bewegungszeit der mit diesem Punkt verbundenen Seite festgelegt.

In Bezug auf die durchschnittliche Zeit ist die Route "0-> 4-> 5-> 6-> 7" und 7,9 Stunden ist die kürzeste Route.

Auf einer vertikalen Straße können Sie jedoch mit einer Chance von 80% in einer Stunde von unten nach oben fahren. Aus diesem Grund scheint die Politik des Aufstiegs gut zu sein, wenn Sie in 1 Stunde vertikal gehen, während Sie nach rechts gehen.

Erfundene Monte-Carlo-Dyxtra-Methode

――Vorbereiten Sie nn Zufallszahlen für jede Seite, die durch die Wahrscheinlichkeit im Voraus bestimmt werden. --Stellen Sie die Zeit bis zum Erreichen des Endpunkts an allen Punkten auf ∞ ein und lassen Sie alle Punkte nicht durchsucht.

• Setzen Sie den nächsten Punkt als Endpunkt und setzen Sie die Ankunftszeit des nächsten Punktes auf 0.
• Wiederholen Sie die folgenden Schritte, bis der Startpunkt gesucht wurde.
• Markieren Sie die folgenden Punkte wie gesucht.
• Aktualisieren Sie die Ankunftszeit des Verbindungspunkts zum nächsten Punkt wie unten beschrieben.
• Unter den Punkten, die nicht durchsucht wurden, wird derjenige mit der kürzesten Ankunftszeit als nächster Punkt festgelegt.

Zeitaktualisierung erreichen

--Update, wenn der Durchschnitt der nn-Zeiten der folgenden Stichprobenwerte kürzer als die aktuelle Ankunftszeit ist. --Für den Punkt, an dem der Beispielwert verbunden werden soll, stellen Sie ihn als Mindestwert für "Summe aus Ankunftszeit und Verbindungszeit" ein.

Versuche zu berechnen

python3

def monte_min(g, s, t, nn=1000):
    n = g.number_of_nodes()
    dd = [np.inf] * n
    bb = [False] * n
    for i, j in g.edges():
        d = g.edge[i][j]
        d['log'] = (np.random.multinomial(1, d['prob'], nn) * d['time']).sum(axis=1)
    nx = t
    dd[nx] = 0
    while not bb[s]:
        bb[nx] = True
        for nd in g.edge[nx].keys():
            dd[nd] = min(dd[nd], np.mean([calcmin(dd, g.edge[nd], i) for i in range(nn)]))
        nx = np.argmin([np.inf if bb[i] else dd[i] for i in range(n)])
        if dd[nx] == np.inf: break
    return dd
def calcmin(dd, dc, i):
    return min([dd[nd] + d['log'][i] for nd, d in dc.items()])

print(monte_min(g, 0, 7))
>>>
[7.0436741200000021,
 5.0366892306401603,
 3.1682992231199996,
 1.7938642600000001,
 6.0,
 4.0,
 2.0,
 0]

Geben Sie die Ankunftszeit für jeden Punkt mit monte_min aus.

Der durchschnittliche Dyxtra betrug 7,9, aber Monte Carlo berechnete ihn auf 7,04. Wenn Sie Punkt 4 passieren, ist es 7,9 (= 6,0 + 1,9), aber wenn Sie Punkt 1 durchlaufen, ist es 7,04 (= 5,04 + 2), daher ist es besser, von Punkt 0 zu Punkt 1 zu gehen.

Wenn Sie Punkt 1 erreichen, gehen Sie zu Punkt 2 und Sie erhalten 5,17 (= 3,17 + 2). Wenn zu diesem Zeitpunkt die Seite (1-5) 1 ist, ist es 5 (= 4,0 + 1), und wenn die Seite (1-5) 6 ist, ist es 10 (= 4,0 + 6). Wie Sie sehen können, ist es besser, nach oben zu fahren, wenn die Reisezeit 1 beträgt.

Beachten Sie, dass diese Monte-Carlo-Dyxtra-Methode keine exakt optimale Lösung garantiert, selbst wenn die Probenahme genau ist.

das ist alles