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

  • 0
    Like
  • 0
    Comment

    典型問題と実行方法

    中国人郵便配達問題

    無向グラフにおいて、全ての辺を必ず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)[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)
    pos = nx.spring_layout(g)
    for i, j in g.edges():
        g.adj[i][j]['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

    データ