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