有名なゲーム Flow の問題を解決する方法を見つけようとしていました。http://moh97.us/flow/
グーグルで調べたところ、これはNP完全な問題であることがわかりました。良い解決策は、ヒューリスティックとカットを利用することです。NP 完全問題を簡単に見つけるにはどうすればよいですか? ブロックすると、明らかな解決策が見えないことがあります。これが NP 完全で発生した場合は、すぐに認識して次の問題に進む方がよいでしょう。
1655 次
2 に答える
1
オブジェクトの爆発がある場合 (たとえば、オブジェクトの数がいくつかのパラメーターに基づいて指数関数的に増加する場合)、これは NP 完全問題であるという方向性を示しているはずです。検査する必要がある場合は、チェックするオブジェクトが多すぎます (組み合わせなど)。通常、これらのオブジェクトは、最初のオブジェクト空間のサブセットまたはサブ空間です。このための直感を構築する必要があります。しかし、いつものように、直感は時々嘘をつきます (私は 2 ～ 3 回、直感によってこのように嘘をつきました)。
次に、ある問題が NP 完全であると思われる場合は、Google で検索して、同じ問題または類似の問題に関する詳細情報を見つけてみてください。
これは少なくとも私がしていることであり、かなり前にかなりの数のアルゴリズムの問題を解決してきました。
これは、NP完全であると確信しているが、たとえば遺伝的アルゴリズムを介して解決できる素晴らしい問題です。
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=973
デューケリングが言ったように、これを行う一般的な方法はありません。
于 2013-11-25T16:41:41.007 に答える
0
これを行う簡単な一般的な方法はありません。基本的には、既知のNP完全問題をこの問題を解決するために削減するか、それらが同等であることを示すことに帰着します。
したがって、よく知られている NP 完全問題についてさらに学び、問題を別の問題の解決に還元し、同等の問題を特定する経験を積んでください。
免責事項: NP 完全問題の特殊なケースには注意する必要があります。問題の一般的なケースを解くには指数時間が必要な場合がありますが、これらの特殊なケースは実際には多項式時間で解ける場合があります。
于 2013-11-25T15:12:59.860 に答える