《巡回セールスマン問題》

【じゅんかいせーるすまんもんだい (traveling salesman problem) 】

　点集合 $V\,$，枝集合 $E\,$ から構成されるグラフ $G=(V,E)\,$, 枝 $(i,j)\in E\,$ 上の距離 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle d_{ij}\, } が与えられたとき，点集合 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle V\, } のすべての点をちょうど1回ずつ経由する巡回路（ハミルトン閉路）で，枝の距離の合計を最小にするものを求める問題を巡回セールスマン問題 (traveling salesman problem) （行商人問題）とよぶ．

　特に，距離の対称性（構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle d_{ij}=d_{ji}\, } ）を満たすものを対称巡回セールスマン問題，3角不等式（構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle d_{ij} \leq d_{ik} + d_{kj}\, } ）を満たすものを3角不等式を満たす巡回セールスマン問題，点集合が 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle d\, } 次元超立方体 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle [0,1]^d\, } 内に分布しており，$2\,$ 点間の距離が点間のユークリッド距離で定義されたものをユークリッド巡回セールスマン問題 (Euclidean (Euclidian) traveling salesman problem) とよぶ．

　巡回セールスマン問題に対する応用は，数百点を扱う基盤配線，運搬経路計画，スケジューリング，数万点を扱う基盤穿孔，X線結晶構造解析 (タンパク質の構造解析)，数百万点を扱うVLSI設計など，さまざまである．また，次世代のVLSI設計においては，数千万点の問題を解く必要があると言われている．

　巡回セールスマン問題は，NP困難 (NP-hard) であり, 多項式時間の厳密解法が絶望視されているばかりでなく，近似比が 一定値構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \alpha (<\infty)\, } で抑えられる多項式時間の近似解法さえ${\rm {P}}\neq {\rm {NP}}\,$ のもとでは存在しないことが示されている．

　3角不等式を満たす対称巡回セールスマン問題に対しては，近似比が $3/2\,$ 以下の保証をもつ多項式時間の近似解法が知られている．また，構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle d\, } を定数としたときの 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle d\, } 次元ユークリッド巡回セールスマン問題に対しては，固定された 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \epsilon >0\, } を与えたときに，近似比が 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle 1+\epsilon\, } 以下に抑えられる多項式時間の近似解法（近似スキーム）が存在する．

　実用的な近似解法としては，最近近傍法 (nearest neighbor method) やセービング法 (saving method) によって構築された巡回路をk-opt法 (構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle k\, } -opt)で改善する方法が一般的である．厳密解法としては，巡回セールスマン問題の多面体構造（TSP多面体(TSP polytope)）を利用した分枝カット法 (branch and cut method) が有効であり，実務的な大規模問題の求解に成功している．

---

参考文献

[1] 山本芳嗣, 久保幹雄,『巡回セールスマン問題への招待』, 朝倉書店，1997.