TSPとは何？わかりやすく解説 Weblio辞書

巡回セールスマン問題

読み方：じゅんかいせーるすまんもんだい
【英】：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/

「OR事典」の他の用語

グラフ･ネットワーク：	完全グラフ局所点連結度局所辺連結度巡回セールスマン問題平面グラフ循環フロー最大フローアルゴリズム
組合せ最適化：	動的計画多面体理論多項式時間アルゴリズム巡回セールスマン問題整数計画施設配置問題最大クリーク問題

トロンボスポンジン

英訳・(英)同義/類義語：thrombospondin, TSP

血小板が分泌するタンパク質で、ヘパリン、フィブリノーゲン、カルシウムイオンと結合して血液凝固に関与するほか、細胞外マトリックス分子とも相互作用する。

「生物学用語辞典」の他の用語

酵素タンパク質モチーフなど：

トロンボキサンA2受容体トロンボキサントロンボキサン合成酵素トロンボスポンジントロンボポエチントロンボモジュリンドメイン構造

TSP

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2024/05/16 00:06 UTC 版)

TSP

巡回セールスマン問題(Traveling Salesman Problem)
東京サウンドプロダクション
株式会社VICTASが使用するブランド名。
東武鉄道で使用されている自動列車停止装置（ATS）の呼称。（別名:東武形ATS）
IIHSが安全な自動車に対して付与する「TOP SAFETY PICK（トップセーフティーピック）」の略称。
タイム・スタンプ・プロトコル（英語版）（Time stamp protocol）
チーム・ソフトウェア・プロセス（英語版）（Team Software Process）
熱帯性痙性対麻痺 (Tropical spastic paraparesis) の略称 ⇒ HTLV-I関連脊髄症
体積の計量単位としての tea spoon の略称。
- カクテルなどで用いられる単位。カクテル#カクテルで用いられる単位を参照。
- 調理で使用される計量スプーンのうち「小さじ(tea spoon)」の英略。「大さじ(table spoon)」は tbsp と略される。
交通信号優先システム（Transit Signal Priority）

TSP（ティーエスピー）

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/06/10 03:06 UTC 版)

「VICTAS」の記事における「TSP（ティーエスピー）」の解説

従来からのブランドで、VICTAS ブランドを立ち上げて以降は一般消費者向けをターゲットにした商品ラインナップとなっていたが2021年3月末を持って生産終了。VICTAS ブランドに統合されたため、人気商品は商品名を変えて VICTAS、VICTAS PLAYから販売されている。

※この「TSP（ティーエスピー）」の解説は、「VICTAS」の解説の一部です。
「TSP（ティーエスピー）」を含む「VICTAS」の記事については、「VICTAS」の概要を参照ください。

ウィキペディア小見出し辞書の「TSP」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。お問い合わせ。


	Copyright (C) 2025 （社）日本オペレーションズ・リサーチ学会 All rights reserved.
	Copyright (C) 2025 NII,NIG,TUS. All Rights Reserved.
	All text is available under the terms of the GNU Free Documentation License. この記事は、ウィキペディアのTSP (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。 Weblio辞書に掲載されているウィキペディアの記事も、全てGNU Free Documentation Licenseの元に提供されております。
	Text is available under GNU Free Documentation License (GFDL). Weblio辞書に掲載されている「ウィキペディア小見出し辞書」の記事は、WikipediaのVICTAS (改訂履歴)、カクテル (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。

TSPとは？わかりやすく解説

巡回セールスマン問題

概要

詳説

トロンボスポンジン

TSP

関連項目

TSP（ティーエスピー）

「TSP」の関連用語

TSPとは？ わかりやすく解説

巡回セールスマン問題

概要

詳説

トロンボスポンジン

TSP

関連項目

TSP（ティーエスピー）

「TSP」の関連用語

TSPとは？わかりやすく解説