[PYTHON] Bereiten Sie die Straße mit Kombinationsoptimierung
Pflastern Sie die Straße in kürzester Zeit
Sie sind Angestellter der Tiefbauabteilung des Rathauses.
- Sie müssen das unbefestigte Straßennetz selbst asphaltieren (wegen des Mangels an Arbeitskräften). ―― Schließlich müssen Sie zum Arbeitsstartpunkt zurückkehren. ――Ich möchte die Arbeit so schnell wie möglich beenden.
Denkweise
Problem mit der chinesischen Postzustellung löst das Problem, eine gesperrte Straße (eine Route, die umhergeht und zurückkehrt) zu finden, die allen Seiten (Straßen) folgt. E5% 9B% BD% E4% BA% BA% E9% 83% B5% E4% BE% BF% E9% 85% 8D% E9% 81% 94% E5% 95% 8F% E9% A1% 8C) Ich werde. Sie kann in polymorpher Zeit mit der Worshall Floyd-Methode berechnet werden. Hier ist jedoch das Problem der Optimierung ganzer Zahlen von Kombinationsoptimierung. Ich werde es lösen. Wenn die Reihenfolge aller Punkte im verketteten Diagramm (die Anzahl der mit den Punkten verbundenen Seiten) gerade ist, ist bekannt, dass ein geschlossener Pfad vorhanden ist. Wenn die Reihenfolge ungerade ist, können Sie eine Rundreise auf derselben Straße machen, damit sie gerade wird.
Die Politik ist zu fragen, ob Sie eine Rundreise auf der Straße machen sollten. (Da es relativ einfach ist, den geschlossenen Pfad eines Graphen mit allen geraden Ordnungen zu finden, wird er hier weggelassen.)
Formulierung
| Minimieren Sie | $ \ sum_i {x_i} $ | Hin- und Rückfahrt | |
| Variablen | $ x_i \ in \ {0, 1 \} ~ \ forall i \ in Road $ | Gibt an, ob eine Rundreise | durchgeführt werden soll / td> |
| $ y_j \ ge 0, \ in Ganzzahl ~ \ für alle j \ in Punkt $ | die halbe Reihenfolge des Punktes | ||
| Einschränkungen | $ \ sum_ {i \ in Seite verbunden mit Punkt j} {~~~~~~~~~~~~ x_i + Grad von Punkt j } = 2 y_j \ forall j \ in Punkt $ | Gerade Reihenfolge |
(Diese Formulierung ist nicht sehr gut, daher wäre in der Praxis eine andere Methode besser.)
In Python ausführen
Erstellen Sie ein zufälliges Diagramm.
python3
%matplotlib inline
import networkx as nx
from pulp import *
g = nx.random_graphs.fast_gnp_random_graph(8, 0.3, 11)
pos = nx.spring_layout(g)
nx.draw_networkx_nodes(g, pos=pos, node_size=600, node_color='w')
nx.draw_networkx_edges(g, pos=pos)
nx.draw_networkx_labels(g, pos=pos, font_size=20)
print([i for i, l in enumerate(g.adjacency_list()) if len(l)%2])
>>>
[0, 2, 3, 6]
Da die Reihenfolge der Punkte 0, 2, 3, 6 ungerade ist, wissen wir, dass wir sie verbinden sollten.
Formulieren und lösen wir es.
python3
m = LpProblem()
xs, ys = [], []
for i, j in g.edges():
g.edge[i][j]['x'] = x = LpVariable('x%d_%d'%(i,j), cat=LpBinary)
xs.append(x)
m += lpSum(xs)
for i, ad in enumerate(g.adjacency_list()):
y = LpVariable(
'y%d'%i, cat=LpInteger)
m += lpSum(g.edge[i][j]['x'] for j in ad) + len(ad) == 2 * y
ys.append(y)
m.solve()
print([g.edges()[i] for i, x in enumerate(xs) if value(x)])
>>>
[(0, 2), (1, 3), (1, 6)]
Im kürzesten Fall sehen Sie, dass die Punkte 0, 2, 3, 6 verbunden sind.
das ist alles
Recommended Posts