コードジャムの問題は次のとおりです。
N 個のノードと K 個の「禁止された」エッジを持つ完全な無向グラフが与えられます。N <= 300、K <= 15. K 個の「禁止された」エッジのいずれも使用しない、グラフ内のハミルトニアン サイクルの数を見つけます。
残念ながら、ここのスタックおよび Web 全体での説明は非常に不十分です。特定の 'n' : (n-1) の HamCycles を計算できます! / 2 .
そして、動的計画法で短いセットを実行できます。
しかし、ボローニャのサブセットをすべて取得することはできません。どうすれば O^K にできますか? 私は Python を使用していますが、利用可能な C++ をまだ解読していません。最終的には、時間をかけて C++ を学び、それを解読するつもりです。しかし、それまでの間、ウェブ上のどこかで誰かがこれをよりよく説明できないのはなぜですか? いつも中途半端な説明です。
不足している説明を指摘していただけると助かりますが、とにかく試してみます...
O(2 k ) ベースのソリューションでは、包含と除外の原則が使用されます。k 個の禁止エッジがあるとすると、セット自体と空のセットを含む、これらのエッジの2 k 個のサブセットがあります。たとえば、{A、B、C} の 3 つの禁止エッジがある場合、2 3 =8 個のサブセットがあります: {}、{A}、{B}、{C}、{A,B}、{A ,C}、{B,C}、{A,B,C}。
サブセットごとに、少なくともそのサブセットのすべてのエッジを含むサイクル数を計算します。エッジsを含むサイクルの数がf(s)であり、Sがすべての禁止エッジのセットである場合、包含除外原理により、禁止エッジを含まないサイクルの数は次のようになります。
sum, for each subset s of S: f(s) * (-1)^|s|
どこで | s | sの要素数です。別の言い方をすれば、任意のエッジを含むサイクル数の合計から、少なくとも 1 つの禁止エッジを含むサイクル数と少なくとも 2 つの禁止エッジを含むサイクル数を差し引いた数、...
f(s) の計算は簡単ではありません。少なくとも、簡単な方法は見つかりませんでした。読み進める前に、立ち止まって考えてみてください。
f(s)を計算するには、どのsノードにも関与しないノードの順列の数から始めます。そのようなノードがm個ある場合、 m個あります。ご存知のように順列。順列の数をcと呼びます。
次に、 sのエッジでチェーンを調べます。3 つのエッジに関係するノードやs内のサブサイクルなど、不可能な組み合わせがある場合、f(s)は 0 です。
それ以外の場合は、チェーンごとにmを 1 増やし、 cに2mを掛けます。(既存の順列にはチェーンを配置する場所がmあり、係数 2 は、チェーンが順方向または逆方向になる可能性があるためです。) 最後に、f(s)はc /( 2m ) です。最後の除算は順列をサイクルに変換します。