索引はこちら
「シ」で始まる主なワード
シ
巡回セールスマン問題
その他の語句
用語の解説
巡回セールスマン問題とは
（ジュンカイセールスマンモンダイ,traveling salesman problem,）
巡回セールスマン問題とは、組み合わせ最適化問題の一つで、「ある都市を出発したセールスマンの移動距離が最小値を取るように、すべての都市を一度ずつ必ず訪問して出発点に戻るための経路を求める」を求める問題のことである。
旅商人問題とも言う。
もともとは米ランド社が提出した懸賞問題である。
巡回セールスマン問題をコンピュータで特には、任意のnに対して最適解を求める解法のうち、最も短い時間で最適解が得られる解法でも、実行時間が2の二乗に比例する。
それゆえ、現在の主流であるノイマン型デジタル計算機では、最適解を求めることが難しいといわれている。
このため、ニューラルネットワーク、進化論的（遺伝的アルゴリズム）アルゴリズムを利用した方法やアニーリング法といった生物を模倣した新しい計算手法の有効性を示す方法として、巡回セールスマン問題をいかに短時間で解けるかが試金石として利用されている。
なお、今日では運送会社の配送ルートの計画から、VLSIの設計など、その解法は様々な場面で応用されている。
CNET Japan
-
SpaceX上場、終値19%高 マスク氏は史上初「兆万長者」に
イーロン・マスク氏率いる米SpaceXが6月12日（現地時間）、ナスダック市場に上場した。公開価格が1株135ドルに対し、1株150ドルで取引が始まり、初日の終値は161ドル弱。時価総額は2.1兆ドルに達し、世界最大級の上場企業が一夜にして誕生した。筆頭株主であるマスク氏の資産は1兆ドルを突破し、世界初の「トリリオネア」（兆万長者）となった。
