Je vais vous présenter comment trouver l'itinéraire le plus court sur le graphique où le temps de trajet change de manière probabiliste.

Faites un exemple de graphique.

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]) #Verticale
    if i < m-1:
        g.add_edge(i, i+1, prob=[1], time=[2]) #côté
        g.add_edge(i+m, i+m+1, prob=[1], time=[2]) #côté

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)});

• Trouvez l'itinéraire le plus court ** du point 0 au point 7 ci-dessus. ――La route secondaire prend définitivement 2 heures. ――La route verticale prend 1 heure avec une probabilité de 80%, mais cela prend 6 heures avec une probabilité de 20%. Cela prend en moyenne 2 heures.
• Les points 0 à 4 peuvent certainement être atteints en 1,9 heure. ――Lorsque vous atteignez un certain point, seul le temps de déplacement du côté connecté à ce point doit être fixé.

En termes de temps moyen, l'itinéraire est "0-> 4-> 5-> 6-> 7", et 7,9 heures est l'itinéraire le plus court.

Cependant, sur une route verticale, vous pouvez aller de bas en haut avec 80% de chances en une heure. A partir de là, il semble que la politique de montée est bonne si vous allez à la verticale en 1 heure en allant vers la droite.

Méthode Monte Carlo Dyxtra inventée

――Préparez nn nombres aléatoires pour chaque côté déterminés à l'avance par la probabilité. --Réglez l'heure pour atteindre le point final sur ∞ à tous les points et laissez tous les points non recherchés. --Définissez le point suivant comme point final et définissez l'heure d'arrivée du point suivant sur 0. --Répétez ce qui suit jusqu'à ce que le point de départ ait été recherché.

• Marquez les points suivants comme recherchés. --Mettre à jour l'heure d'arrivée du point de connexion au point suivant comme décrit ci-dessous. --Parmi les points qui n'ont pas été recherchés, celui avec l'heure d'arrivée la plus courte est défini comme point suivant.

Mise à jour du temps d'accès

--Mise à jour si la moyenne de nn fois les valeurs d'échantillon ci-dessous est plus courte que l'heure d'arrivée actuelle. --Pour le point de connexion de la valeur d'échantillon, réglez-la sur la valeur minimale de «somme de l'heure d'arrivée et du temps côté connexion».

Essayez de calculer

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]

Sortez l'heure d'arrivée de chaque point avec monte_min.

Le Dyxtra moyen était de 7,9, mais Monte Carlo l'a calculé à 7,04. De plus, si vous passez par le point 4, ce sera 7,9 (= 6,0 + 1,9), mais si vous passez par le point 1, ce sera 7,04 (= 5,04 + 2), il est donc préférable de passer du point 0 au point 1.

Lorsque vous atteignez le point 1, allez au point 2 et vous obtenez 5,17 (= 3,17 + 2). À ce moment, si le côté (1-5) est 1, ce sera 5 (= 4,0 + 1), et si le côté (1-5) est 6, ce sera 10 (= 4,0 + 6). Comme vous pouvez le voir, il est préférable de remonter lorsque le temps de trajet ascendant est de 1.

Notez que cette méthode Monte Carlo Dyxtra ne garantit pas une solution optimale exacte même si l'échantillonnage est précis.

c'est tout