はじめに
不審船を見つけるために、巡視船を出航させます。
どのような、航路を選べばよいでしょうか？
問題
エリアは、10×10の格子状としましょう。
各エリア間の移動は10分でできるとします。
時間帯(10分)ごと、エリアごとの発見確率は、過去の実績から推定しておきます。
1日走って、見つからない確率を最小化しましょう。
考え方
このような問題は、時空間ネットワーク上での最短路問題として解くことができます。
最短路問題は、組合せ最適化の典型問題の1つです。
時空間ネットワークとは、各時間帯ごとのネットワークを時間に沿ってつなげたものです。
見つからない確率は、各時間帯の見つからない確率の積で表されます。
因子の部屋のテクニックを使って、logを使えば、積を線形の式にできます。
また、確率のlogをとると負になりますが、最短路のホップ数は同じなので、最小値を0にかさ上げすることにします。
Pythonで解く
最短路は、PythonのNetworkXのdijkstra_pathを使うと解くことができます。
やってみましょう。発見確率は、乱数で作ることにします。
python
import numpy as np, pandas as pd, networkx as nx
from itertools import product
from pulp import *
nt = 6*24 # 時間数(10分刻みで24時間分)
nn = 10 # 10x10のエリア
np.random.seed(1)
# 時間帯ごとエリアごとの発見確率
a = pd.DataFrame(np.random.rand(nt, nn*nn))
b = np.log(1-a) # 見つからない確率(1-a)のlogをとる
b -= b.min().min() # 最小値を0にする
g = nx.Graph() # ノード = 時刻×100＋エリア
for t, r in b.iterrows():
for i, j in product(range(nn), range(nn)):
k1 = t*100 + i*nn + j
for di, dj in [(-1,0), (0,-1), (0,0), (0,1), (1,0)]:
if 0<=i+di<nn and 0<=j+dj<nn:
k2 = (i+di)*nn + j+dj
# 時空間ネットワークの接続をする
g.add_edge(k1, (t+1)*100 + k2, weight=r[k2])
# 最短路を求める
res = np.array(nx.dijkstra_path(g, 0, nt*100))
結果の表示
時間を無視して表示してみます。
python
from more_itertools import pairwise
h = nx.Graph()
h.add_edges_from([(i, j) for i, j in pairwise(res%100)])
nx.draw(h, pos={(i*nn+j):(i, j) for i in range(nn) for j in range(nn)})
以上