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.

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

Réduire $ \ sum_i {x_i} $ Route aller-retour
Variables $ x_i \ in \ {0, 1 \} ~ \ forall i \ in Road $ S'il faut faire un aller-retour / td>
$ y_j \ ge 0, \ in integer ~ \ forall j \ in point $ la moitié de l'ordre du point
Contraintes $ \ sum_ {i \ in Côté connecté au point j} {~~~~~~~~~~~~ x_i + degré du point j } = 2 y_j \ forall j \ in Point $ Ordre pair

(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]

a.png

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

Paver la route avec l'optimisation des combinaisons
Aménagement routier par optimisation
Résolution du problème N Queen avec l'optimisation continue / combinée
Résolution du problème N Queen avec l'optimisation des combinaisons
Jeux de regroupement avec optimisation des combinaisons
Optimisation combinée avec recuit quantique
Maximisez les ventes des restaurants grâce à l'optimisation combinée
La puissance des solveurs d'optimisation combinée
Résolution de la théorie des jeux avec l'optimisation des combinaisons
Résolution des problèmes de sac à dos avec les outils OR de Google - Pratiquer les bases des problèmes d'optimisation combinée
Résolvons le portefeuille avec une optimisation continue
Empilons les livres à plat avec l'optimisation des combinaisons
Résolution des problèmes de planification des infirmières grâce à l'optimisation des combinaisons
La route de la compilation vers Python 3 avec Thrift
Utiliser l'optimisation des combinaisons
Trouver la main de "Millijan" par l'optimisation des combinaisons
Créer un programme académique avec optimisation des combinaisons
Décidons le cours de date par optimisation de combinaison
Résolution des problèmes d'organisation des districts scolaires grâce à l'optimisation des combinaisons
Minimisez le nombre de polissages en optimisant la combinaison
Juger la finition du mahjong par l'optimisation des combinaisons
Optimisation du regroupement par combinaison
Introduction à l'optimisation
La route vers Pythonista
La route vers Djangoist
Décidons la conférence de PyCon JP 2016 par optimisation de combinaison
Décidons la position du service d'incendie par optimisation combinée
Essayez l'optimisation des fonctions avec Optuna
Insérez le débogueur avec le nez
Enquête Star avec optimisation des combinaisons
La route pour télécharger Matplotlib
Restaurez les photos décousues avec l'optimisation!
Devinez le mot de passe avec klee
Optimisation globale à usage général avec Z3
gethostbyaddr () communique avec l'extérieur
Gratter la moyenne du Nikkei avec le dramaturge-python
Vérifiez le code avec flake8
Calibrer le modèle avec PyCaret
Appelez l'API avec python3.
Ajuster les hyper paramètres avec l'optimisation bayésienne
Résolution du problème d'horaire des infirmières (optimisation des équipes) avec un algorithme génétique