Calculation of the shortest path using the Monte Carlo method

Introduction of Dijkstra's algorithm using Monte Carlo method

I will introduce how to find the shortest path on the graph where the travel time changes stochastically.

Make a sample graph.

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]) #Vertical
    if i < m-1:
        g.add_edge(i, i+1, prob=[1], time=[2]) #side
        g.add_edge(i+m, i+m+1, prob=[1], time=[2]) #side

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

image

--Find the shortest path ** from point 0 to point 7 above. ――The side road definitely takes 2 hours. ――The vertical road has a probability of 80% and takes 1 hour, but with a probability of 20% it takes 6 hours. It takes 2 hours on average. ――From point 0 to point 4, you can definitely go in 1.9 hours. ――When you reach a certain point, only the movement time of the side connected to that point shall be fixed.

In terms of average time, the route is "0-> 4-> 5-> 6-> 7", and 7.9 hours is the shortest route.

However, on a vertical road, you can go from bottom to top with an 80% chance of going in an hour. From this, it seems good to go up if you go vertically in 1 hour while going to the right.

Invented Monte Carlo Dijkstra method

――Prepare nn random numbers for each side determined by probability in advance. --Set the time to reach the end point to ∞ at all points, and leave all points unsearched. --Set the next point as the end point, and set the arrival time of the next point to 0. --Repeat the following until the starting point has been searched. --Mark the following points as searched. --Update the arrival time of the point connecting to the next point as described below. --Among the points that have not been searched, the one with the shortest arrival time is set as the next point.

Reach time update

--Update if the average of nn times of the sample values below is shorter than the current arrival time. --For the point to connect the sample value, set it to the minimum value of "sum of arrival time and connection side time".

Try to calculate

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]

Output the arrival time for each point with monte_min.

The average Dijkstra was 7.9, but when calculated in Monte Carlo it was 7.04. Also, if you pass through point 4, it will be 7.9 (= 6.0 + 1.9), but if you go through point 1, it will be 7.04 (= 5.04 + 2), so it is better to go from point 0 to point 1.

When you reach point 1, go to point 2 and you get 5.17 (= 3.17 + 2). At this time, if the side (1-5) is 1, it becomes 5 (= 4.0 + 1), and if the side (1-5) is 6, it becomes 10 (= 4.0 + 6). As you can see, it is better to go up when the up travel time is 1.

Note that this Monte Carlo Dijkstra method does not guarantee an exact optimal solution even if the sampling is accurate.

that's all

Recommended Posts

Calculation of the shortest path using the Monte Carlo method
Increase the speed of the Monte Carlo method of Cython cut-out implementation.
Monte Carlo method
Find the ratio of the area of Lake Biwa by the Monte Carlo method
About the accuracy of Archimedean circle calculation method
#Monte Carlo method to find pi using Python
Try implementing the Monte Carlo method in Python
Speed comparison of each language by Monte Carlo method
Introduction to Monte Carlo Method
Reuse the behavior of the @property method by using a descriptor [16/100]
Sprinkle rice grains to find the circumference (Monte Carlo method)
Numerical approximation method when the calculation of the derivative is troublesome
Understand the metropolitan hasting method (one of the methods in Markov chain Monte Carlo method) with implementation
Find the critical path of PERT using breadth-first search and depth-first search
Calculation of normal vector using convolution
[Scientific / technical calculation by Python] Monte Carlo simulation of thermodynamics of 2D Ising spin system by Metropolis method
Feature extraction by TF method using the result of morphological analysis
Calculation of the number of Klamer correlations
[Statistics] Visualize and understand the Hamiltonian Monte Carlo method with animation.
Simulate Monte Carlo method in Python
Estimating π by Monte Carlo method
[Anomaly detection] Try using the latest method of deep distance learning
Get the file path using Pathlib
I couldn't install pypy3.6-7.3.1 on macOS + pyenv, but I could install pypy3.6-7.3.0. I felt the wind of pypy by the Monte Carlo method.
Installation method using the pip command of the Python package (library) Mac environment
Implement the shortest path search for the maze
Count / verify the number of method calls.
Saddle point search using the gradient method
Pass the path of the imported python module
Try cluster analysis using the K-means method
Check the path of the Python imported module
Dominion compression play analyzed by Monte Carlo method
Shortening the analysis time of Openpose using sound
Estimating the effect of measures using propensity scores
Check the type of the variable you are using
Exclusive release of the django app using ngrok
Try using the collections module (ChainMap) of python3
Find the geometric mean of n! Using Python
To get the path of the currently running python.exe
Generate a hash value using the HMAC method.
[Introduction to Algorithm] Find the shortest path [Python3]
Determine the number of classes using the Starges formula
I tried using the image filter of OpenCV
Find the shortest path with the Python Dijkstra's algorithm
Check the status of your data using pandas_profiling
Scraping the winning data of Numbers using Docker
Calculation of support vector machine (SVM) (using cvxopt)
Python: Calculate the uniform flow depth of a rectangular cross section using the Brent method