私は大学で NP 完全性の文脈で TSP を学びました。実際の問題に適用される状況は実際にはありませんでした。少しの調査によると、ドリルを移動するための最も安価な経路、つまり回路基板に穴をあける方法を選択するために使用されていることが示されています。それは私が見つけることができたほとんどすべてです。
使っていますか？TSA には他にどのような実用的なアプリケーションがありますか?
8581 次
14 に答える
8
私はかつて、長方形の領域を「波線」（自己交差しない曲線）でかなり均一に塗りつぶすプログラムを作成するタスクを与えられました。私の最初の試みは、長方形内にランダムなポイントを生成し、それらのツアーを見つけようとすることでした（必ずしも絶対的に最短である必要はありません）。残念ながら、このアプローチはうまく機能しなかったため、私はそれを放棄しました。
私は最終的に問題を解決しました：
私の成功した方法はTSPとは関係ありませんでしたが、好奇心旺盛な人のために要約します。
単一の線分から始めます。ここでループします。行が「長すぎる」場合は、2つに分割します。各ポイントを少しランダムに移動しますが、ポイントが互いに反発するようにします。進捗がほとんどない場合は、ループを終了します。詳細はありますが、うまくいけばあなたはアイデアを得ることができます。
もちろん、これにより角度のあるパスが生成されますが（許容範囲内）、コーナーを滑らかな円弧に変えるのは簡単です。
そして、はい、私はコードを保持しました。
于 2008-11-05T02:41:03.267 に答える
7
問題がいつ NP 困難であるかを知ることは、その問題を解決することを含むソリューションを除外するのに役立ちます。TSP (またはその他の NP 困難な問題) が、自明ではないサイズの問題に頭を悩ませているのを見るたびに、間違った道を進んでいることがわかります。あなたはそれを知っているだけでなく、その理由を知っており、上司/チームメイト/誰にでも自信を持って伝えることができます.
そうは言っても、 http: //en.wikipedia.org/wiki/CONCORDEは次のことを明らかにしています。
Concorde は、遺伝子マッピング、[1] タンパク質機能の予測、[2] 車両の経路指定、[3] ビットマップ画像から連続した線画への変換、[4] 地震調査のための船の移動のスケジューリング、[5] などの問題に適用されています。組み合わせ最適化問題のスケーリング特性の研究[6]。
于 2008-11-05T01:23:17.247 に答える
7
はい、ルート計画のためのジオキャッシング アプリケーションで使用しています。
現在、ポイント間の直線距離を使用していますが、道路を使用してポイント間の距離を計算する必要があります。
于 2008-11-05T02:10:56.073 に答える
6
個人的には使ったことはありませんが、回路基板の穴あけ以外の用途としては、たとえば掃除機を売りに行くなど、さまざまな場所に行きたい場合があります。問題の解決策を使用して、すべての場所を 1 回だけ訪れる最も安価な方法を決定できます。
于 2008-11-05T01:01:15.480 に答える
5
ほとんどの場合、NP-Complete/Hard 問題を解決するアルゴリズムを使用したくありません。「十分な」アルゴリズムが必要なだけです。これらは通常、ヒューリスティックに基づいており、合理的な近似値を提供します。
Independent-Set (NP-Complete) のインスタンスである 1 つの問題がありましたが、大部分のケースでかなり良い結果を出し、効率的なランタイムを持つ貪欲なアルゴリズムを見つけました。
于 2008-11-06T00:27:12.507 に答える
4
TSPは、NP完全問題のHelloWorldです。純粋な標準形では、実際にはあまり見られませんが（このようなデモは含まれていません）、NP完全問題の巨大なサブセットが関連しているか、TSPに基づいています。
- 車両ルーティング（供給トラックルーティングを含む）
- 航空会社/フライトルーティング
- 列車のルーティング
- スキースローププラウマシンルーティング
これらのそれぞれには、追加のドメイン固有の制約があり、解決が困難になります。したがって、TSPは、NP完全問題の性質を理解するための優れた入門書です。
于 2012-05-02T10:03:04.160 に答える
3
カープールの集荷、UPSの荷物の配達など、多くの種類の最適化された注文。ノードのトラバーサル要件を時間や距離などの1つの次元で表すことができます。
于 2008-11-05T02:21:22.573 に答える
3
実生活での問題は、数学の授業で学ぶものと一致するものはほとんどありません。問題は単純化および抽象化されているため、数学を確認でき、詳細に気を取られることはありません。あなたが言ったように、大規模なTSPの最良の実例は、実際には巡回セールスマンを必要としません。それは、シーケンスに依存するセットアップ時間で実行するジョブを持つスケジューリングマシンを含みます。これには、腕がさまざまな場所でツールを動かすマシンや、一部のペイントアプリケーション（赤->オレンジ->黄色は赤->黄色->オレンジよりも簡単です）が含まれます。X線結晶学には、結晶のサンプルをいくつかの異なる角度に向ける必要があるアプリケーションもあります。
于 2008-11-06T01:01:30.487 に答える
3
このスレッドの他の人たちと同様に、私は大学で NP 完全問題の解決策を作成しました (これは友人のサイド プロジェクトでした) - スケジューリング プログラムです。私が彼の問題に取り組むことに同意したとき、私は NP 完全が何であるかを知りませんでした。後で、問題を解決するためのかなり優れたヒューリスティックを思いついたことに気づきましたが、もちろん、本当の秘訣は、ユーザーに解決策がなく、問題を過度に制限していることをいつ伝えるかを知ることでした。
私の最終的な理論クラスと現実の世界を結びつける素晴らしい方法でした.
繰り返しになりますが、理想的なソリューションを見つけて実装するコストのために、ほぼ最適なソリューションが好まれる現実の用途では、ヒューリスティックと「十分に近い」は一般的に問題ありません。
于 2008-11-06T02:06:35.693 に答える
2
この会社は、改善された TSP アルゴリズムに基づいていました。
彼らは、ケーブルテレビの設置業者や修理工をニューヨーク市周辺に派遣し、さまざまな問題を抱えています。
于 2009-04-16T16:38:53.767 に答える
2
通常、人間は 20 ～ 60 個のノードを持つマップのほとんどのアルゴリズムと同等またはそれ以上に TSP 問題を解決できるため、コンピュータに問題を解決させることはあまり一般的ではありません。コストが十分に高い場合、コンピュータが人間よりも 1 ～ 2% 向上することは、計算を実行するコストに見合う価値があります。ルートが変更されない場合は、最適化に時間を費やすことを正当化できます。これは、集積回路設計では一般的です。
航空会社の旅行サイトでは、航空会社のリストと各ルートの価格を表示する際に、TSP 問題の特殊なバージョンを使用しています。違いは、距離ではなく、コストを最適化することです。もちろん、各都市を 1 回訪れる必要はありません。LGA から LAX に飛行機で行きたいとします。約 1/2 ダースの直行ルートがあり、その他のルートは無数にあります。LGA->ORD->LAX または LGA->DWF->LAX を示唆している可能性があります。ルートを手動で価格設定できる人間は、旅行サイトで検索されたものよりも安い運賃を見つけることがあります。通常、人々は 2 つ以上の接続を必要としませんが、特定のフライトの接続数に上限はありません。
Traveling Salesman iPhone Gameのルートを解決するために使用しました。興味深いことに、人々は最短ルートを解くのは得意ですが、最長ルートを解くのは得意ではありません。最長ルートと最短ルートの複雑さは同じですが、人々は最短ルートを見つけられるように訓練されているようで、多くの場合、コンピュータよりも速く、より正確に見つけることができます。
于 2009-08-05T21:00:36.960 に答える
1
私の最初の仕事では、在宅ケア スケジューリング アプリケーションを構築しました。
いくつかの非線形時間制約と追加の非線形コスト関数を使用して TSP 問題を解決しました。
問題を解決するために非最適ソルバーを使用しました。
于 2010-08-16T09:04:18.027 に答える
0
グーグルマップ（そして他のすべてのマップベースのルーティングソフトウェア）は、運転ルートを解決するためにある種の巡回セールスマンを使用していませんか？
于 2008-11-05T02:51:40.813 に答える
0
私が知る限り、TSP を使用したことはありませんが、迷路を横断する多数の自律型ロボットに取り組んできました。では、TSP を迷路の解法に応用できないかと考えています。
于 2008-11-06T00:07:55.790 に答える