ネットワーク最適化 NetworkX

問題

あなたは都市間を結ぶ道路網を計画するプロジェクトを担当しています。

各都市はノードとして表現され、道路はエッジ（辺）で接続されます。

各道路には建設費用と通行料があり、最小の建設費用で全ての都市を繋ぐためにどの道路を建設すべきかを決定する必要があります。

以下は都市と道路の情報です。

建設費用は道路の建設コストであり、通行料はその道路を通るたびに支払う必要がある費用です。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
import networkx as nx

# 都市と道路の情報
cities = ['A', 'B', 'C', 'D', 'E', 'F']
roads = [
    ('A', 'B', {'construction_cost': 10, 'toll': 2}),
    ('A', 'C', {'construction_cost': 15, 'toll': 4}),
    ('B', 'C', {'construction_cost': 12, 'toll': 3}),
    ('B', 'D', {'construction_cost': 20, 'toll': 5}),
    ('C', 'E', {'construction_cost': 18, 'toll': 4}),
    ('D', 'E', {'construction_cost': 25, 'toll': 6}),
    ('D', 'F', {'construction_cost': 22, 'toll': 5}),
    ('E', 'F', {'construction_cost': 30, 'toll': 7}),
]

この道路網を最小の建設費用で全ての都市を繋ぐために、どの道路を建設すべきかを見つけてください。

また、最小建設費用と通行料の合計も計算してください。

ヒント:

NetworkXの最小全域木 (Minimum Spanning Tree) アルゴリズムを使用すると、最小建設費用の道路網を見つけるのに役立ちます。

最小全域木を見つけた後、通行料を合計して最終的なコストを計算します。

解答

問題の最適な道路網を計算し、その結果をグラフで可視化します。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
import networkx as nx
import matplotlib.pyplot as plt

# 都市と道路の情報
cities = ['A', 'B', 'C', 'D', 'E', 'F']
roads = [
    ('A', 'B', {'construction_cost': 10, 'toll': 2}),
    ('A', 'C', {'construction_cost': 15, 'toll': 4}),
    ('B', 'C', {'construction_cost': 12, 'toll': 3}),
    ('B', 'D', {'construction_cost': 20, 'toll': 5}),
    ('C', 'E', {'construction_cost': 18, 'toll': 4}),
    ('D', 'E', {'construction_cost': 25, 'toll': 6}),
    ('D', 'F', {'construction_cost': 22, 'toll': 5}),
    ('E', 'F', {'construction_cost': 30, 'toll': 7}),
]

# グラフを作成
G = nx.Graph()
G.add_nodes_from(cities)
G.add_edges_from([(u, v, {'construction_cost': data['construction_cost'], 'toll': data['toll']}) for u, v, data in roads])

# 最小全域木を計算
minimum_spanning_tree = nx.minimum_spanning_tree(G)

# 最小全域木に含まれるエッジの情報を取得
selected_edges = [(u, v) for u, v in minimum_spanning_tree.edges()]

# 最小建設費用と通行料を計算
construction_cost_total = sum(data['construction_cost'] for u, v, data in minimum_spanning_tree.edges(data=True))
toll_total = sum(data['toll'] for u, v, data in minimum_spanning_tree.edges(data=True))
total_cost = construction_cost_total + toll_total

# グラフを描画
pos = nx.spring_layout(G, seed=42)
plt.figure(figsize=(10, 8))

# 道路網全体を描画
nx.draw(G, pos, with_labels=True, node_size=500, node_color='lightblue', font_size=10, font_weight='bold', arrowsize=20)

# 最小全域木に含まれるエッジを太線で描画
nx.draw_networkx_edges(G, pos, edgelist=selected_edges, width=2, edge_color='red')

# グラフの詳細を表示
plt.title("Optimal Road Network")
plt.text(0.5, -0.1, f"Total Construction Cost: {construction_cost_total}", transform=plt.gca().transAxes, horizontalalignment='center')
plt.text(0.5, -0.15, f"Total Toll: {toll_total}", transform=plt.gca().transAxes, horizontalalignment='center')
plt.text(0.5, -0.2, f"Total Cost: {total_cost}", transform=plt.gca().transAxes, horizontalalignment='center')

plt.show()

# 結果を出力
print("Optimal Road Network:")
print("Selected Edges (Roads):", selected_edges)
print("Total Construction Cost:", construction_cost_total)
print("Total Toll:", toll_total)
print("Total Cost (Construction + Toll):", total_cost)

このコードは、最小全域木を計算し、最適な道路網を可視化します。

また、最小建設費用、通行料、総コストを計算して表示します。

[実行結果]

Optimal Road Network:
Selected Edges (Roads): [('A', 'B'), ('A', 'C'), ('B', 'D'), ('C', 'E'), ('D', 'F')]
Total Construction Cost: 85
Total Toll: 20
Total Cost (Construction + Toll): 105

ソース解説

以下にソースコードの詳細を説明します。

1. networkxとmatplotlibモジュールをインポートします。

これらはグラフ理論とグラフの可視化のために使用されます。

2. 都市と道路の情報を定義します。

  • cities: 都市名のリストです。
  • roads: 道路の情報が格納されたリストで、各要素は道路の始点、終点、および建設費用と通行料を含む辞書です。

3. 空のグラフ G を作成します。

これは都市と道路の関係を表現するためのグラフです。

4. G に都市ノードを追加し、roadsリストからエッジ（道路）を追加します。

各エッジには、建設費用と通行料がエッジの属性として追加されます。

5. nx.minimum_spanning_tree 関数を使用して、最小全域木を計算します。

最小全域木は、最小の建設費用で全ての都市を繋ぐ道路のサブセットです。

6. minimum_spanning_tree から最小全域木に含まれるエッジの情報を取得し、selected_edges リストに格納します。

7. 最小全域木に含まれるエッジの建設費用と通行料を合計して、最小建設費用と通行料の合計である construction_cost_total と toll_total を計算します。

8. 道路網全体と最小全域木を可視化するためのグラフ描画を行います。

  • nx.spring_layout を使用して、都市と道路の配置を計算します。
  • nx.draw を使用して、道路網全体を描画します。
  • nx.draw_networkx_edges を使用して、最小全域木に含まれるエッジを太線で描画します。
  • plt.title、plt.text を使用して、グラフの詳細情報を表示します。

9. 最終的な道路網とコストに関する情報をコンソールに出力します。

このプログラムは、都市間の最適な道路網を計画し、その結果を視覚化しています。

グラフ解説

このグラフは、都市間の道路網を可視化したものです。

以下はこのグラフの説明です：

1. 都市と道路の配置:

グラフは、都市（A、B、C、D、E、F）がノードとして表示され、道路がこれらの都市間をエッジとして表示されています。
都市と道路の配置は、nx.spring_layoutを使用して計算され、適切に配置されています。

2. ノードの表示:

各都市は、それぞれの名前（A、B、C、D、E、F）がラベルとして表示されています。
ノードは青い円で表され、そのサイズは node_size=500 で設定されています。

3. エッジ（道路）の表示:

道路は都市間を結ぶエッジとして表示されています。
最小全域木に含まれるエッジ（最適な道路）は太線の赤い線で描画されています。
これらのエッジは、最小建設費用で全ての都市を繋ぐために選択されました。

4. グラフの詳細情報:

グラフの上部には「Optimal Road Network」というタイトルが表示されています。
また、グラフの下部には以下の情報が表示されています。

  • Total Construction Cost: 選択されたエッジ（道路）の建設費用の合計が表示されています。
  • Total Toll: 選択されたエッジ（道路）の通行料の合計が表示されています。
  • Total Cost: 建設費用と通行料の合計コストが表示されています。

このグラフは、最適な道路網を視覚化し、最小建設費用と通行料を示しています。

最小全域木に含まれるエッジが強調表示されており、道路網全体の構造がわかりやすく表示されています。