Paver la route avec l'optimisation des combinaisons

Pave la route dans les plus brefs délais

Vous êtes salarié de la section génie civil de la mairie.

• Vous devez paver vous-même le réseau routier non asphalté (à cause du manque de main-d'œuvre). ――Enfin, vous devez revenir au point de départ du travail. «Je veux terminer le travail le plus tôt possible.

Façon de penser

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

Formulation

(Cette formulation n'est pas très bonne, donc en pratique une autre méthode serait meilleure.)

Exécuter en Python

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