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

提供: ORWiki
2007年7月4日 (水) 15:25時点における122.26.167.76 (トーク)による版
ナビゲーションに移動 検索に移動

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

 点集合 $V$,枝集合 $E$ から構成されるグラフ $G=(V,E)$, 枝 $(i,j) \in E$ 上の距離 $d_{ij}$ が与えられたとき,点集合 $V$ のすべての点をちょうど1回ずつ経由する巡回路(ハミルトン閉路)で,枝の距離の合計を最小にするものを求める問題を巡回セールスマン問題 (traveling salesman problem) (行商人問題)とよぶ.

 特に,距離の対称性($d_{ij}=d_{ji}$)を満たすものを対称巡回セールスマン問題,3角不等式($d_{ij} \leq d_{ik} + d_{kj}$)を満たすものを3角不等式を満たす巡回セールスマン問題,点集合が $d$ 次元超立方体 $[0,1]^d$ 内に分布しており,$2$ 点間の距離が点間のユークリッド距離で定義されたものをユークリッド巡回セールスマン問題 (Euclidean (Euclidian) traveling salesman problem) とよぶ.

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

 巡回セールスマン問題は,NP困難 (NP-hard) であり, 多項式時間の厳密解法が絶望視されているばかりでなく,近似比が 一定値$\alpha (<\infty)$ で抑えられる多項式時間の近似解法さえ${\rm P} \neq {\rm NP}$ のもとでは存在しないことが示されている.

 3角不等式を満たす対称巡回セールスマン問題に対しては,近似比が $3/2$ 以下の保証をもつ多項式時間の近似解法が知られている.また,$d$ を定数としたときの $d$ 次元ユークリッド巡回セールスマン問題に対しては,固定された $\epsilon >0$ を与えたときに,近似比が $1+\epsilon$ 以下に抑えられる多項式時間の近似解法(近似スキーム)が存在する.

 実用的な近似解法としては,最近近傍法 (nearest neighbor method) やセービング法 (saving method) によって構築された巡回路をk-opt法 {{$k$}-opt法}($k$-opt)で改善する方法が一般的である.厳密解法としては,巡回セールスマン問題の多面体構造(TSP多面体(TSP polytope))を利用した分枝カット法 (branch and cut method) が有効であり,実務的な大規模問題の求解に成功している.



参考文献

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