中国人郵便配達問題
無向グラフにおいて、全ての辺を必ず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)])
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)])
