Traveling Salesman Problemとは? わかりやすく解説

Weblio 辞書 > コンピュータ > IT用語辞典 > Traveling Salesman Problemの意味・解説 

巡回セールスマン問題

読み方:ジュンカイセールスマンモンダイ
【英】traveling salesman problem

巡回セールスマン問題とは、組み合わせ最適化問題の一つで、「ある都市を出発したセールスマンの移動距離が最小値を取るように、すべての都市を一度ずつ必ず訪問して出発点に戻るための経路を求める」を求める問題のことである。旅商人問題とも言う。もともとは米ランド社が提出した懸賞問題である。

巡回セールスマン問題をコンピュータで特には、任意のnに対して最適解を求める解法のうち、最も短い時間で最適解が得られる解法でも、実行時間が2の二乗に比例する。それゆえ、現在の主流であるノイマン型デジタル計算機では、最適解を求めることが難しいといわれている。

このため、ニューラルネットワーク、進化論的(遺伝的アルゴリズム)アルゴリズムを利用した方法やアニーリング法といった生物を模倣した新しい計算手法の有効性を示す方法として、巡回セールスマン問題をいかに短時間で解けるかが試金石として利用されている。

なお、今日では運送会社の配送ルートの計画から、VLSIの設計など、その解法は様々な場面で応用されている。

情報処理のほかの用語一覧
アルゴリズム:  選択ソート  シェルソート  識別子  巡回セールスマン問題  昇順  シーケンシャルサーチ  挿入ソート

TSP多面体


巡回セールスマン問題

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

概要

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

詳説

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

 特に,距離の対称性(d_{ij}=d_{ji}\, )を満たすものを対称巡回セールスマン問題,三角不等式(d_{ij} \leq d_{ik} + d_{kj}\, )を満たすものを三角不等式を満たす巡回セールスマン問題,点集合が d\, 次元超立方体 [0,1]^d\, 内に分布しており,2\, 点間の距離が点間のユークリッド距離で定義されたものをユークリッド巡回セールスマン問題 (Euclidean (Euclidian) traveling salesman problem) とよぶ.

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

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

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

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



参考文献

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

[2] D. L. Applegate, R. E. Bixby, V. Chvatal and W. J. Cook, The Traveling Salesman Problem, Princeton, 2006.

[3] アルゴリズムデータベース http://www-or.amp.i.kyoto-u.ac.jp/algo-eng/db/


「traveling salesman problem」の例文・使い方・用例・文例

Weblio日本語例文用例辞書はプログラムで機械的に例文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。


英和和英テキスト翻訳

英語⇒日本語日本語⇒英語

辞書ショートカット

すべての辞書の索引

「Traveling Salesman Problem」の関連用語

Traveling Salesman Problemのお隣キーワード

   

英語⇒日本語
日本語⇒英語
   



Traveling Salesman Problemのページの著作権

   
IT用語辞典バイナリIT用語辞典バイナリ
Copyright © 2005-2026 Weblio 辞書 IT用語辞典バイナリさくいん。 この記事は、IT用語辞典バイナリの【巡回セールスマン問題】の記事を利用しております。
日本オペレーションズ・リサーチ学会日本オペレーションズ・リサーチ学会
Copyright (C) 2026 (社)日本オペレーションズ・リサーチ学会 All rights reserved.
Tanaka Corpusのコンテンツは、特に明示されている場合を除いて、次のライセンスに従います:
 Creative Commons Attribution (CC-BY) 2.0 France.
この対訳データはCreative Commons Attribution 3.0 Unportedでライセンスされています。
浜島書店 Catch a Wave
Copyright © 1995-2026 Hamajima Shoten, Publishers. All rights reserved.
株式会社ベネッセコーポレーション株式会社ベネッセコーポレーション
Copyright © Benesse Holdings, Inc. All rights reserved.
研究社研究社
Copyright (c) 1995-2026 Kenkyusha Co., Ltd. All rights reserved.
日本語WordNet日本語WordNet
日本語ワードネット1.1版 (C) 情報通信研究機構, 2009-2010 License All rights reserved.
WordNet 3.0 Copyright 2006 by Princeton University. All rights reserved. License
日外アソシエーツ株式会社日外アソシエーツ株式会社
Copyright (C) 1994- Nichigai Associates, Inc., All rights reserved.
「斎藤和英大辞典」斎藤秀三郎著、日外アソシエーツ辞書編集部編
EDRDGEDRDG
This page uses the JMdict dictionary files. These files are the property of the Electronic Dictionary Research and Development Group, and are used in conformance with the Group's licence.

©2026 GRAS Group, Inc.RSS