[PYTHON] Kombinationsoptimierung - typisches Problem - Problem der chinesischen Postzustellung

Typisches Problem und Ausführungsmethode

Problem mit der Zustellung chinesischer Post

Suchen Sie in einem ungerichteten Diagramm den kleinsten Pfad, der immer einmal durch alle Seiten verläuft und zum ursprünglichen Punkt zurückkehrt.

Ausführungsmethode

usage

Signature: chinese_postman(g_, weight='weight')
Docstring:
Problem mit der Zustellung chinesischer Post
Eingang
    g:Graph
    weight:Attribut Charakter des Gewichts
Ausgabe
Entfernungs- und Scheitelpunktliste

python

#CSV-Daten
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))

Ergebnis

(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

#Zufällige Daten
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))

Ergebnis

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

Daten

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