NP完全性は、ほとんどが理論上のものであり、通常の作業環境で遭遇するようなものではないものの1つに似ているように思えます。
ですから、誰かが仕事でNP完全であることが判明し、それに対応するために設計を変更する必要があるという問題に遭遇したことがあるかどうか、私はちょっと興味がありますか？
9 に答える
7
他の人が述べているように、ナップザック (貨物を梱包するため) と巡回セールスマンの問題は、おそらく最も一般的な「現実世界」の NP 完全問題です。
私は職場で、NP が完全か不完全かを証明できない問題に出くわす傾向があります。
于 2009-03-10T01:34:19.710 に答える
1
私は大学1年生のときに友人の父親のためにソフトウェアを書くことに同意しました。リソースをスケジュールするためのものでした。当時は気づいていませんでしたが、NP完全問題であることがわかりました。
ありがたいことに、解決策を見つけるだけでも問題ありませんでした。最適な解決策を見つける必要はありませんでした。プログラムの実行中に問題を解決しようとしているときに変更できるヒューリスティック（実際にはそれらのセット）を作成するのは楽しかったです。
私は夏に解決策を実行しましたが、その後、毎年新しいバージョンに取り組みました。それを売るという私の大きな計画は横ばいでした。私はマーケターよりも優れた開発者でした。
それはとても楽しかったし、開発の実際の世界について多くのことを早い段階で教えてくれました-（エンドユーザー、要件の収集、テストなど-学部生のCSでは得られない多くのこと）
あなたの質問に答えるために-それは特別な指導のために学生をスケジュールしなければならなかった教師のためでした。彼は言語聴覚士および聴覚学者でしたが、同様の分野に適用できました。彼には、回避するための既存の教師、教室、および学生の活動があり、週に特定の回数、学生と会う必要がありました。これは、ナップサック問題または他の同様の/同等のスケジューリング問題の数です。
繰り返しになりますが、解決策を得るだけで問題がないことがわかりました。何も最大化または最小化する必要はありませんでした。すべての学生に対応する必要がありました。
私がシナリオを実行するために使用したテストケースを解決できなかったことを思い出すことができるだけです-私たちが解決した何年にもわたって彼が提供したすべての問題。
私はそれを売り込むことができませんでした-主に私は自分が何をしているのかわからず、自分の市場/購入者に到達する方法がわからなかったためです。
于 2009-08-05T18:24:51.253 に答える
1
シミュレーテッドアニーリングや圧縮アニーリングなど、NP完全問題に対して「十分に良い」答えを取得するためのヒューリスティック近似手法があることは注目に値します。NP完全問題を巡回セールスマン問題に減らすことができる場合は、これらのアプローチを使用できます。（NP完全問題は、他のNP完全問題に還元できますが、実際にそれを行うと、お尻が痛くなることがあります。）
とにかく、そこにはシミュレーテッドアニーリングと圧縮アニーリングの実装があります。その1つがDjinniです。これは、C ++で記述されており、Pythonバインディングを備えています。
于 2009-08-05T18:25:34.653 に答える
1
また、ナップザック問題 (NP 困難) もかなり頻繁に発生します。これは、物事を最適化しようとする誘惑的な罠です。
于 2009-03-10T01:30:00.703 に答える
1
2 つ以上の場所の間の最適な移動ポイントを見つける必要があるあらゆる種類のマッピング ツールは、何も変更しなくてもNP 完全問題になる可能性があります。
于 2009-03-10T00:48:35.593 に答える
1
倉庫からのウェーブ ピッキングを最適化する問題は、巡回セールスマンの問題に相当します。
つまり、N 個の注文がピッキング待ちであり、移動距離とピッカーが訪れたさまざまなピッキング場所を最小限に抑えるために、n 個の最良の注文を見つけたいと考えています。
最近、この問題に遭遇しました。平均的なケースではうまく機能する近似をパントして使用しましたが、最適ではない結果が得られる場合もあります。
于 2009-03-10T00:52:20.250 に答える
0
私は数年前、ネイティブのGoogleマップのようなマッピングプログラムに取り組んでいました。場所の地図に小さなマーカーを配置しましたが、特定の場所に多くのマーカーが密集していました。上司は「マーカーを少しドラッグできるように作成させてください」と言いました（マーカーから実際の場所に線または吹き出しポインターが表示されます）。
ユーザーにこれを行わせるのはばかげていると思いました。特に、ユーザーが5分かけて完璧に仕上げてからズームレベルを変更すると、すべてが間違ってしまうためです。
各ラベルからその場所までの合計画面距離が最小になるようにラベルをレイアウトする方法を見つける関数を書いてみることにしました。当時、これはNP完全であると確信していましたが、少なくとも多くの場合、ポイント数はまだ実行可能であるほど十分に少ない可能性があります。（クラスでNP完全性の証明に多くの時間を費やし、代替ソリューションに十分ではないと思ったことを覚えています。上司が何かをしたいのであれば、「NP困難、やらない」とだけ言うことはできません。まだ何かを考え出す必要があります。）
それからグーグルマップがやって来て、すべてのラベルを重ね合わせただけで、それは完全にひどいです（そして私は毎日それを呪います）、しかし私は他の機能と競争することができないので私はあきらめました。:-(
于 2009-08-05T18:40:56.557 に答える
0
もう 1 つの例は、地域の配送センターを持つ企業、特に顧客に直接配送する企業 (Netflix など) は、施設の場所として知られる NP-Complete の問題のファミリーについて心配する必要があることです。
実際、NP 完全問題が現実の世界に関連しているという考えは、それらの近似アルゴリズムが運用研究の雑誌に頻繁に登場するという事実によって証明されています。
于 2009-08-05T18:26:49.253 に答える
0
巡回セールスマン問題はその好例です。同じ種類の物流上の問題は、航空会社、郵便局、およびあらゆる種類の業界に当てはまります。
于 2009-03-10T00:48:20.510 に答える