コトバンクはYahoo!辞書と技術提携しています。

巡回セールスマン問題 ジュンカイセールスマンモンダイ

1件 の用語解説(巡回セールスマン問題の意味・用語解説を検索)

デジタル大辞泉の解説

じゅんかいセールスマン‐もんだい〔ジユンクワイ‐〕【巡回セールスマン問題】

あるセールスマンが複数の都市を一度ずつ訪れるとき、どのような順番で巡回すれば総移動時間(移動距離または交通費)を最小にできるかを問う問題。グラフ理論の有名な問題の一つであり、都市(ノード)の数が大きくなると計算量が爆発的に増えることが知られている。同種の問題は、荷物の配送や集積回路の配線などに応用される。

出典|小学館 この辞書の凡例を見る
監修:松村明
編集委員:池上秋彦、金田弘、杉崎一雄、鈴木丹士郎、中嶋尚、林巨樹、飛田良文
編集協力:曽根脩
(C)Shogakukan Inc.
それぞれの用語は執筆時点での最新のもので、常に最新の内容であることを保証するものではありません。

世界大百科事典内の巡回セールスマン問題の言及

【ニューラルコンピューティング】より

…各極小値に対応するネットワークの状態を想起パターンと考えれば,自己想起型連想記憶のモデルとなる。さらにホップフィールドらは,このモデルを計算論的にNP-困難な巡回セールスマン問題に適用し,組合せ最適化問題のヒューリスティック解法として有効性を示唆した。組合せ最適化問題においては,図2の点A,Bのような局所最適解への収束を避けてCのような大局最適解もしくはそのよい近似解を得ることが求められる。…

【アルゴリズム】より

…なお〈データ数が小さいときやすでにほとんど小さい順になっている場合は直接挿入法が速く,そうでなければ併合法の方が速い〉とか〈平均計算量はクイック法,最大計算量はヒープ法の方が小さい〉ということがあるので,方法の選択には注意が要る。 都市の間の交通網と都市間の移動経費がわかっているとき,〈すべての都市を巡回する経費最小の経路を求めよ〉という〈巡回セールスマン問題〉はひじょうにむずかしく,都市数nがふえると〈計算時間の爆発〉が起こり,現実的な時間内には最適解を求められないことがある。そこで最適解を求める代わりに,それに近い〈近似解〉を求める〈近似解法〉が研究され,数万を超える都市についてよい解が得られたとの報告がある。…

※「巡回セールスマン問題」について言及している用語解説の一部を掲載しています。

出典|株式会社日立ソリューションズ・クリエイト
All Rights Reserved. Copyright (C) 2015, Hitachi Solutions Create,Ltd. 収録データは1998年10月に編集製作されたものです。それぞれの用語は執筆時点での最新のもので、常に最新の内容であることを保証するものではありません。また、本文中の図・表・イラストはご提供しておりません。

巡回セールスマン問題の関連キーワードセールスマンの死ルート・セールスクリスマスセールセールスセールスマンホールセールバンキングセールスウーマンダイレクトセールス販売日報セールスマン管理

今日のキーワード

トランスアジア航空

台湾・台北市に本拠を置く航空会社。中国語名は復興航空。1951年、台湾初の民間航空会社として設立。83年に台湾の国産実業グループに経営移管され、組織改編を実施した。92年に国際チャーター便の運航を始め...

続きを読む

コトバンク for iPhone

巡回セールスマン問題の関連情報