Python
最適化

組合せ最適化 - 典型問題 - 中国人郵便配達問題

典型問題と実行方法

中国人郵便配達問題

無向グラフにおいて、全ての辺を必ず1度は通って元の点に戻る経路の中で最小になるものを求めよ。

実行方法

usage
Signature: chinese_postman(g_, weight='weight')
Docstring:
中国人郵便配達問題
入力
    g: グラフ
    weight: 重みの属性文字
出力
    距離と頂点リスト
python
# 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))
結果
(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)])

image.png

python
# pandas.DataFrame
from ortoolpy.optimization import ChinesePostman
ChinesePostman('data/edge0.csv')[1]
node1 node2 capacity weight
0 0 4 2 2
1 4 5 2 1
2 4 5 2 1
3 3 4 2 4
4 2 3 2 3
5 2 3 2 3
6 0 3 2 2
7 0 5 2 4
8 1 5 2 5
9 1 2 2 5
10 0 2 2 4
11 0 1 2 1
12 0 1 2 1
python
# 乱数データ
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))
結果
(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)])

image.png

データ