免責事項: 以下に説明する方法は普遍的なものではありませんが、多くの場合、問題を解決したり、適切な解決策を見つけるのに役立ちます.
問題内の順列の存在を確認する必要がある場合、または一致する順列の数を見つける必要がある場合、または同様のものを見つける必要がある場合は、動的サブセット プログラミングの使用を検討する必要があります。
メインパラメータはビットマスクで、どの要素がすでに置換に含まれているか、どの要素が含まれていないかを示します。また、どの要素が最後に含まれたかを示す 2 番目のパラメータも必要になることがよくあります。
多くの場合、グラフ内のパスのコンテキストで順列が見られます。したがって、古典的な例であるハミルトン経路問題を考えてみましょう。
ハミルトニアン パスは、グラフの各頂点を 1 回だけ通過する単純なパスです。これは、単純に長さ n の順列として表すことができます (n は頂点の数です)。この順列内の順序は、このパス内の頂点が通過する順序を示します。
グラフ内のハミルトニアン パスの存在を確認するために、ダイナミクス dp[mask][last] を開始しましょう。マスク ビットマスクで 1 でマークされた頂点をバイパスし、最後の頂点に到達する単純なパスはありますか。
初期値は dp[2i][i] = true、残りは false になります。これは、いずれかの頂点から始まる空のパスが常に存在することを意味します。
dp[mask][last] の値を true にすると、「パスを延長する」という意味で、前方に遷移します。つまり、マスク内でゼロのマークが付いている頂点の数 (途中でまだ訪問していません) を探し、同時に最後の頂点からこの頂点までのエッジが存在する頂点の数を探します (パスは既存のエッジによって延長されます)。つまり、 dp[mask | 2k][k] = dp[mask][last] = true かつマスク & の場合は true 2k = 0 (頂点 k はまだ訪問されていません) そして最後にエッジがあります ->き
最終的に、オール 1 ビットマスクおよび任意の最後の頂点のパラメーターの dp に真の値があれば、ハミルトニアン パスが存在します。