問題を解決するために巡回セールスマンアルゴリズムを使用しましたか？
https://stackoverflow.com/questions/264050
-
06-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian質問
私は大学でNP完全性の文脈でTSPを勉強しました。実際に実際の問題に当てはまるような状況になったことはありません。少しの研究では、ドリルを移動する最も安価な経路を選択するために使用されていることが示されています。つまり、回路基板に穴を開けています。それは私が見つけることができるほとんどすべてです。
それを使用していますか？ TSAには他にどのような実用的なアプリケーションがありますか？
解決
このスレッドの他のユーザーと同様に、私は大学でNP完全問題の解決策を構築しました（これは友人の副プロジェクトでした）-スケジューリングプログラムです。彼の問題に取り組むことに同意した時点で、NPが何であるかはわかりませんでした。後で、問題を解決するためのかなり良いヒューリスティックを思いついたことに気付きましたが、実際のトリックは、解決策がなく、問題を過度に制約していることをユーザーに伝えるタイミングを知ることでした。
これは、私の理論上のクラスと現実の世界を結びつける素晴らしい方法でした。
再び、ヒューリスティックと「十分に近い」理想的なソリューションを見つけて実装するためのコストのために、最適に近いソリューションが好まれる実際の使用では一般に問題ありません。
他のヒント
「スクイーグル」で長方形の領域をほぼ均一に埋めるプログラムを書くというタスクを一度与えられました。 -自己交差しない曲線。私の最初の試みは、長方形の中にランダムなポイントを生成し、それらのツアーを見つけることでした（必ずしも最短ではありません）。残念ながら、このアプローチはうまく機能しなかったため、私はそれを放棄しました。
最後に問題を解決しました：
私の成功した方法はTSPとは関係ありませんでしたが、好奇心のために要約します：
単一のラインセグメントから開始します。ループ：行が「長すぎる」場合は、2つに分割します。各ポイントをランダムに少し動かしますが、ポイントを互いに反発させます。少ししか進行できなくなったらループを終了します。詳細はありますが、うまくいけばアイデアが得られます。
もちろん、これは角のあるパスを生成します（これは受け入れられます）が、角を滑らかな円弧に変えるのは簡単です。
そして、はい、コードを保持しました。
私は個人的に使用したことはありませんが、回路基板の穴あけ以外の別の用途は、真空を販売するなど、さまざまな場所に行きたい場合です。問題の解決策を使用して、どこでも一度だけ正確に訪問する最も安価な方法を決定できます。
問題がNPハードであるかどうかを知ることは、その問題を解決することを含むソリューションを除外するのに役立ちます。 TSP（またはその他のNPの困難な問題）を目にするたびに、あなたが間違った道を進んでいるという知っている自明でないサイズの問題のitsい頭を隠します。あなたはそれを知っているだけでなく、なぜを知っており、上司/チームメイト/誰にも自信を持って伝えることができます。
http://en.wikipedia.org/wiki/CONCORDE と言われていることは、 ：
コンコルドは問題に適用されました 遺伝子マッピング、[1]タンパク質機能 予測、[2]車両ルーティング、[3] ビットマップ画像の変換 連続線画、[4] 地震に対する船の動きのスケジューリング 調査[5] コンビナトリアルのスケーリング特性 最適化の問題。[6]
はい、ルート計画のためにジオキャッシングアプリケーションで使用します。
現在はポイント間の直線距離を使用していますが、正しく（私がそれに近づいたとき）道路を使用してポイント間の距離を計算する必要があります。
ほとんどの場合、NP-Complete / Hard問題を解決するアルゴリズムを使用したくありません。 「十分に良い」アルゴリズムが必要なだけです。これらは通常、ヒューリスティックに基づいており、合理的な近似値を提供します。
Independent-Set（NP-Complete）のインスタンスである問題が1つありましたが、大部分のケースでかなり良い結果を出し、効率的な実行時間を持つ貪欲なアルゴリズムを見つけました。
ノードのトラバーサル要件が時間や距離などの1次元の労力で表現できる場合、カープールピックアップ、UPSパッケージ配達など、最適化された順序の多くのタイプ。
TSPは、NP完全問題の hello world です。純粋な標準形式では、頻繁に見かけることはありません（このようなデモは含まれていません）、ただし、NP完全問題の膨大なサブセットは、TSPに関連しているか、またはTSPに基づいています：
- 車両ルーティング（サプライトラックルーティングを含む）
- 航空会社/フライトのルーティング
- 列車のルーティング
- スキースローププラウマシンルーティング
これらのそれぞれには、ドメイン固有の余分な制約があり、解決が難しくなっています。 そのため、TSPはNPの完全な問題の優れた紹介であり、その性質を理解するのに役立ちます。
実際の問題は、数学の授業で学習するものとほとんど一致しません。問題は単純化され抽象化されているため、数学を見ることができ、詳細に気を取られることはありません。先ほど述べたように、大規模なTSPの実際の最良の例は、実際には巡回セールスマンが関与するものではありません。それは、これには、アームがツールをさまざまな場所で動かすマシンや、一部の塗装アプリケーション（赤->オレンジ->黄色は赤->黄色->オレンジよりも簡単です）が含まれます。 X線結晶構造にもいくつかのアプリケーションがあります。水晶のサンプルをいくつかの異なる角度に向ける必要があります。
通常、人間は20〜60個のノードを持つマップのほとんどのアルゴリズムよりも同等以上のTSP問題を解決できるため、コンピューターに問題を解決させることはあまり一般的ではありません。コストが十分に高い場合、コンピューターを人間よりも1〜2％改善することは、計算を実行するコストの価値があります。ルートが変更されない場合、最適化に時間を費やすことを正当化できます。これは集積回路設計では一般的です。
航空会社の旅行Webサイトでは、航空会社のリストと各ルートの価格を表示するときに、TSP問題の特殊バージョンを使用します。違いは距離ではなく、コストを最適化することであり、各都市を一度訪れる必要はありません。 LGAからLAXに飛びたいとしましょう。約1/2ダースの直接ルートと、無限の数の他のルートがあります。 LGA-＆gt; ORD-＆gt; LAXまたはLGA-＆gt; DWF-＆gt; LAXを示唆する場合があります。ルートを手動で価格設定できる人間は、旅行サイトで検索された運賃よりも安い運賃を見つけることがあります。通常、人は3つ以上の接続を必要としませんが、特定のフライトの接続数に上限はありません。
Travelling Salesman iPhone Game のルートを解決するために使用しました。興味深いのは、人々は最短ルートを解決するのが得意ですが、最長ルートを解決することはできません。最長ルートと最短ルートの複雑さは同じですが、人々は最短ルートを見つけることができるように訓練されているようです。多くの場合、コンピューターができることよりも速くて優れています。
最初の仕事で在宅介護のスケジューリングアプリケーションを作成しました。
いくつかの非線形時間制約と追加の非線形コスト関数でTSP問題を解決しました。
問題を解決するために非最適ソルバーを使用しました。
Googleマップ（および他のすべてのマップベースのルーティングソフトウェア）は、運転ルートを解決するためにある種の巡回セールスマンを使用しませんか？
私は知る限りTSPを使用していませんが、迷路を横断するために多くの自律ロボットに取り組んできました。それで、迷路解決にTSPを適用できるかどうか疑問に思います。
