「巡回セールスマン問題」の版間の差分
ナビゲーションに移動
検索に移動
| 1行目: | 1行目: | ||
'''【じゅんかいせーるすまんもんだい (traveling salesman problem (TSP))】''' | '''【じゅんかいせーるすまんもんだい (traveling salesman problem (TSP))】''' | ||
| − | 枝に重みを与えたグラフ<math>\,</math>$において, すべての点を丁度1度ずつ訪問して元に戻る巡回路(ハミルトン閉路)のうち, 総重みを最小にするものを求める問題. グラフの枝が有向であるか無向であるかで大別する. 平面上(あるいは空間内)の<math>n\,</math>点と各点の間の距離が与えられたとき, すべての点を訪問する順回路のうち最短のものを求める問題, と定義されることもある. 代表的な組合せ最適化問題の1つ. | + | 枝に重みを与えたグラフ<math>G\,</math>$において, すべての点を丁度1度ずつ訪問して元に戻る巡回路(ハミルトン閉路)のうち, 総重みを最小にするものを求める問題. グラフの枝が有向であるか無向であるかで大別する. 平面上(あるいは空間内)の<math>n\,</math>点と各点の間の距離が与えられたとき, すべての点を訪問する順回路のうち最短のものを求める問題, と定義されることもある. 代表的な組合せ最適化問題の1つ. |
2007年7月13日 (金) 18:21時点における版
【じゅんかいせーるすまんもんだい (traveling salesman problem (TSP))】
枝に重みを与えたグラフ$において, すべての点を丁度1度ずつ訪問して元に戻る巡回路(ハミルトン閉路)のうち, 総重みを最小にするものを求める問題. グラフの枝が有向であるか無向であるかで大別する. 平面上(あるいは空間内)の点と各点の間の距離が与えられたとき, すべての点を訪問する順回路のうち最短のものを求める問題, と定義されることもある. 代表的な組合せ最適化問題の1つ.
