소개

수상한 선박을 찾기 위해 순시선을 출항합니다.
어떤 항로를 선택하면 좋을까요?

문제

지역은 10 × 10 격자 모양으로합시다.
각 지역 간의 이동은 10분 내에 가능하다고 가정합니다.
시간대(10분)마다, 지역별 발견 확률은 과거 실적으로부터 추정해 둡니다.
하루를 달리면 누락된 확률을 최소화하세요.

사고방식

이러한 문제는 시공간 네트워크에서 최단 경로 문제로 풀 수 있습니다.
최단 경로 문제는 조합 최적화의 일반적인 문제 중 하나입니다.

시공간 네트워크는 시간대별로 각 시간대의 네트워크를 연결한 것입니다.



찾을 수 없는 확률은 각 시간대에 없는 확률의 곱으로 표시됩니다.
요인 방 의 기법을 사용해, log 를 사용하면, 곱을 선형의 식으로 할 수 있습니다.
또, 확률의 log를 취하면 음이 됩니다만, 최단로의 홉 수 는 같기 때문에, 최소치를 0에 올리기로 합니다.

파이썬으로 풀기

최단 경로는 Python의 NetworkX dijkstra_path를 사용하여 해결할 수 있습니다.
해보자. 발견 확률은 난수로 만들기로 결정합니다.

파이썬

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

결과 표시

시간을 무시하고 표시해 봅니다.

파이썬

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

이상