TSP

OR事典

巡回セールスマン問題

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

概要

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

詳説

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

　特に，距離の対称性（）を満たすものを対称巡回セールスマン問題，三角不等式（）を満たすものを三角不等式を満たす巡回セールスマン問題，点集合が 次元超立方体 内に分布しており， 点間の距離が点間のユークリッド距離で定義されたものをユークリッド巡回セールスマン問題 (Euclidean (Euclidian) traveling salesman problem) とよぶ．

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

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

　三角不等式を満たす対称巡回セールスマン問題に対しては，近似比が 以下の保証をもつ多項式時間の近似解法が知られている．また， を定数としたときの 次元ユークリッド巡回セールスマン問題に対しては，固定された を与えたときに，近似比が 以下に抑えられる多項式時間の近似解法（近似スキーム）が存在する．

　実用的な近似解法としては，最近近傍法 (nearest neighbor method) やセービング法 (saving method) によって構築された巡回路をk-opt法 (-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）』 (2022/09/12 13:56 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)」の英略。「大さじ(table spoon)」は tbsp と略される。

関連項目

• TSPで始まる記事の一覧

ウィキペディア小見出し辞書

TSP（ティーエスピー）

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

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

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

tsp( Tea-spoon、ティースプーン )

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

「カクテル」の記事における「tsp( Tea-spoon、ティースプーン )」の解説

バー・スプーン1杯分程、約1/9オンス、日本語では「茶匙」とあらわす。