[PYTHON] Finden der Route von Patrouillenbooten durch Optimieren
Einführung
Verlassen Sie ein Patrouillenboot, um ein verdächtiges Schiff zu finden. Welche Route soll ich wählen?
Problem
Machen wir den Bereich zu einem 10x10-Raster. Angenommen, Sie können in 10 Minuten zwischen Bereichen wechseln. Die Entdeckungswahrscheinlichkeit für jede Zeitzone (10 Minuten) und jeden Bereich wird aus früheren Ergebnissen geschätzt. Laufen Sie einen Tag lang, um die ** Wahrscheinlichkeit, nicht gefunden zu werden **, zu minimieren.
Denkweise
Ein solches Problem kann als das Problem des kürzesten Weges im ** raumzeitlichen Netzwerk ** gelöst werden. Das Problem mit dem kürzesten Pfad ist eines der typischen Probleme von Kombinationsoptimierung.
Ein raumzeitliches Netzwerk ist eine zeitnahe Verbindung von Netzwerken für jede Zeitzone.
Die fehlende Wahrscheinlichkeit wird als Produkt der fehlenden Wahrscheinlichkeiten für jeden Zeitraum ausgedrückt. Mit der Technik von Factor Room (http://qiita.com/SaitoTsutomu/items/cfa4c144ab7713766d48) können Sie log verwenden, um das Produkt zu einer linearen Gleichung zu machen. Wenn Sie das Wahrscheinlichkeitsprotokoll nehmen, ist es negativ, aber der kürzeste Weg [Anzahl der Sprünge](http://e-words.jp/w/%E3%83%9B%E3%83%83%E3%83] % 97% E6% 95% B0.html) ist dasselbe, daher erhöhen wir den Mindestwert auf 0.
Löse mit Python
Der kürzeste Pfad kann mit Pythons NetworkX dijkstra_path gelöst werden. Machen wir das. Die Entdeckungswahrscheinlichkeit wird mit Zufallszahlen ermittelt.
python
import numpy as np, pandas as pd, networkx as nx
from itertools import product
from pulp import *
nt = 6*24 #Std(24 Stunden in Schritten von 10 Minuten)
nn = 10 #10x10 Fläche
np.random.seed(1)
#Erkennungswahrscheinlichkeit für jede Zeitzone und jeden Bereich
a = pd.DataFrame(np.random.rand(nt, nn*nn))
b = np.log(1-a) #Wahrscheinlichkeit nicht gefunden(1-a)Log
b -= b.min().min() #Setzen Sie den Mindestwert auf 0
g = nx.Graph() #Knoten=Zeit x 100 + Fläche
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
#Stellen Sie eine Verbindung zu einem raumzeitlichen Netzwerk her
g.add_edge(k1, (t+1)*100 + k2, weight=r[k2])
#Finden Sie den kürzesten Weg
res = np.array(nx.dijkstra_path(g, 0, nt*100))
Ergebnisse anzeigen
Ignorieren Sie die Uhrzeit und versuchen Sie, sie anzuzeigen.
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)})
das ist alles
Recommended Posts