巡回セールスマン問題（Traveling Salesman Problem, TSP）は、コンピュータサイエンスや最適化問題の中でも特に有名な問題の一つです。複数の都市を効率よく巡回し、全ての都市を一度ずつ訪問した後に出発点に戻る最短経路を求めるという課題は、物流やルート計画、さらには機械学習の分野でも応用されています。
本記事では、初心者でも理解しやすいように、巡回セールスマン問題の基本的な定義から代表的なアルゴリズムまでを数式とPythonコードを交えて丁寧に解説します。問題の本質を掴みながら、実際に動くコード例を通して理解を深めましょう。
この記事で学べることは以下の通りです。
- 巡回セールスマン問題の概要と数式による定式化
- 代表的なアルゴリズム（総当たり法、近似アルゴリズム）の仕組み
- Pythonでの基本的な実装方法
特に、TSPの難しさを示すために、都市数が増えると計算量が爆発的に増加することを示す数式も紹介します。例えば、都市数が\( n \)のとき、全ての経路の組み合わせは \((n-1)!\) 個にのぼります。これがTSPがNP困難問題と呼ばれる所以です。
巡回セールスマン問題は単なる理論上の問題ではなく、実際のビジネスや研究の現場で重要な役割を果たしています。今回紹介した総当たり法は理解しやすい反面、都市数が多い場合は計算時間が膨大になり実用的ではありません。そこで近似アルゴリズムやヒューリスティックが活用されます。
今回の内容を踏まえて、さらに効率的なアルゴリズムや実践的な応用例に挑戦してみると理解が深まるでしょう。アルゴリズムの選択や計算量の観点から問題を考察すると、より広い視野で最適化問題に取り組めます。
次に読むと良い関連記事候補の観点としては、「最適化アルゴリズムの計算量と効率化テクニック」が挙げられます。これにより、単純なアルゴリズムを超えた高度な手法への橋渡しができます。
- 総当たり法以外の近似アルゴリズム（例えば、遺伝的アルゴリズムや局所探索法）について学ぶ
- 実際のデータセットを用いた巡回セールスマン問題のハンズオン
- 計算量削減のためのメモ化や動的計画法の応用事例を調べる
巡回セールスマン問題とは何か
巡回セールスマン問題（Traveling Salesman Problem、略してTSP）は、組合せ最適化の代表的な問題の一つです。具体的には、複数の都市をすべて一度ずつ訪問し、最後に出発地点に戻る最短経路を見つける問題です。この問題は物流や配送、製造業の生産計画など、さまざまな分野で応用されています。
問題の本質は「都市の数が増えると探索すべきルートの数が爆発的に増加する」という点にあります。例えば、都市が \(n\) 個ある場合、訪問順序のパターンは \((n-1)!\) 通りも存在します。これを数式で表すと
\[
\text{ルート数} = (n-1)!
\]
となります。これほどの数の候補をすべて計算するのは、都市数が多くなると現実的ではありません。したがって、効率よく最短経路を見つけるためのアルゴリズムが重要となります。
距離行列と目的関数の定義
巡回セールスマン問題を数学的に定式化する際には、各都市間の距離を表す行列 \(D = [d_{ij}]\) を用います。ここで、\(d_{ij}\) は都市 \(i\) から都市 \(j\) への距離です。
巡回経路を示す順序を \(\pi = (\pi_1, \pi_2, \ldots, \pi_n)\) とすると、目的は全経路の合計距離を最小化することです。これを数式で書くと、
\[
\min_{\pi} \sum_{k=1}^{n-1} d_{\pi_k \pi_{k+1}} + d_{\pi_n \pi_1}
\]
となります。ここで、最後の項 \(d_{\pi_n \pi_1}\) は出発地点に戻る距離です。
Pythonで距離行列を扱う例
Pythonを使って距離行列を扱う簡単な例を示します。ここでは3都市間の距離を表現し、全てのルートの距離を計算するコードです。
import numpy as np
from itertools import permutations
# 距離行列の定義（3都市）
D = np.array([[0, 10, 15],
[10, 0, 20],
[15, 20, 0]])
cities = [0, 1, 2]
min_distance = float('inf')
best_route = None
# 全ての巡回順序を探索
for perm in permutations(cities):
# 出発地点から戻る経路距離を計算
distance = sum(D[perm[i], perm[i+1]] for i in range(len(perm)-1))
distance += D[perm[-1], perm[0]]
if distance < min_distance:
min_distance = distance
best_route = perm
print(f"最短距離: {min_distance}")
print(f"最短ルート: {best_route}")
このコードは全探索により最短ルートを見つけますが、都市数が増えると計算量が急増するため、実用的にはヒューリスティックやメタヒューリスティックなどのアルゴリズムが使われます。
巡回セールスマン問題の重要性と応用例
巡回セールスマン問題（Traveling Salesman Problem、TSP）は、与えられた複数の都市をすべて一度ずつ訪問し、最後に出発点に戻る最短ルートを求める問題です。単純に見えるこの問題は、組合せ最適化の代表例として非常に重要視されています。実際のビジネスや物流、データ解析の分野で幅広く応用されているため、アルゴリズムの習得はデータサイエンスを学ぶ上で欠かせません。
数学的には、都市の集合を点の集合 \(V = \{v_1, v_2, \dots, v_n\}\) とし、都市間の距離を重み付きの辺として表します。目標は、すべての頂点を一度ずつ訪れ、総距離を最小化する巡回路（ハミルトン回路）を見つけることです。これを式で表すと、巡回路 \(C\) の長さは
\min_{C} \sum_{i=1}^{n} d(v_{c_i}, v_{c_{i+1}}), \quad \text{ただし } v_{c_{n+1}} = v_{c_1}
\]
ここで、\(d(v_i, v_j)\) は都市 \(v_i\) と \(v_j\) 間の距離を示し、\(C = (v_{c_1}, v_{c_2}, \dots, v_{c_n})\) は訪問順序を表します。この問題の難しさは、都市数が増えるごとに考慮すべきルートの数が爆発的に増える点にあります（可能な順列は \((n-1)!\) となります）。
例えば、実際の応用例としては以下のようなものがあります：
- 配送ルートの最適化：宅配業者が効率的に商品を届けるための経路計算
- 製造業の工程管理：複数の工程を最短時間で回るスケジューリング
- 遺伝子解析やネットワーク設計：膨大な組合せから最適な経路や配列を探索
ここでは、簡単な距離行列を用いた巡回セールスマン問題の距離計算方法をPythonで示します。まず、距離行列を用意し、あるルートの総距離を計算する関数を作成します。
import numpy as np
# 4都市の距離行列（対称行列）
distance_matrix = np.array([
[0, 10, 15, 20],
[10, 0, 35, 25],
[15, 35, 0, 30],
[20, 25, 30, 0]
])
def total_distance(route, dist_mat):
total = 0
n = len(route)
for i in range(n):
total += dist_mat[route[i], route[(i+1) % n]]
return total
# 例: ルート[0, 1, 3, 2]の距離を計算
route = [0, 1, 3, 2]
print(f"ルートの総距離: {total_distance(route, distance_matrix)}")
このコードは、与えられた「ルート（訪問順序）」の総距離を計算し、最適なルート探索の基礎となります。実際のアルゴリズムでは、これを用いて全探索やヒューリスティックな手法を繰り返し適用し、より良い解を見つけていきます。巡回セールスマン問題を理解することで、複雑なデータサイエンス問題の解析や最適化に役立つ考え方が身につきます。
巡回セールスマン問題の数式表現
巡回セールスマン問題（Traveling Salesman Problem、TSP）は、与えられた複数の都市をすべて一度ずつ訪問し、元の出発地に戻る最短経路を求める問題です。数学的には、グラフ理論の一種として表現され、都市を頂点、都市間の距離を辺の重みとする完全グラフ上の巡回路（ハミルトン閉路）を求める問題に帰着します。
例えば、都市の集合を \( V = \{1, 2, \ldots, n\} \) とし、都市 \( i \) と都市 \( j \) 間の距離を \( d_{ij} \) とします。巡回路は都市の順列 \( \pi = (\pi_1, \pi_2, \ldots, \pi_n) \) で表され、この巡回路の総距離は次のように定義されます。
\[
L(\pi) = \sum_{k=1}^{n-1} d_{\pi_k \pi_{k+1}} + d_{\pi_n \pi_1}
\]
ここで、最適な巡回路とは、全ての順列 \( \pi \) の中で \( L(\pi) \) を最小化するものです。つまり、
\[
\min_{\pi} L(\pi)
\]
この数式は、「すべての都市を一度ずつ訪れて元に戻る経路のうち、距離の合計が最も短いものを選ぶ」という問題を示しています。
次に、この数式の考え方をPythonで簡単に確認してみましょう。以下のコードは、都市間の距離行列を用いて、指定した順列の経路距離を計算する例です。
import numpy as np
# 都市間距離の例（4都市）
dist_matrix = np.array([
[0, 10, 15, 20],
[10, 0, 35, 25],
[15, 35, 0, 30],
[20, 25, 30, 0]
])
def calculate_route_length(route, dist_matrix):
length = 0
n = len(route)
for i in range(n - 1):
length += dist_matrix[route[i], route[i+1]]
length += dist_matrix[route[-1], route[0]] # 最後の都市から出発地へ戻る
return length
# 例：巡回路の順序 [0, 1, 2, 3]
route = [0, 1, 2, 3]
print("経路の距離:", calculate_route_length(route, dist_matrix))
このコードでは、都市間距離を行列で表現し、与えられた巡回路の距離を計算しています。実際のアルゴリズムでは、この計算を繰り返して最短の巡回路を探索しますが、問題の規模が大きくなると計算量が爆発的に増加するため、効率的なアルゴリズムや近似手法が必要となります。
巡回セールスマン問題の基本的な考え方
巡回セールスマン問題（Traveling Salesman Problem、TSP）は、与えられた複数の都市をすべて一度ずつ訪問し、最終的に出発点に戻る経路の中で「総移動距離（またはコスト）」を最小にする問題です。これは組合せ最適化の代表例であり、物流や配送ルートの最適化など実世界の課題に深く関わっています。
問題を数式で表現すると、都市の集合を \( V = \{1, 2, \ldots, n\} \) とし、都市 \(i\) から都市 \(j\) への距離（またはコスト）を \( d_{ij} \) とします。目的は、すべての都市を1回ずつ訪れる順序 \( (v_1, v_2, \ldots, v_n) \) を決めて、次の合計距離を最小化することです。
\[
\min_{(v_1, \ldots, v_n)} \sum_{k=1}^{n-1} d_{v_k v_{k+1}} + d_{v_n v_1}
\]
ここで、最後の項 \( d_{v_n v_1} \) は巡回のために出発点に戻る距離を表しています。
この問題の難しさは都市数が増えると経路の組合せが爆発的に増え、総当たり探索が現実的でなくなる点にあります。たとえば都市が10個なら訪問順序は約36万通りですが、20個になるとその数は約2.4兆通りに跳ね上がります。
Pythonでの簡単な距離計算例を示します。ここでは２次元座標の都市間距離をユークリッド距離で計算します。
import math
def distance(city1, city2):
return math.sqrt((city1[0] - city2[0])**2 + (city1[1] - city2[1])**2)
cities = [(0,0), (1,1), (2,0)]
total_dist = 0
route = [0, 1, 2]
for i in range(len(route)-1):
total_dist += distance(cities[route[i]], cities[route[i+1]])
total_dist += distance(cities[route[-1]], cities[route[0]]) # 戻る距離
print(f"合計距離: {total_dist:.2f}")
このコードは「都市の座標」リストから、指定されたルートの総距離を計算しています。実際のアルゴリズム開発では、こうした距離計算が基本となり、効率的な経路探索手法と組み合わせて最適解を目指します。
巡回セールスマン問題の難しさと計算量
巡回セールスマン問題（Traveling Salesman Problem、TSP）は、与えられた複数の都市をすべて一度ずつ訪問し、最短の経路で出発点に戻るルートを求める問題です。見た目は単純ですが、実際には計算量が非常に膨大になるため、効率的なアルゴリズム設計が求められます。
問題の難しさの一因は、都市の数が増えるごとに可能な経路の数が爆発的に増加することにあります。具体的には、都市の数を \( n \) とすると、全ての訪問順序のパターン数は以下のように表されます。
\[
(n-1)! = (n-1) \times (n-2) \times \cdots \times 2 \times 1
\]
この階乗（ファクトリアル）という計算は、都市が増えると桁違いに大きな数字となり、全探索による解決は現実的ではなくなります。例えば、10都市の場合でも \(9! = 362,880\) 通りの経路を調べる必要があります。
このようにTSPは「NP困難」と呼ばれるクラスに属し、効率的に最適解を求めることが非常に難しい問題です。そこで、実際には近似アルゴリズムや動的計画法を使って計算量を削減します。
動的計画法による計算量の削減例
動的計画法の一つの有名な手法は「ベルマン–ヘルド–カーグマン（Bellman–Held–Karp）アルゴリズム」です。これは部分集合ごとに最短経路を計算し、重複計算を避けることで計算量を大幅に減らします。
このアルゴリズムの計算量はおよそ
\[
O(n^2 \times 2^n)
\]
となり、全探索 \(O(n!)\) に比べて大幅に高速ですが、それでも都市数が増えると計算負荷は高くなります。
def tsp_dp(dist):
n = len(dist)
ALL_VISITED = (1 << n) - 1
memo = [[None] * n for _ in range(1 << n)]
def visit(visited, last):
if visited == ALL_VISITED:
return dist[last][0] # 出発点に戻るコスト
if memo[visited][last] is not None:
return memo[visited][last]
ans = float('inf')
for city in range(n):
if visited & (1 << city) == 0:
cost = dist[last][city] + visit(visited | (1 << city), city)
if cost < ans:
ans = cost
memo[visited][last] = ans
return ans
return visit(1, 0)
このコードは、距離行列 dist を受け取り、動的計画法で最短巡回路のコストを計算しています。
– visited は訪問済みの都市集合をビットで表現
– last は最後に訪れた都市
– すべての都市を訪れたら出発点に戻る距離を返す
– メモ化を使い、同じ状態の計算を繰り返さない
初心者でも理解しやすいように、計算量の爆発的増加と、それを抑えるためのアルゴリズムの工夫をイメージできることが大切です。巡回セールスマン問題はデータサイエンスの最適化問題としても重要なテーマであり、アルゴリズムの選択が実務の効率化に直結します。
“`html
巡回セールスマン問題を解く代表的なアルゴリズム
巡回セールスマン問題（TSP）は、与えられた複数の都市を一度ずつ訪れて元の都市に戻る最短経路を求める問題です。計算量が非常に大きくなるため、効率的なアルゴリズムが求められています。ここでは、初心者にも理解しやすい代表的なアルゴリズムを3つ紹介します。
- 1. 総当たり探索（ブルートフォース）
全ての都市の訪問順序を試す方法で、最も単純です。都市数が増えると計算量が爆発的に増えるため、実用的ではありませんが、問題の理解には役立ちます。計算量は約 \(O(n!)\) です。 - 2. 動的計画法（Held-Karp法）
巡回セールスマン問題の計算量を大幅に削減できる方法で、部分問題の解を再利用します。計算量は約 \(O(n^2 2^n)\) で、総当たりよりはるかに効率的です。具体的には、状態を「訪問済みの都市集合」と「現在の都市」で表現し、次の都市への最短経路を次のように定義します。
数式で表すと、都市の集合を \(S\)、現在位置を \(j\) としたとき、部分問題のコスト関数は
\[
C(S, j) = \min_{k \in S, k \neq j} \left[ C(S \setminus \{j\}, k) + d_{k,j} \right]
\]
ここで、\(d_{k,j}\) は都市 \(k\) から都市 \(j\) への距離です。初期条件は、出発点から他の都市への距離で設定します。
Pythonでの簡単な動的計画法の実装例は以下の通りです。
from functools import lru_cache
dist = [
[0, 10, 15, 20],
[10, 0, 35, 25],
[15, 35, 0, 30],
[20, 25, 30, 0]
]
@lru_cache(None)
def tsp(current, visited):
if visited == (1 << len(dist)) - 1:
return dist[current][0]
ans = float("inf")
for city in range(len(dist)):
if visited & (1 << city) == 0:
ans = min(ans, dist[current][city] + tsp(city, visited | (1 << city)))
return ans
print(tsp(0, 1))
- 3. 近似アルゴリズム（例：最近近傍法）
最適解を必ずしも求められませんが、計算が速く大規模な問題にも対応できます。現在いる都市から最も近い未訪問の都市を順に訪れる方法です。
これらのアルゴリズムはそれぞれメリット・デメリットがあり、問題の規模や求める精度によって使い分けられます。動的計画法は中規模までの問題に適しており、近似アルゴリズムは大規模問題で実用的です。初心者の方はまず動的計画法の仕組みを理解することで、巡回セールスマン問題の本質に近づけるでしょう。
“`
総当たり探索（全探索）
巡回セールスマン問題とは、複数の都市をすべて一度ずつ訪れて元の都市に戻る最短ルートを求める問題です。最もシンプルな解法の一つに「総当たり探索（全探索）」があります。これは、考えられるすべての都市の並び順（経路）を試して、その中で最も距離が短いものを選ぶ方法です。
例えば、都市数が \( n \) の場合、訪問順序の組み合わせは \((n-1)!\) 通りあります。ここで、1つの都市を出発点に固定することで、巡回の重複を避けています。つまり、総当たり探索の計算量は以下のように表せます：
\[
\text{計算量} = (n-1)!
\]
この計算量は都市の数が増えると急激に増大するため、\( n \) が大きくなると実用的ではありません。しかし、都市数が少ない場合には確実に最適解を見つけられる強力な手法でもあります。
総当たり探索のPythonコード例
Pythonの標準ライブラリ itertools の permutations を使うと、全ての経路パターンを簡単に生成できます。以下のコードでは、距離行列 dist に基づき、総当たり探索で最短経路を求めています。
import itertools
# 都市間の距離行列（例）
dist = [
[0, 10, 15, 20],
[10, 0, 35, 25],
[15, 35, 0, 30],
[20, 25, 30, 0]
]
n = len(dist)
cities = list(range(1, n)) # 出発点0以外の都市リスト
min_cost = float('inf')
best_route = None
for perm in itertools.permutations(cities):
cost = dist[0][perm[0]] # 出発点から最初の都市へ
for i in range(len(perm) - 1):
cost += dist[perm[i]][perm[i + 1]] # 各都市間の距離を加算
cost += dist[perm[-1]][0] # 最後の都市から出発点へ戻る
if cost < min_cost:
min_cost = cost
best_route = perm
print("最短距離:", min_cost)
print("最短経路:", (0,) + best_route + (0,))このコードの流れは「式 → 解釈 → コード」で説明すると：
- 式：すべての順列 \(\pi\) に対して、経路長を計算します。
\[
\text{コスト}(\pi) = d_{0, \pi_1} + \sum_{i=1}^{n-2} d_{\pi_i, \pi_{i+1}} + d_{\pi_{n-1}, 0}
\]
ここで \(d_{i,j}\) は都市 \(i\) から都市 \(j\) への距離を表します。 - 解釈：出発都市0からスタートし、順列で定められた順番で各都市を巡回、最後に出発都市へ戻る合計距離を計算しています。
- コード：Pythonで全ての並び順を生成し、それぞれの経路距離を計算、最短距離と経路を更新しています。
総当たり探索は単純で理解しやすいものの、都市数が多くなると計算時間が膨大になるため、より効率的なアルゴリズムと組み合わせて使うことが多いです。本記事ではこの後、より高速なアルゴリズムも紹介します。
動的計画法（Held-Karpアルゴリズム）
巡回セールスマン問題（TSP）は、すべての都市を一度ずつ訪れ、元の都市に戻る最短経路を求める問題です。都市数が増えると組み合わせが爆発的に増えるため、単純な全探索は現実的ではありません。そこで、動的計画法の一種であるHeld-Karpアルゴリズムが活躍します。
Held-Karpアルゴリズムは、部分問題の結果をメモ化しながら最適解を求める手法です。具体的には、訪問済みの都市の集合と現在いる都市を状態として管理し、次に訪れる都市を再帰的に決定していきます。
数学的には、次のように定義されます。都市集合 \( S \) と現在の都市を \( j \) としたとき、部分問題の最短経路コストを \( C(S, j) \) とします。すると、再帰的に以下の式で表せます：
\[
C(S, j) = \min_{i \in S, i \neq j} \left[ C(S \setminus \{j\}, i) + d_{i,j} \right]
\]
ここで、\( d_{i,j} \) は都市 \( i \) から都市 \( j \) への距離です。初期条件として、出発点 \( 0 \) から各都市への距離は以下のように設定します：
\[
C(\{0, j\}, j) = d_{0,j}
\]
この式は「訪問済み集合 \( S \) の中で、最後に訪れた都市が \( j \) のときの最短経路」を意味し、再帰的に部分問題を解いていくことで全体の最適解を導きます。
以下にPythonで簡単な実装例を示します。都市数が多いと計算量が増えるため、小規模の問題で使うのが現実的です。
from itertools import combinations
def held_karp(dist):
n = len(dist)
C = {}
for k in range(1, n):
C[(frozenset([0, k]), k)] = dist[0][k]
for subset_size in range(2, n):
for subset in combinations(range(1, n), subset_size):
subset_frozenset = frozenset([0] + list(subset))
for j in subset:
prev_subset = subset_frozenset - frozenset([j])
C[(subset_frozenset, j)] = min(
C[(prev_subset, k)] + dist[k][j] for k in subset if k != j
)
full_set = frozenset(range(n))
return min(C[(full_set, j)] + dist[j][0] for j in range(1, n))
このコードでは、距離行列 dist を入力とし、部分集合と現在地の組み合わせを辞書 C で管理しています。最後に、すべての都市を訪問した状態から元の都市に戻る最短コストを求めています。
Held-Karpアルゴリズムは計算量が \(O(n^2 2^n)\) と、全探索よりは効率的ですが都市数が多いとまだ計算負荷が高いです。しかし、動的計画法の基本的な考え方や状態管理を学ぶには非常に良い教材となります。
分枝限定法
巡回セールスマン問題（TSP）は、すべての都市を一度ずつ訪れて最短経路を求めるという組合せ最適化問題で、都市数が増えると計算量が急激に増大します。分枝限定法は、探索空間を効率的に絞り込むことで、計算負荷を抑えつつ最適解を見つけるアルゴリズムの一つです。
分枝限定法の基本的な考え方は、探索の「分枝」と「限定」の２つのステップに分かれます：
- 分枝（Branching）: 問題を部分問題に分割し、探索ツリーの各ノードに対応させる。
- 限定（Bounding）: 部分問題の下限コストを計算し、その値が現在の最良解より悪ければその枝を切り捨てる。
例えば、現在の部分経路の距離を \(d\)、まだ訪れていない都市の最小追加コストの下限を \(h\) とすると、部分問題の下限コストは
\[ L = d + h \]
で表されます。この \(L\) が既に見つかっている最短経路のコストより大きければ、その部分問題は最適解を含まないと判断して探索を打ち切ります。
以下はPythonで分枝限定法の骨組みを示した例です。実際にはヒューリスティックな下限コスト計算や優先度付きキューを用いて効率化しますが、ここでは概念的な実装に留めます。
from math import inf
def branch_and_bound(graph):
n = len(graph)
best_cost = inf
best_path = []
def dfs(path, visited, current_cost):
nonlocal best_cost, best_path
if len(path) == n:
total_cost = current_cost + graph[path[-1]][path[0]]
if total_cost < best_cost:
best_cost = total_cost
best_path = path[:]
return
# 下限コストの簡易計算（ここでは未訪問都市の最小辺を合計）
remaining = [i for i in range(n) if i not in visited]
min_edge_sum = sum(min(graph[i][j] for j in range(n) if j != i) for i in remaining)
lower_bound = current_cost + min_edge_sum
if lower_bound >= best_cost:
return # これ以上探索しても最良解は得られないので枝刈り
for next_city in remaining:
dfs(path + [next_city], visited | {next_city}, current_cost + graph[path[-1]][next_city])
dfs([0], {0}, 0)
return best_cost, best_path
このように、分枝限定法は単純な全探索よりも効率的に最適解を探せるため、中規模のTSPに有効です。下限コストの計算方法や探索の順序を工夫することで、さらに高速化が可能です。
近似アルゴリズム
巡回セールスマン問題（TSP）は、すべての都市を一度ずつ訪れて最小の移動距離を求める問題で、正確解を求めるのは都市数が増えると計算量が爆発的に増加します。そこで実用的には「近似アルゴリズム」が用いられ、最適解に限りなく近い解を効率的に得る手法が注目されています。
代表的な近似アルゴリズムの一つに「最近傍法（Nearest Neighbor）」があります。これは現在いる都市から最も近い未訪問の都市を次に選び、すべての都市を巡る方法です。式で表すと、都市集合 \(V\) の中で現在地を \(v_i\)、未訪問の集合を \(U\) とすると、次に訪れる都市 \(v_j\) は
\[
v_j = \underset{v \in U}{\arg\min} \ d(v_i, v)
\]
ここで \(d(v_i, v)\) は都市間の距離を表します。この単純なルールにより計算量は大幅に削減され、都市数が多くても高速に経路を求められます。
以下はPythonで最近傍法を実装した例です。距離はユークリッド距離を用いています。
import numpy as np
def nearest_neighbor(cities):
n = len(cities)
visited = [False] * n
path = [0] # 最初の都市を0番目とする
visited[0] = True
for _ in range(n - 1):
last = path[-1]
dist = np.full(n, np.inf)
for i in range(n):
if not visited[i]:
dist[i] = np.linalg.norm(cities[last] - cities[i])
next_city = np.argmin(dist)
path.append(next_city)
visited[next_city] = True
return path
このように近似アルゴリズムは、厳密な最適解ではないものの、計算資源を節約しつつ実用的な解を得るために非常に有用です。特にデータサイエンスの現場では、膨大なデータを扱うため高速な近似手法が求められます。将来的には、より精度の高い近似やメタヒューリスティックな手法にも挑戦してみましょう。
Pythonで巡回セールスマン問題を解く準備
巡回セールスマン問題（TSP）は、与えられた複数の都市をすべて一度だけ訪れ、元の都市に戻る最短経路を求める問題です。Pythonでこの問題を解くためには、まず問題の数理モデルを理解し、必要なライブラリの準備や基本的なデータ構造の作成から始めましょう。
1. 巡回セールスマン問題の数式モデル
TSPはグラフ理論で表現され、都市を頂点、都市間の距離を辺の重みとします。最短経路を求めるための目的関数は、全ての訪問経路の合計距離を最小化することです。ここで、都市の集合を \( V = \{1, 2, \dots, n\} \)、都市間の距離を \( d_{ij} \) とすると、巡回路の距離の総和は次のように表されます。
\[
\min \sum_{i=1}^{n} \sum_{j=1, j \neq i}^{n} d_{ij} x_{ij}
\]
ここで、変数 \( x_{ij} \) は都市 \( i \) から都市 \( j \) へ移動する場合に1、それ以外は0となる二値変数です。この制約条件を加えて、すべての都市が一度だけ訪問される巡回路を形成します。
2. Pythonでの準備作業
次にPythonでTSPを解くための準備として、距離行列の作成と必要なライブラリのインストールを行います。ここでは代表的な距離行列の生成方法を紹介します。例えば、5都市の間の距離を2次元座標からユークリッド距離で計算する場合は以下のように実装できます。
import numpy as np
# 各都市の座標 (x, y)
cities = np.array([
[0, 0],
[1, 3],
[4, 3],
[6, 1],
[3, 0]
])
# 距離行列の作成（ユークリッド距離）
def calculate_distance_matrix(points):
n = len(points)
dist_matrix = np.zeros((n, n))
for i in range(n):
for j in range(n):
dist_matrix[i, j] = np.linalg.norm(points[i] - points[j])
return dist_matrix
distance_matrix = calculate_distance_matrix(cities)
print(distance_matrix)
この距離行列は、TSPの入力として使います。巡回セールスマン問題のアルゴリズムは、この行列を基に最短経路を探索します。次のステップでは、これを使って具体的なアルゴリズムを実装していきます。
Pythonによる総当たり探索の実装例
巡回セールスマン問題（TSP）は、与えられた複数の都市をすべて一度ずつ訪れ、最短の経路を求める問題です。最も基本的な解法の一つに「総当たり探索（全探索）」があります。これは、全ての都市の訪問順序を試し、それぞれの経路長を計算して最短経路を見つける方法です。
総当たり探索のアルゴリズムの肝は、都市の順列を生成し、各順列の距離を計算する点にあります。都市の数を \(n\) とすると、順列の総数は \(n!\)（階乗）となり、都市数が増えると計算量が急激に増加するため、現実的には小規模問題に適しています。
ここで、距離の計算を考えます。2点間の距離をユークリッド距離で表すと、都市 \(i\) の座標 \((x_i, y_i)\) と都市 \(j\) の座標 \((x_j, y_j)\) の距離は次のようになります。
\[
d(i, j) = \sqrt{(x_i – x_j)^2 + (y_i – y_j)^2}
\]
この距離を使って、順列で表される経路の総距離を求めます。経路を \(\pi = (\pi_1, \pi_2, \ldots, \pi_n)\) としたとき、総距離は
\[
D(\pi) = \sum_{k=1}^{n-1} d(\pi_k, \pi_{k+1}) + d(\pi_n, \pi_1)
\]
最後に出発点に戻る距離も加えます。以下にPythonでの総当たり探索の実装例を示します。標準ライブラリの itertools.permutations を使って全順列を生成し、最短経路を求めています。
import math
from itertools import permutations
# 都市の座標リスト（例）
cities = [(0, 0), (1, 3), (4, 3), (6, 1)]
def distance(city1, city2):
return math.sqrt((city1[0] - city2[0])**2 + (city1[1] - city2[1])**2)
def total_distance(route):
dist = 0
for i in range(len(route) - 1):
dist += distance(route[i], route[i+1])
dist += distance(route[-1], route[0]) # 最後に出発点に戻る距離
return dist
min_route = None
min_dist = float('inf')
for perm in permutations(cities):
dist = total_distance(perm)
if dist < min_dist:
min_dist = dist
min_route = perm
print("最短距離:", min_dist)
print("最短経路:", min_route)
このコードでは、4つの都市のすべての訪問順序を試し、最短距離とその経路を出力します。実行時間は都市数の増加に伴い急激に長くなるため、実際の大規模問題では別の効率的なアルゴリズムが必要です。しかし、初学者がTSPの基本的な考え方やアルゴリズムを理解するには適した方法です。
Pythonで動的計画法を使った解法の実装例
巡回セールスマン問題（TSP）は、全ての都市を一度ずつ訪れ、最短の経路を見つける問題です。全探索では計算量が爆発的に増えるため、動的計画法を用いることで計算効率を改善できます。ここでは、動的計画法の考え方からPythonのコード例まで初心者向けに解説します。
まず、動的計画法の基本アイデアは「部分問題の最適解を組み合わせて全体の最適解を求める」ことです。TSPの場合、訪問済みの都市集合と現在の位置を状態として管理します。状態を次のように表現します：
- \( S \)：訪問済みの都市の集合（ビットマスクで表現）
- \( j \)：現在いる都市
このとき、部分問題の最小コストを
\( dp(S, j) \)
と表すと、遷移式は以下のようになります。
\( dp(S, j) = \min_{i \in S, i \neq j} \left[ dp(S \setminus \{j\}, i) + dist_{i, j} \right] \)
ここで、\( dist_{i, j} \) は都市 \( i \) から都市 \( j \) への距離です。つまり、現在の集合 \( S \) において、最後に訪れた都市が \( j \) である場合の最小コストは、\( j \) を除いた集合で最後に訪れた都市 \( i \) から \( j \) に移動するコストを加えた最小値となります。
この式をPythonで実装すると次のようになります。
import sys
def tsp(dist):
n = len(dist)
dp = [[float('inf')] * n for _ in range(1 << n)]
dp[1][0] = 0 # スタート地点は都市0とする
for S in range(1 << n):
for j in range(n):
if not (S & (1 << j)):
continue
for k in range(n):
if S & (1 << k) and k != j:
dp[S][j] = min(dp[S][j], dp[S ^ (1 << j)][k] + dist[k][j])
# 全ての都市を訪問した状態からスタート地点に戻るコストを足す
full = (1 << n) - 1
ans = min(dp[full][j] + dist[j][0] for j in range(1, n))
return ans
このコードでは、都市数 \( n \) と距離行列 dist を入力とし、bit全探索で訪問済み集合を表現しています。dp[S][j] は集合 S の都市を訪問し最後に都市 j にいるときの最短距離を保持します。動的計画法を使うことで、指数的な探索空間を大幅に削減し、現実的な都市数まで計算できます。
このように、巡回セールスマン問題の動的計画法は、数式での状態遷移を理解し、それを効率的にコード化することがポイントです。初心者の方もまずは小規模な距離行列で動作を確認し、理解を深めていくことをおすすめします。
分枝限定法のPython実装のポイント
巡回セールスマン問題（TSP）を解く分枝限定法は、探索空間を効率的に絞り込むことで計算量を削減するアルゴリズムです。初心者にとっては「どのように無駄な探索を排除するか」がポイントになります。ここでは、Pythonでの実装時に意識したい基本的な考え方とコード例を紹介します。
分枝限定法では、部分解の評価関数として「下界（lower bound）」を用います。これは、現在の部分経路に対して「これ以上小さくならない距離の見積もり」を意味し、下界が既存の最良解より悪ければ、その枝は探索しないで打ち切ります。
具体的な数式で示すと、ある部分経路の下界 \(LB\) は以下のように表せます。
\[
LB = \text{現在の訪問済み経路の距離} + \text{未訪問都市の最小コストの合計}
\]
ここで「未訪問都市の最小コストの合計」は、訪問していない都市から他の都市への最小距離を足し合わせたものです。これにより、これ以上の距離短縮が不可能なら探索を打ち切れます。
Pythonでのコード例は以下の通りです。都市間距離を格納した2次元リスト dist と、現在の部分経路 path、訪問済みフラグ visited を用いて下界を計算します。
def calculate_lower_bound(dist, path, visited):
n = len(dist)
current_distance = 0
last = path[-1]
# 現在の経路距離を計算
for i in range(len(path) - 1):
current_distance += dist[path[i]][path[i+1]]
# 未訪問都市の最小コストの合計を計算
min_edge_sum = 0
for city in range(n):
if not visited[city]:
min_edge = float('inf')
for k in range(n):
if city != k:
min_edge = min(min_edge, dist[city][k])
min_edge_sum += min_edge
return current_distance + min_edge_sum
この関数を使い、探索中に下界が現在の最短経路の距離を超えた場合は、その探索枝を打ち切る判断をします。こうすることで、全探索を避けつつ、最適解に近づくことが可能です。
分枝限定法の要点は次の通りです。
- 部分経路の評価（下界）を正確かつ効率的に計算すること
- 既存の最良解を更新しながら、探索空間を狭めていくこと
- Pythonの再帰やスタックを活用して、分枝の展開と打ち切りを管理すること
初心者はまず「下界の計算ロジック」と「探索の打ち切り条件」に注目し、コードを書きながら理解を深めると良いでしょう。
近似アルゴリズムをPythonで試す方法
巡回セールスマン問題（TSP）は都市数が増えると計算量が爆発的に増えるため、すべての経路を調べるのは現実的ではありません。そこで、近似アルゴリズムを使って「十分良い」解を効率的に求める方法がよく使われます。ここでは初心者でも理解しやすい「最近点ヒューリスティック法」をPythonで実装しながら解説します。
まず、都市間の距離の計算を数式で表すと、2点 \((x_i, y_i)\)、\((x_j, y_j)\) 間のユークリッド距離は次のようになります。
\[
d_{ij} = \sqrt{(x_i – x_j)^2 + (y_i – y_j)^2}
\]
これを使って、現在の都市から最も近い未訪問の都市を順に選び、経路を作るのが最近点法の基本アイデアです。Pythonでの距離計算と近い都市探しは次のコードのようになります。
import numpy as np
def euclidean_distance(a, b):
return np.sqrt(np.sum((a - b) ** 2))
def nearest_neighbor_tsp(cities):
n = len(cities)
visited = [False] * n
path = [0]
visited[0] = True
for _ in range(n - 1):
last = path[-1]
next_city = None
min_dist = float('inf')
for i in range(n):
if not visited[i]:
dist = euclidean_distance(cities[last], cities[i])
if dist < min_dist:
min_dist = dist
next_city = i
path.append(next_city)
visited[next_city] = True
return path
この関数では、まず最初の都市（インデックス0）からスタートし、未訪問の都市の中で最も距離が近い都市を1つずつ選んでいます。こうすることで計算量はおよそ \(O(n^2)\) となり、大きな都市数でも比較的高速に経路を求めることが可能です。
実際に都市の座標を用意して試すと、巡回セールスマン問題の近似解を簡単に得られます。もちろんこの方法は最短経路を保証するわけではありませんが、初学者がTSPのアルゴリズムの感覚を掴むにはとても良い出発点です。
巡回セールスマン問題の可視化方法
巡回セールスマン問題（TSP）は、複数の都市をすべて一度ずつ訪れ、最短ルートを見つける問題です。アルゴリズムの理解を深めるためには、問題の可視化が非常に役立ちます。ここでは、Pythonを使った基本的な可視化手法を紹介します。
まず、都市の座標を2次元平面上に点としてプロットし、訪問順に線で結ぶ方法が一般的です。これにより、ルートの全体像が直感的に把握できます。例えば、都市の座標を \((x_i, y_i)\) とし、訪問順序を示す経路をリストで表します。
距離の計算はユークリッド距離がよく使われ、2点間の距離は次の式で表されます。
\[
d_{ij} = \sqrt{(x_i – x_j)^2 + (y_i – y_j)^2}
\]
この距離を使って、巡回経路の総距離を計算し、最小化することが問題の目的です。
以下はPythonのライブラリ matplotlib を用いて、都市とルートを可視化する簡単なコード例です。
import matplotlib.pyplot as plt
# 都市の座標（例）
cities = [(2, 3), (5, 7), (9, 6), (4, 1), (7, 2)]
# 訪問順序の例
route = [0, 3, 4, 2, 1, 0] # 最後に出発点に戻る
# x座標とy座標を分ける
x = [cities[i][0] for i in route]
y = [cities[i][1] for i in route]
plt.figure(figsize=(8,6))
plt.plot(x, y, 'o-', color='blue')
for i, (xi, yi) in enumerate(cities):
plt.text(xi, yi, f'City {i}', fontsize=12)
plt.title("巡回セールスマン問題のルート可視化")
plt.xlabel("X座標")
plt.ylabel("Y座標")
plt.grid(True)
plt.show()このコードでは、都市の位置を点で示し、訪問順に線で結ぶことでルートを視覚的に表現しています。初心者でも簡単に実装でき、アルゴリズムの結果を確認しやすくなるため、ぜひ試してみてください。
実際のデータを使った巡回セールスマン問題の解決例
巡回セールスマン問題（TSP）は、与えられた複数の都市をすべて一度ずつ訪れ、最短の経路を求める問題です。ここでは、Pythonを使い、簡単な距離行列から最適経路を求める基本的なアルゴリズムの例を紹介します。実際のデータとして5つの都市の座標を用い、それらの間の距離を計算し、総移動距離が最小となる巡回ルートを探します。
距離行列の計算
まず、点 \( (x_i, y_i) \) と \( (x_j, y_j) \) の間の距離はユークリッド距離で表され、次の式で計算されます。
\[
d_{ij} = \sqrt{(x_i – x_j)^2 + (y_i – y_j)^2}
\]
この距離行列は問題を解くための基礎データとなります。
Pythonコードによる距離行列の作成と簡易的な解法
以下は、5つの都市の座標から距離行列を計算し、全ての巡回ルートを試して最短距離を求める単純な全探索の例です。都市数が増えると計算量が爆発的に増えるため、実務ではより効率的なアルゴリズムが必要です。
import itertools
import numpy as np
# 都市の座標（例）
cities = np.array([
[0, 0],
[1, 5],
[5, 2],
[6, 6],
[8, 3]
])
# 距離行列の計算
def calc_distance_matrix(points):
n = len(points)
dist_matrix = np.zeros((n, n))
for i in range(n):
for j in range(n):
dist_matrix[i, j] = np.sqrt((points[i, 0] - points[j, 0])**2 + (points[i, 1] - points[j, 1])**2)
return dist_matrix
dist_matrix = calc_distance_matrix(cities)
# 全巡回経路の中で最短経路を探索
def tsp_brute_force(dist_matrix):
n = len(dist_matrix)
min_path = None
min_dist = float('inf')
for perm in itertools.permutations(range(1, n)):
path = (0,) + perm + (0,)
total_dist = sum(dist_matrix[path[i], path[i+1]] for i in range(n))
if total_dist < min_dist:
min_dist = total_dist
min_path = path
return min_path, min_dist
best_path, best_distance = tsp_brute_force(dist_matrix)
print("最短経路:", best_path)
print("総距離:", best_distance)
このコードでは、全ての可能な経路を試し、最短距離を持つルートを見つけています。結果は、出発点に戻る最短の巡回ルートとその総距離として表示されます。初心者には全探索が理解しやすいですが、都市数が多い場合は効率的なアルゴリズム（例えば、動的計画法や遺伝的アルゴリズム）を検討しましょう。
アルゴリズム選択のポイントと注意点
巡回セールスマン問題（TSP）は、与えられた複数の都市をすべて一度ずつ訪れて元の都市に戻る最短経路を求める問題です。アルゴリズム選択の際には、以下のポイントを押さえることが重要です。
- 問題の規模に応じた選択
都市数が少ない場合は、全探索（総当たり）でも計算可能ですが、都市数が増えると計算量が爆発的に増加します。TSPの計算量は一般的に \(O(n!)\) であり、都市数 \(n\) が増えると現実的に解けなくなります。 - 近似アルゴリズムの利用
大規模問題では、正確解を求めるのが難しいため、ヒューリスティックやメタヒューリスティック（例えば、遺伝的アルゴリズムやシミュレーテッドアニーリング）が使われます。これらは厳密解ではないものの、実用的な時間で良好な解を得られます。 - 問題の性質に応じたアルゴリズム選択
例えば、距離が対称か非対称か、制約条件の有無によって適切なアルゴリズムは異なります。
ここで、単純な動的計画法（Held-Karpアルゴリズム）の数式を紹介します。部分集合 \(S\) と現在の都市 \(j\) に対して、最短経路のコストを \(C(S,j)\) と表すと：
\[
C(S,j) = \min_{k \in S, k \neq j} \left[ C(S \setminus \{j\}, k) + d_{k,j} \right]
\]
ここで、\(d_{k,j}\) は都市 \(k\) から都市 \(j\) までの距離です。この式は「部分集合 \(S\) の中で都市 \(j\) に最後に到達する経路の最短距離は、\(j\) 以外の都市 \(k\) から来る最短経路に距離 \(d_{k,j}\) を足したものの最小値」という意味です。
Pythonでの簡単な実装例は以下の通りです（詳細な最適化は省略）：
def held_karp(dist):
n = len(dist)
C = {}
for k in range(1, n):
C[(frozenset([0, k]), k)] = dist[0][k]
for subset_size in range(2, n):
for subset in (frozenset(comb) | frozenset([0])
for comb in itertools.combinations(range(1, n), subset_size)):
for j in subset:
if j == 0:
continue
prev_subset = subset - frozenset([j])
C[(subset, j)] = min(
C[(prev_subset, k)] + dist[k][j] for k in subset if k != 0 and k != j
)
full_set = frozenset(range(n))
res = min(C[(full_set, j)] + dist[j][0] for j in range(1, n))
return res
このように、アルゴリズム選択は問題規模や目的に応じて慎重に行うことが重要です。初心者の方は、まず小規模問題で動的計画法や近似アルゴリズムを試しながら理解を深めることをおすすめします。
巡回セールスマン問題のさらなる学習リソース紹介
巡回セールスマン問題（TSP）は、単純に見えて実は非常に奥が深い問題です。初心者の方がアルゴリズムの理解を深め、実践的なスキルを身につけるためには、良質な学習リソースを活用することが重要です。ここでは、数学的な理解とPythonによる実装の両面から学べるおすすめのリソースを紹介します。
数学的背景を理解するためのリソース
TSPの本質はグラフ理論と組合せ最適化にあります。まずは問題の定式化を復習しましょう。巡回セールスマン問題は、訪問すべき都市の集合を \( V \)、都市間の距離を重み付きグラフの辺として表します。目的は、全ての都市を一度ずつ訪れ、元の都市に戻る最短経路（ハミルトン閉路）を見つけることです。数学的には、次のように定式化できます。
巡回経路を表す変数 \( x_{ij} \) を用いて、
\[
\min \sum_{i \in V} \sum_{j \in V, j \neq i} d_{ij} x_{ij}
\]
ここで、\( d_{ij} \) は都市 \( i \) と \( j \) 間の距離、\( x_{ij} \) は辺 \( (i,j) \) が巡回路に含まれるかを示す二値変数です。制約条件として、各都市から出る辺は1本、入る辺も1本であることを課します。
この定式化を理解するためには、グラフ理論や線形計画法の基礎知識が役立ちます。おすすめの教科書としては、『組合せ最適化入門』や『線形計画法とネットワークフロー』があります。
Pythonで巡回セールスマン問題を解く入門例
次に、Pythonで簡単な近似アルゴリズムを実装してみましょう。ここでは、「貪欲法（Greedy Algorithm）」を使った例を示します。貪欲法は、現在地から最も近い未訪問の都市へ移動するという単純な戦略です。
def greedy_tsp(dist_matrix):
n = len(dist_matrix)
visited = [False] * n
path = [0] # 最初の都市からスタート
visited[0] = True
for _ in range(n - 1):
last = path[-1]
next_city = min(
(dist_matrix[last][j], j) for j in range(n) if not visited[j]
)[1]
path.append(next_city)
visited[next_city] = True
path.append(0) # 最初の都市に戻る
return path
このコードは、距離行列 dist_matrix を入力とし、訪問順序のリスト path を返します。貪欲法は必ずしも最適解を保証しませんが、問題の理解やアルゴリズムの基礎を掴むには最適です。
追加で学ぶべきポイント
- 最適化手法の学習: 分枝限定法、動的計画法、メタヒューリスティクス（遺伝的アルゴリズムやシミュレーテッドアニーリング）など、より高度な手法を段階的に学びましょう。
- Pythonライブラリの活用:
networkxやscipy.optimizeなどのツールでTSPのモデル化やアルゴリズム実装を効率化できます。 - オンライン講座やチュートリアル: CourseraやUdemyなどで、組合せ最適化やアルゴリズム設計に特化した講座を活用するのも効果的です。
これらのリソースを活用しながら、数式で問題を正しく理解し、Pythonで手を動かして実装することで、巡回セールスマン問題のアルゴリズムを着実に身につけることができます。