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

[典型問題と実行方法](0f6c1a4415d196e64314)
##中国人郵便配達問題
無向グラフにおいて、全ての辺を必ず1度は通って元の点に戻る経路の中で最小になるものを求めよ。

##実行方法

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

```python: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))
```

```text:結果
(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](https://qiita-image-store.s3.amazonaws.com/0/13955/95222b91-cb6d-966f-4522-ce21c45eac68.png)

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

<table>
  <thead>
    <tr>
      <th></th>
      <th>node1</th>
      <th>node2</th>
      <th>capacity</th>
      <th>weight</th>
    </tr>
  </thead>
  <tbody>
    <tr>
      <th>0</th>
      <td>0</td>
      <td>4</td>
      <td>2</td>
      <td>2</td>
    </tr>
    <tr>
      <th>1</th>
      <td>4</td>
      <td>5</td>
      <td>2</td>
      <td>1</td>
    </tr>
    <tr>
      <th>2</th>
      <td>4</td>
      <td>5</td>
      <td>2</td>
      <td>1</td>
    </tr>
    <tr>
      <th>3</th>
      <td>3</td>
      <td>4</td>
      <td>2</td>
      <td>4</td>
    </tr>
    <tr>
      <th>4</th>
      <td>2</td>
      <td>3</td>
      <td>2</td>
      <td>3</td>
    </tr>
    <tr>
      <th>5</th>
      <td>2</td>
      <td>3</td>
      <td>2</td>
      <td>3</td>
    </tr>
    <tr>
      <th>6</th>
      <td>0</td>
      <td>3</td>
      <td>2</td>
      <td>2</td>
    </tr>
    <tr>
      <th>7</th>
      <td>0</td>
      <td>5</td>
      <td>2</td>
      <td>4</td>
    </tr>
    <tr>
      <th>8</th>
      <td>1</td>
      <td>5</td>
      <td>2</td>
      <td>5</td>
    </tr>
    <tr>
      <th>9</th>
      <td>1</td>
      <td>2</td>
      <td>2</td>
      <td>5</td>
    </tr>
    <tr>
      <th>10</th>
      <td>0</td>
      <td>2</td>
      <td>2</td>
      <td>4</td>
    </tr>
    <tr>
      <th>11</th>
      <td>0</td>
      <td>1</td>
      <td>2</td>
      <td>1</td>
    </tr>
    <tr>
      <th>12</th>
      <td>0</td>
      <td>1</td>
      <td>2</td>
      <td>1</td>
    </tr>
  </tbody>
</table>

```python: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))
```

```text:結果
(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](https://qiita-image-store.s3.amazonaws.com/0/13955/4fe78068-808e-03b9-b303-ecb627866901.png)

##データ
- [data/node0.csv](https://www.dropbox.com/s/7v4x2ypbgkj52vr/node0.csv)
- [data/edge0.csv](https://www.dropbox.com/s/2vryg0i2kb76mic/edge0.csv)