[PYTHON] Optimisation de combinaison-problème typique-problème de livraison postale chinoise

Problème typique et méthode d'exécution

Problème de livraison de courrier chinois

Dans le graphique non orienté, recherchez le plus petit chemin qui passe toujours une fois par tous les côtés et revient au point d'origine.

Méthode d'exécution

usage

Signature: chinese_postman(g_, weight='weight')
Docstring:
Problème de livraison de courrier chinois
contribution
    g:Graphique
    weight:Caractère d'attribut du poids
production
Liste des distances et des sommets

python

#Données CSV
import pandas as pd, networkx as nx, matplotlib.pyplot as plt
from ortoolpy import chinese_postman, graph_from_table, networkx_draw
tbn = pd.read_csv('data/node0.csv')
tbe = pd.read_csv('data/edge0.csv')
g = graph_from_table(tbn, tbe, multi=True)[0]
networkx_draw(g)
plt.show()
print(chinese_postman(g))

résultat

(36.0, [(0, 4), (4, 5), (5, 4), (4, 3), (3, 2), (2, 3), (3, 0),
        (0, 5), (5, 1), (1, 2), (2, 0), (0, 1), (1, 0)])

python

# pandas.DataFrame
from ortoolpy.optimization import ChinesePostman
ChinesePostman('data/edge0.csv')[1]

python

#Données aléatoires
import math, networkx as nx, matplotlib.pyplot as plt
from ortoolpy import chinese_postman, networkx_draw
g = nx.random_graphs.fast_gnp_random_graph(10, 0.3, 1)
g = nx.MultiGraph(g)
pos = nx.spring_layout(g)
for i, j, k in g.edges:
    g.adj[i][j][k]['weight'] = math.sqrt(sum((pos[i] - pos[j])**2))
networkx_draw(g, nx.spring_layout(g))
plt.show()
print(chinese_postman(g))

résultat

(7.054342373467126, [(0, 4), (4, 8), (8, 6), (6, 9), (9, 7), (7, 4),
                     (4, 9), (9, 3), (3, 7), (7, 5), (5, 4), (4, 6),
                     (6, 1), (1, 2), (2, 5), (5, 1), (1, 0)])

Les données

• data/node0.csv
• data/edge0.csv