조합 최적화 - 전형적인 문제 - 중국인 우편 배달 문제

일반적인 문제와 실행 방법

중국인 우편 배달 문제

무향 그래프에 있어서, 모든 변을 반드시 한번은 통과하여 원래의 점으로 되돌아가는 경로 중에서 최소가 되는 것을 구해라.

실행 방법

usage

Signature: chinese_postman(g_, weight='weight')
Docstring:
中国人郵便配達問題
入力
    g: グラフ
    weight: 重みの属性文字
出力
    距離と頂点リスト

파이썬

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

파이썬

# 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



파이썬

# 乱数データ
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)])

데이터

data/node0.csv

data/edge0.csv