[PYTHON] Trouver l'itinéraire des patrouilleurs en optimisant
Introduction
Quittez un bateau de patrouille pour trouver un navire suspect. Quel type d'itinéraire dois-je choisir?
Problème
Faisons de la zone une grille 10x10. Supposons que vous puissiez vous déplacer entre les zones en 10 minutes. La probabilité de découverte pour chaque fuseau horaire (10 minutes) et chaque zone est estimée à partir des résultats antérieurs. Courez une journée pour minimiser les ** chances de ne pas être trouvé **.
Façon de penser
Un tel problème peut être résolu comme le problème de chemin le plus court sur le ** réseau spatio-temporel **. Le problème du chemin le plus court est l'un des problèmes typiques de Optimisation de combinaison.
Un réseau spatio-temporel est une connexion opportune des réseaux pour chaque fuseau horaire.
La probabilité manquante est exprimée comme le produit des probabilités manquantes pour chaque période. En utilisant la technique de Factor Room (http://qiita.com/SaitoTsutomu/items/cfa4c144ab7713766d48), vous pouvez utiliser log pour faire du produit une équation linéaire. De plus, si vous prenez le journal des probabilités, il sera négatif, mais l'itinéraire le plus court [nombre de sauts](http://e-words.jp/w/%E3%83%9B%E3%83%83%E3%83] % 97% E6% 95% B0.html) est le même, nous allons donc augmenter la valeur minimale à 0.
Résoudre avec Python
Le chemin le plus court peut être résolu à l'aide de NetworkX dijkstra_path de Python. Faisons le. La probabilité de découverte sera faite avec des nombres aléatoires.
python
import numpy as np, pandas as pd, networkx as nx
from itertools import product
from pulp import *
nt = 6*24 #Heures(24 heures par incréments de 10 minutes)
nn = 10 #Zone 10x10
np.random.seed(1)
#Probabilité de découverte pour chaque fuseau horaire et zone
a = pd.DataFrame(np.random.rand(nt, nn*nn))
b = np.log(1-a) #Probabilité introuvable(1-a)Journal
b -= b.min().min() #Définissez la valeur minimale sur 0
g = nx.Graph() #nœud=Temps x 100 + zone
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
#Connectez-vous à un réseau spatio-temporel
g.add_edge(k1, (t+1)*100 + k2, weight=r[k2])
#Trouvez l'itinéraire le plus court
res = np.array(nx.dijkstra_path(g, 0, nt*100))
Afficher les résultats
Ignorez l'heure et essayez de l'afficher.
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)})
c'est tout
Recommended Posts