この質問は実際にその1つを言い換えます。コードジャムの問題は次のとおりです。
N個のノードとK個の「禁止された」エッジを持つ完全な無向グラフが提供されます。N <= 300、K <= 15.K個の「禁止された」エッジを使用しないハミルトン閉路の数をグラフで見つけます。
の単純なDPアプローチは、このようなNO(2^N*N^2)では機能しません。勝者の解決策はであるように見えます。誰かがこの問題を解決する方法を知っていますか？O(2^K)
2269 次
2 に答える
4
禁止されたエッジのサブセットSごとに、Sのすべてのエッジを使用するハミルトン閉路がいくつ存在するかを調べましょう。このサブタスクを解くと、包除原理によって問題が解かれます。
では、サブタスクをどのように解決しますか？Sのすべてのエッジを描画しましょう。2を超える次数の頂点が存在する場合、明らかにサイクルを完了できず、答えは0です。それ以外の場合、グラフは連結成分に分割されます。各コンポーネントは、唯一の頂点、サイクル、または単純なパスです。
サイクルが存在する場合、それはすべての頂点を通過する必要があります。そうでない場合、ハミルトンサイクルを完了することができません。この場合、答えは2です（サイクルは2方向に移動できます）。それ以外の場合、答えは0です。
残りのケースは、c個のパスとk個の唯一の頂点がある場合です。ハミルトン閉路を完了するには、各パスの方向（2 ^ c方向）を選択してから、コンポーネントの順序を選択する必要があります。c + kコンポーネントがあるので、（c + k）で再配置できます！方法。しかし、私たちはサイクルに関心があるので、周期的なシフトによって互いに変わる順序を区別しません。（したがって、（1,2,3）、（2,3,1）、および（3,1,2）は同じです。）これは、答えをシフト数c+kで除算する必要があることを意味します。したがって、（サブタスクに対する）答えは2 ^ c（c + k-1）です！。
このアイデアは、bmerryのソリューション（非常にクリーンなコード、ところで）に実装されています。
于 2011-01-21T15:39:37.040 に答える
1
ハミルトン閉路問題は、巡回セールスマン問題の特殊なケースです（2つの都市間の距離を、隣接している場合は有限定数に設定し、そうでない場合は無限大に設定することで得られます）。
これらはNP完全問題であり、簡単に言えば、それらに対する迅速な解決策が知られていないことを意味します。
ハミルトンパスを見つけるための簡単なヒューリスティックアルゴリズムは、パスabc ...を作成し、それが不可能になるまで拡張することです。zのすべてのネイバーがすでにパスにあるためにパスabc...xyzを拡張できなくなった場合、1ステップ戻り、エッジyzを削除して、yの別のネイバーでパスを拡張します。ハミルトンパスを生成する選択肢がない場合は、さらに一歩後退して、エッジxyを削除し、xの別の隣接パスでパスを拡張します。このアルゴリズムは確かにハミルトンパス（もしあれば）を見つけますが、指数関数的な時間で実行されます。
詳細については、コルメンによる「アルゴス入門」のNP完全問題の章を確認してください。
于 2012-04-01T22:08:59.407 に答える