「巡回セールスマン問題」の版間の差分

提供: ORWiki
ナビゲーションに移動 検索に移動
(基礎編と用語編のマージ)
1行目: 1行目:
 
'''【じゅんかいせーるすまんもんだい (traveling salesman problem (TSP))】'''
 
'''【じゅんかいせーるすまんもんだい (traveling salesman problem (TSP))】'''
  
 +
=== 概要 ===
 
枝に重みを与えたグラフ<math>G\,</math>において, すべての点を丁度1度ずつ訪問して元に戻る巡回路(ハミルトン閉路)のうち, 総重みを最小にするものを求める問題. グラフの枝が有向であるか無向であるかで大別する. 平面上(あるいは空間内)の<math>n\,</math>点と各点の間の距離が与えられたとき, すべての点を訪問する順回路のうち最短のものを求める問題, と定義されることもある. 代表的な組合せ最適化問題の1つ.
 
枝に重みを与えたグラフ<math>G\,</math>において, すべての点を丁度1度ずつ訪問して元に戻る巡回路(ハミルトン閉路)のうち, 総重みを最小にするものを求める問題. グラフの枝が有向であるか無向であるかで大別する. 平面上(あるいは空間内)の<math>n\,</math>点と各点の間の距離が与えられたとき, すべての点を訪問する順回路のうち最短のものを求める問題, と定義されることもある. 代表的な組合せ最適化問題の1つ.
  
詳しくは[[《巡回セールスマン問題》|基礎編:巡回セールスマン問題]]を参照.
+
=== 詳説 ===
 +
 点集合 <math>V\, </math>,枝集合 <math>E\, </math> から構成されるグラフ <math>G=(V,E)\, </math>, 枝 <math>(i,j) \in E\, </math> 上の距離 <math>d_{ij}\, </math> が与えられたとき,点集合 <math>V\, </math> のすべての点をちょうど1回ずつ経由する巡回路(ハミルトン閉路)で,枝の距離の合計を最小にするものを求める問題を[[巡回セールスマン問題]] (traveling salesman problem) (行商人問題)とよぶ.
 +
 
 +
 特に,距離の対称性(<math>d_{ij}=d_{ji}\, </math>)を満たすものを対称巡回セールスマン問題,三角不等式(<math>d_{ij} \leq d_{ik} + d_{kj}\, </math>)を満たすものを三角不等式を満たす巡回セールスマン問題,点集合が <math>d\, </math> 次元超立方体 <math>[0,1]^d\, </math> 内に分布しており,<math>2\, </math> 点間の距離が点間のユークリッド距離で定義されたものを[[ユークリッド巡回セールスマン問題]] (Euclidean (Euclidian) traveling salesman problem) とよぶ.
 +
 
 +
 巡回セールスマン問題に対する応用は,数百点を扱う基盤配線,運搬経路計画,スケジューリング,数万点を扱う基盤穿孔,X線結晶構造解析 (タンパク質の構造解析),数百万点を扱うVLSI設計など,さまざまである.また,次世代のVLSI設計においては,数千万点の問題を解く必要があると言われている.
 +
 
 +
 巡回セールスマン問題は,[[NP困難]] (NP-hard) であり, 多項式時間の厳密解法が絶望視されているばかりでなく,近似比が 一定値<math>\alpha (<\infty)\, </math> で抑えられる多項式時間の近似解法さえ<math>{\rm P} \neq {\rm NP}\, </math> のもとでは存在しないことが示されている.
 +
 
 +
 三角不等式を満たす対称巡回セールスマン問題に対しては,近似比が <math>3/2\, </math> 以下の保証をもつ多項式時間の近似解法が知られている.また,<math>d\, </math> を定数としたときの <math>d\, </math> 次元ユークリッド巡回セールスマン問題に対しては,固定された <math>\epsilon >0\, </math> を与えたときに,近似比が <math>1+\epsilon\, </math> 以下に抑えられる多項式時間の近似解法(近似スキーム)が存在する.
 +
 
 +
 実用的な近似解法としては,[[最近近傍法]] (nearest neighbor method) や[[セービング法]] (saving method) によって構築された巡回路を[[k-opt法 (巡回セールスマン問題の)|k-opt法]] (<math>k\, </math>-opt)で改善する方法が一般的である.厳密解法としては,巡回セールスマン問題の多面体構造([[TSP多面体]](TSP polytope))を利用した[[分枝カット法]] (branch and cut method) が有効であり,実務的な大規模問題の求解に成功している.
 +
 
 +
 
 +
----
 +
'''参考文献'''
 +
 
 +
[1] 山本芳嗣, 久保幹雄,『巡回セールスマン問題への招待』, 朝倉書店,1997.
 +
 
 +
 
 +
[[Category:グラフ・ネットワーク|じゅんかいせーるすまんもんだい]]

2008年3月13日 (木) 23:07時点における版

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

概要

枝に重みを与えたグラフにおいて, すべての点を丁度1度ずつ訪問して元に戻る巡回路(ハミルトン閉路)のうち, 総重みを最小にするものを求める問題. グラフの枝が有向であるか無向であるかで大別する. 平面上(あるいは空間内)の点と各点の間の距離が与えられたとき, すべての点を訪問する順回路のうち最短のものを求める問題, と定義されることもある. 代表的な組合せ最適化問題の1つ.

詳説

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

 特に,距離の対称性()を満たすものを対称巡回セールスマン問題,三角不等式()を満たすものを三角不等式を満たす巡回セールスマン問題,点集合が 次元超立方体 内に分布しており, 点間の距離が点間のユークリッド距離で定義されたものをユークリッド巡回セールスマン問題 (Euclidean (Euclidian) traveling salesman problem) とよぶ.

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

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

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

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



参考文献

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