몬테카를로법을 이용한 다이크스트라법 소개

확률적으로 이동 시간이 바뀌는 그래프상의 최단로를 구하는 방법을 소개합니다.

샘플 그래프를 만듭니다.

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

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

위의 점 0에서 점 7까지의 최단 경로를 찾습니다.

옆길은 확정적으로 2시간이 걸립니다.

세로 길이는 80% 확률로 1시간이지만 20% 확률로 6시간이 소요됩니다. 평균 2시간이 소요됩니다.

점 0에서 점 4까지는 확정적으로 1.9시간으로 갈 수 있습니다.

어느 점에 도달했을 때, 그 점에 연결되는 변의 이동 시간만은, 확정하는 것으로 합니다.

평균 시간으로 보면 "0 -> 4 -> 5 -> 6 -> 7"경로에서 7.9 시간이 최단 경로입니다.

그러나 세로 길에서 아래에서 위까지는 확률 80%로 1시간으로 갈 수 있습니다. 이것으로부터, 오른쪽으로 진행하면서, 세로로 1시간으로 갈 수 있으면, 위로 진행하는 방침이, 좋을 것 같습니다.

고안한 몬테카를로다이크스트라법

미리, 확률로 정하는 변에 대해 각각 nn개의 난수를 준비해 둡니다.

모든 점에서 종점에의 도달 시간을 ∞로 하고, 모든 점을 미탐색으로 합니다.

다음 점을 종점으로, 다음 점의 도달 시간을 0으로 설정합니다.

시작점을 찾았을 때까지 다음을 반복하십시오.

다음 점을 검색했습니다.

다음에 접속하는 점의 도달 시간을 아래와 같이 갱신합니다.

검색되지 않은 점 중, 도달 시간이 최소인 것을 다음의 점으로 합니다.

도달 시간 업데이트

이하의 샘플치의 nn회의 평균이, 현재의 도달 시간보다 짧으면, 갱신합니다.

샘플치를 접속하는 점에 대해 「도착 시간과 접속변의 시간의 합」의 최소치로 합니다.

계산해보기

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]

monte_min은 각 점에 대한 도달 시간을 출력합니다.

평균값인 다이크스트라에서는 7.9였지만, 몬테카를로로 계산하면 7.04가 되었습니다.
또, 점 4 를 통과하면, 7.9 (= 6.0+1.9) 입니다만, 점 1 경유로 하면, 7.04 (= 5.04+2)이므로, 점 0 으로부터는 점 1 에 가는 것이 좋게 됩니다.

점 1에 붙으면 점 2로 향하면 5.17 (= 3.17+2)입니다. 이때 변(1-5)이 1이면 5(=4.0+1)가 되고 변(1-5)이 6이면 10(=4.0+6)이 됩니다. 이런 식으로 위로 이동 시간이 한 곳에서 위로 가는 것이 좋습니다.

덧붙여 이 몬테카를로다이쿠스트라법은, 샘플링이 정확하더라도 엄격한 최적해의 보증은 없습니다.

이상