モンテカルロ法を用いたダイクストラ法の紹介
確率的に移動時間が変わるグラフ上の最短路を求める方法を紹介します。
サンプルのグラフを作ります。
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)となります。このように、上への移動時間が1のところで上へ行くことがよいこともわかります。
なお、このモンテカルロダイクストラ法は、サンプリングが正確であっても厳密な最適解の保証はありません。
以上