アルゴリズム の 巡回セールスマン問題に関する解説。

株式会社 日立ソリューションズ

HITACHI Inspire the Next

  • ホーム
  • ソリューション・商品
  • 事例紹介
  • セミナー・展示会
  • ビジネスコラム
  • 企業情報
  • お問い合わせ

巡回セールスマン問題

読み方、または別称:じゅんかいせーるすまんもんだい

巡回セールスマン問題(Traveling Salesman Problem、TSP)とは、コンピュータをセールスマンに例えれば、都市の集合と各2都市間の移動命令が与えられた時に、その全ての都市を一度ずつ訪問して出発地に戻る巡回路の総移動コストが最小になる組合せ最適化問題のことである。
問題例の大きさは都市の数で表されるが、この問題はNP困難と呼ばれる問題で、すなわち問題例の大きさに関する多項式時間アルゴリズムが見つからない、計算量的に困難な問題である。
例えば、都市間の移動コストを距離と呼べる部分問題もNP困難である。都市を平面上の点、都市間の距離を平面上のユークリッド距離とする部分問題は最も理解しやすいが、矢張りこれも NP困難である。さらに、都市間の移動コストを 1 または 2 に制限しても、この問題は NP困難である。
ただし、三角不等式が成り立つ TSP には多項式時間近似アルゴリズムが数多く存在する。例えば近似率 2のアルゴリズムや近似度 1.5 のアルゴリズムが知られている。

ページトップへ戻る

話題の用語

ITと社会用語辞典

ワークロード

ワークロードとは、システムのパフォーマンスを適正な状態に保つための指標のこと。

インターネット用語辞典

ライフログ

ライフログとは、人間の活動の記録(行動履歴)をデジタルデータとして記録すること、およびその記録のことである。

ページトップへ戻る

情報漏洩防止ソリューション 「秘文」

ITのお悩みをソリュっと解決! 特命課ソリュートくんがいく!

『オムニチャネル』から商品を探すページです。日立ソリューションズは、コンサルティングからシステム構築、サポートとトータルソリューションをご提供するシステムインテグレーション企業です。

ページトップへ戻る