Vous êtes salarié de la section génie civil de la mairie.
Problème de livraison postale chinoise E5% 9B% BD% E4% BA% BA% E9% 83% B5% E4% BE% BF% E9% 85% 8D% E9% 81% 94% E5% 95% 8F% E9% A1% 8C) Je vais. Il peut être calculé en temps polymorphe en utilisant la méthode de Worshall Floyd, mais ici le problème d'optimisation d'entiers mixtes de Optimisation de combinaison Je vais le résoudre. Si l'ordre de tous les points dans le graphe concaténé (le nombre de côtés connectés aux points) est pair, on sait qu'un chemin fermé existe. Si l'ordre est impair, vous pouvez faire un aller-retour sur la même route pour qu'il devienne pair.
La politique est de vous demander si vous devez faire un aller-retour sur la route. (Comme il est relativement facile de trouver le chemin fermé d'un graphe avec tous les ordres pairs, il est omis ici.)
Réduire td> | $ \ sum_i {x_i} $ td> | Route aller-retour td> tr> | |
Variables td> | $ x_i \ in \ {0, 1 \} ~ \ forall i \ in Road $ td> | S'il faut faire un aller-retour | / td> tr> |
$ y_j \ ge 0, \ in integer ~ \ forall j \ in point $ td> | la moitié de l'ordre du point td> tr> | ||
Contraintes td> | $ \ sum_ {i \ in Côté connecté au point j} {~~~~~~~~~~~~ x_i + degré du point j } = 2 y_j \ forall j \ in Point $ td> | Ordre pair td> tr> |
(Cette formulation n'est pas très bonne, donc en pratique une autre méthode serait meilleure.)
Créez un graphique aléatoire.
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]
Puisque l'ordre des points 0, 2, 3, 6 est impair, nous savons que nous devons les relier.
Formulons et résolvons-le.
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)]
Au plus court, vous pouvez voir que les points 0, 2, 3, 6 sont connectés.
c'est tout
Recommended Posts