巡回セールスマン問題（NetworkX）

巡回セールスマン問題

巡回セールスマン問題（Traveling Salesman Problem）は、すべての都市を一度だけ訪れ、最短距離で戻ってくる経路を求める問題です。

以下は、NetworkXを使用して巡回セールスマン問題を解く例です。

import networkx as nx
import matplotlib.pyplot as plt

# 5つの都市の座標を設定
positions = {1: (0, 0), 2: (1, 1), 3: (2, 0), 4: (3, 1), 5: (4, 0)}

# 距離を計算する関数を定義
def distance(u, v):
    x1, y1 = positions[u]
    x2, y2 = positions[v]
    return ((x1-x2)**2 + (y1-y2)**2)**0.5

# グラフを作成
G = nx.Graph()
G.add_nodes_from(positions.keys())
for u in positions:
    for v in positions:
        if u < v:
            G.add_edge(u, v, weight=distance(u, v))

# 巡回セールスマン問題を解く
tsp = list(nx.algorithms.approximation.traveling_salesman_problem(G))

# 解を表示
print("最短距離の順序：", tsp)
print("最短距離：", sum(distance(u, v) for u, v in zip(tsp, tsp[1:]+tsp[:1])))

# グラフを可視化
pos = positions
nx.draw(G, pos=pos, with_labels=True)
nx.draw_networkx_edges(G, pos=pos, edgelist=[(u, v) for u, v in zip(tsp, tsp[1:]+tsp[:1])], edge_color='r')
plt.show()

このコードでは、5つの都市の座標を定義し、距離を計算する関数を定義しています。

その後、座標をノードとし、距離をエッジとしたグラフを作成します。

nx.algorithms.approximation.traveling_salesman_problem関数を使用して、巡回セールスマン問題を解きます。

解は、最短距離の順序として返されます。

最後に、解を表示しグラフを可視化しています。

[実行結果]