問題
巡回セールスマン問題（TSP）の計算複雑性に関する記述として正しいものはどれか。
選択肢
- 1P クラスに属し多項式時間で厳密解が得られる
- 2NP 困難であり、現時点で多項式時間アルゴリズムは知られていない
- 3NP に属するが P に含まれることが証明されている
- 4常に O(n log n) で解ける
正解
2. NP 困難であり、現時点で多項式時間アルゴリズムは知られていない
詳しい解説を見る解説を閉じる
解説
TSP の判定版（一定距離以下の巡回路存在判定）は NP 完全、最適化版は NP 困難に属する代表的問題で、現時点では決定性多項式時間アルゴリズムは未発見である（P=NP 問題が未解決）。厳密解には動的計画法（ビット DP）で O(n^2·2^n)、近似解には最近近傍法（任意倍率まで悪化し得る）、最小全域木ベース 2-近似（対称距離・三角不等式成立時）、Christofides 1.5-近似などが知られる。物流・配車最適化で頻出。
一問一答
全400問を繰り返し学習