分割アルゴリズムとファンデルワーデン数

こんにちは、Habr！ グラフォマニアに浸り、先週末のエンターテイメントの結果を共有することにしました（この週末だけがずっと前に過ぎており、記事はエンターテイメントよりもはるかに長く書かれていました。彼らは言うように、時間は楽しい時間です）。



いわゆる分割アルゴリズム（特に、DPLLアルゴリズムについて）、定理とファンデルワーデン数について説明し、記事の最後に独自の分割アルゴリズムを記述し、30分の計算で数w（2; 5 ）は178に等しい（1978年の発見者はこれを行うのに8日以上の計算を要した）。

分割アルゴリズム

これは、次の問題を解決するかなり一般的なアルゴリズムです：有限のセットSがあり、それをいくつかのプロパティを持つ2つのサブセットAとBに分割するか、セットSを必要な方法で分割できないと判断します。



これは次のように行われます：3つの交差しないサブセットA、B、Cが各ステップで開始およびサポートされ、セットSを完全にカバーします。Cは、AとBの間でまだ分配されていない要素のセットです。最初は、C = S、 AとBは空です。 セットCの各反復で、要素aが任意に選択され、セットAまたはセットBのいずれかに配置できます。実際、両方を実行し、両方の可能なオプションを再帰的に処理します。











その結果、分割ツリーが作成されます。そのリーフには、セットSのすべての種類のAとBへの分割があり、セットCは空です。 ここで、すべてのリーフについて関心のあるプロパティのフルフィルメントをチェックする必要があります。



「Let me！」、あなたは言う、「2つのうち明らかな検索よりも優れているもの^{| S |} オプション？」。 そして、すべてがカットオフであり、アルゴリズムの提案されたバックボーンに追加すると非常に便利です！



クリッピングリスト：

1. 部分的に構築されたAとBが適切でない場合-ロールバック
2. 要素をSからAまたはBに移動すると、他の要素がSからAまたはBに移動する場合があります
3. 各ステップでSからaを適切に選択すると、反復ツリーのサイズを大幅に削減できます。

カットオフを使用すると、ツリーのサイズが大幅に減少し、葉の数が著しく減少し、時には0になります（これは、SをAとBに分割できないことを意味します）。 アルゴリズムの複雑さは最悪の場合でも指数関数のままです。



例として従来のDPLLアルゴリズムを使用して、一般的な分割アルゴリズムと提案されているすべてのカットオフを説明すると便利です。

DPLLアルゴリズム

Davis – Putnam – Logemann – Loveland （DPLL）アルゴリズムは、連言標準形式で記述されたブール式の実行可能性を判定するために1962年に開発されました。 SAT問題を解決します。 このアルゴリズムは非常に効果的であることが判明したため、50年以上後、最も効果的なSATソルバーの基礎となりました。



DPLLアルゴリズムの機能を詳しく見てみましょう。 彼はブール式を取り、その一部であるすべての変数を2つのセットAとBに分割しようとします。ここで、Aはtrueのすべての変数のセットで、Bはfalseのすべての変数のセットです。



各ステップで、まだ値が割り当てられていない変数が選択され（そのような変数をfreeと呼びます）、値trueが割り当てられます（この変数はセットAに入力されます）。 その後、得られた単純化された問題は解決されます。 実行可能であれば、元の式は実行可能です。 そうでない場合、選択された変数はfalseに設定され（Bに入力されます）、問題は新しい単純化された式で解決されます。 実行可能であれば、元の式は実行可能です。 そうでなければ-残念ながら、元の式は実行不可能です。



各割り当ての後、次の2つのルールによって数式がさらに簡略化されます。

1. 可変伝播（ユニット伝播）。 句に変数が1つだけ残っている場合、その句に最終的にtrueになるような値を割り当てる必要があります（否定があるかどうかに応じてAまたはBに移動します）。
2. 「純粋な」変数の除外（純粋なリテラル削除）。 いずれかの変数が負の値のみ、または常に負の値なしで式に入力される場合、その変数はpureと呼ばれます。 この変数には、すべてのオカレンスがtrueになるような値を割り当てることができます。これにより、自由変数の数が減ります。

これらの2つのルールは、適用される限り適用する必要があります。通常、最初の割り当ての後、単純化のカスケード全体が続き、自由変数の数が大幅に減少します。



単純化した後に空の句を取得した場合（その単純な接続詞はすべてfalse）-現在の式は実行不可能であり、ロールバックする必要があります。 自由変数が残っていない場合、式は実行可能であり、アルゴリズムを完了することができます。 分離が残っていない場合は、アルゴリズムを終了することもできます。未使用の自由変数を任意に割り当てることができます。



何が起こるかを説明する小さなCのような擬似コード：

bool DPLL( eq F, set A, set B, set C ) { while(1) { //    if (F is empty) { //  ! write A, B, C; return true; } if (F contains an empty clause) return false; //    //  bool flag = false; if (unit_propagation(&F, &A, &B, &C)) flag = true; if (pure_literal_elimination(&F, &A, &B, &C)) flag = true; if (!flag) break; //    } //  x = choose_literal(F, ); if (DPLL(F ∧ (x), A^x, B, C^x)) return true; if (DPLL(F ∧ (¬x), A, B^x, C^x)) return true; return false; }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

＆記号は、unit_propagationおよびpure_literal_elimination関数で、変数F、A、B、およびCが参照渡し、つまり 内部で変更できます。 何かが変更された場合、これらの関数はtrueを返します。 逆に、再帰下降では、オブジェクトのコピーが作成されます。 ^アイコンは、オブジェクトが存在する場合はセットから除外し、存在しない場合は追加します。



次の式を検討して、DPLLアルゴリズムの動作を確認してください。









単純化ルールはこの式には適用されないため、ツリーを分岐する必要があります。 分岐の要素として、x ₁を使用します。最初に、trueに設定します。 次の単純化のチェーンを取得します。









二重矢印は、最初のルールを使用していることを示しています。つまり、孤独な変数を見つけて、希望する値を割り当てています。



残念ながら、このブランチは不可能な式、すなわち このブランチでは、無駄に試みました。 ロールバックして、変数x ₁をfalseに設定しようとします。 これにより、次の一連の簡略化が行われます。









三重矢印は、2番目の単純化ルールを適用していることを示しています。 このブランチでは、成功が待っています。最大2つのソリューションが見つかりました！



トラバーサルツリー全体：









二重矢印と三重矢印で示される変換はツリーの各頂点内で発生するため、ツリー自体は実際には3つの頂点のみで構成されていることがわかります！ ただし、より複雑な例を思いつくことはおそらく可能でした。



たとえば、要素x ₂が分岐用に選択された場合、目的のツリーははるかに小さくなり、答えははるかに早く見つかります（読者は必要な計算を個別に行うように求められます）。 したがって、分岐する要素を選択する戦略は非常に重要です。 たとえば、最大数の句に含まれる分岐用の変数を選択できます。



また、このアルゴリズムを使用すると、すべてのソリューションを見つけることは不可能であることに注意する価値があります。これは、「純粋な」変数を排除するヒューリスティックによって防止されます。 ヒューリスティックに従って、trueに設定された変数の値がfalseであるソリューションが見落とされた可能性があります。 すべてのソリューションを検索するには、アルゴリズムから2番目のルールを除外する必要があります。

ファンデルワーデンの定理と数

ファンデルワーダーの定理は、ラムジーの理論で最も重要な結果の1つです。ラムジーの理論は、多数のランダムな要素で構成されるオブジェクトのパターンの外観を研究する数学の分野です。 すべては次のように始まりました。



前世紀の20年代に、ある数学者は次の問題に直面しました。



すべての自然数のセットを2つの異なる色でペイントします。 数が同じ色で描かれている、任意の長い算術級数があると言えますか？



タスクは非常に単純に思え、肯定的な解決策はほとんど明白に見えます。 しかし、最初はこの声明を証明しようとしても何も起こりませんでした。 数年後、タスクはオランダの若い数学者バーテル・レンデルト・ファン・デル・ワーデンにやっと屈しました。 彼はわずかに異なる定式化で、より一般的なバージョンを証明しました。



任意のrおよびkには、n個の異なる色の自然数S = {1、2、...、n（r; k）}のセットの色付けに対して、このセットSに算術が含まれるような数n（r; k）が存在します同じ色で塗られたk個の数字の連続。



証明は、いわゆる二重帰納法に基づいています。 この証明の簡易版は、たとえばここにあります 。



数値n（r; k）の最小値はw（r; k）で示されます。 番号w（r; k）は、ファンデルワーデン番号と呼ばれます。 ファンデルワーデンの定理の証明は、数値w（r; k）の正確な値ではなく、上限のみを提供します。 そして、私を信じて、この上限は単純に巨大です！ 2色の場合でも、数w（r; k）の推定値は、 アッカーマンの関数として大きくなることが判明しました。 この最高の見積もりは徐々に改善されています。 2001年のTimothy Gowersの最新の結果は次のとおりです。



w（r; k）≤2 ^{2 r 2 2 k + 9} 。



結果はオリジナルよりも少し怖いですが、まだ少し怖いです。 それでも、この境界は、w（r; k）の正確な値とはかけ離れています。



別の研究分野は、異なるrとkの数値w（r; k）の正確な値の決定です。 このタスクは非常にリソースを消費します（これは、ラムジー理論のほとんどのタスクの典型です）。 ウィキペディアによると、現時点では、w（r; k）の正確な値は、rとkの7つのペアについてのみ知られています。

r / k	3	4	5	6
2色	9	35	178	1132
3色	27	293
4色	76

w（2; 3）の答えは簡単に得られます。







w（r、k）の値がわずかに大きい場合、通常、証明は次のように要約されます：数値nの色付きチェーンの長さは固定され、その後、論理式が連言標準形式で構築され、これらのn数値がrおよびkの制限を考慮して色付けできることを検証し、その実現可能性は、SATソルバーを使用してチェックされます。 解が見つかった場合、数値n + 1はw（r; k）の下限であり、それ以外の場合、数値nはw（r; k）の上限と見なされます。



多くのSATソルバーはDPLLアルゴリズムに基づいているため、数値w（r; k）は分割アルゴリズムを使用して検索されます。



色の数r = 2に対して必要なブール式を作成する簡単な方法を示します。 n個の変数x _iを取得します。これは、対応する数字がどの色でペイントされているかを意味します。 値trueは1番目の色を意味し、false-2番目の色を意味します。 算術の進行に両方の色が含まれるように制限を導入する必要があります。 これは非常に簡単に行われます：フォームの分離（x _a 1∨xa 2∨...∨xa _k ）は最初の色の存在を保証し、フォームの分離（¬xa 1∨¬xa 2∨...∨¬xa _k ）-2番目の色。 まあ、実際には、それだけです-各算数の進行に対して、2つの式を作成し、発生したすべてを1つの大きなCNFに接着します。



r = 2、k = 3、n = 9の式の例：



（x 1∨x2∨x3）∧（¬x1∨¬x2∨¬x3）∧（x 2∨x3∨x4）∧（¬x2∨¬x3∨¬x4）∧ （x 3∨x4∨x5）∧（¬x3∨¬x4∨¬x5）∧

（x 4∨x5∨x6）∧（¬x4∨¬x5∨¬x6）∧（x 5∨x6∨x7）∧（¬x5∨¬x6∨¬x7）∧ （x 6∨x7∨x8）∧（¬x6∨¬x7∨¬x8）∧

（x 7∨x8∨x9）∧（¬x7∨¬x8∨¬x9）∧（x 1∨x3∨x5）∧（¬x1∨¬x3∨¬x5）∧ （x 2∨x4∨x6）∧（¬x2∨¬x4∨¬x6）∧

（x 3∨x5∨x7）∧（¬x3∨¬x5∨¬x7）∧（x 4∨x6∨x8）∧（¬x4∨¬x6∨¬x8）∧ （x 5∨x7∨x9）∧（¬x5∨¬x7∨¬x9）∧

（x 1∨x4∨x7）∧（¬x1∨¬x4∨¬x7）∧（x 2∨x5∨x8）∧（¬x2∨¬x5∨¬x8）∧ （x 3∨x6∨x9）∧（¬x3∨¬x6∨¬x9）∧

（x 1∨x5∨x9）∧（¬x1∨¬x5∨¬x9）



以前のスポイラーでは、この式は不可能であることが証明されました。

知識を実践する

次に、数値w（2; k）を見つけるための独自の分割アルゴリズムを作成します。これは、SATソルバーのような見掛け倒しを使用しません。 C ++で記述します（私はMS Visual Studioを使用します）。 アルゴリズムの基礎は次のとおりです。

 #pragma comment(linker,"/STACK:64000000") #include <iostream> #include <bitset> #include <time.h> #include <memory.h> using namespace std; #define N 178 #define K 5 #define BSET bitset< N > bool dfs( BSET & A, BSET & B ) { int i = choice( A, B ); if (i<0) { for (int a=0; a<N; a++) if (A[a]) cout << "A"; else if (B[a]) cout << "B"; else cout << "?"; cout << "\n"; return true; } A[i] = true; if (check(A, B)) { BSET A1 = A, B1 = B; if (reduce( A1, B1 )) if (dfs( A1, B1 )) return true; } A[i] = false; B[i] = true; if (check( A, B )) { BSET A1 = A, B1 = B; if (reduce( A1, B1 )) if (dfs( A1, B1 )) return true; } B[i] = false; return false; } int main() { freopen("input.txt","r",stdin); freopen("output.txt","w",stdout); BSET A, B; if (!dfs( A, B )) cout << "No counterexamples\n"; cout << "n=" << N << " k=" << K << "\n"; cout << "time=" << clock() << "\n"; return 0; }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

実際、dfsプロシージャはアルゴリズムのバックボーンです。 定数NおよびK（それぞれシーケンスの長さおよび算術進行の長さ）は、プリプロセッサによってコードに数値の形式で挿入されます。これは、コンパイラがコードを最適化するのに役立つ場合があります。 セットAおよびB（それぞれ、1番目と2番目の色で色付けされたシーケンス要素）は、長さNのビットマスクで設定されます。次に、提案されたスケルトンで関数をハングアップする必要があります。

1. choice-ツリーを分岐させる要素の選択。
2. check-長さKの等差数列がないことを確認します。
3. reduce-色を一意に決定できる追加要素をペイントします。

選択関数は、最も興味深いものの1つです。

 int cost[N]; int choice( BSET & A, BSET & B ) { memset( cost, 0, sizeof(cost) ); for (int a=0; a<N; a++) for (int d=1; a+d*(K-1)<N; d++) { int cnt1=0, cnt2=0; for (int c=0; c<K; c++) if (A[a+c*d]) cnt1 ++; for (int c=0; c<K; c++) if (B[a+c*d]) cnt2 ++; if (cnt1==0 || cnt2==0) for (int c=0; c<K; c++) if (!A[a+c*d] && !B[a+c*d]) cost[a+c*d] += cnt1+cnt2+1; } int mx = 0; for (int a=0; a<N; a++) mx = max( mx, cost[a] ); if (mx > 0) for (int a=0; a<N; a++) if (cost[a] == mx) return a; return -1; }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

選択に組み込まれた要素を選択するための戦略は次のとおりです。潜在的な単色算術進行の最大数に含まれる要素が選択されます。 しかし、これがすべてではありません。色付きの数字の潜在的な数が進行するほど、推定に対する貢献度が大きくなります。 原則として、分割アルゴリズムでは、すべてを可能な限り不良にし、競合をより高速にする要素を選択する必要があります（チェック関数がfalseを返す場合）。 このような戦略は、多くの場合、不要な分岐を切り捨て、オプションのスペースを削減します。



次に、チェック手順を検討します。

 bool check( BSET & A, BSET & B ) { for (int a=0; a<N; a++) for (int d=1; a+d*(K-1)<N; d++) { bool f1=true, f2=true; for (int c=0; c<K; c++) f1 &= A[a+c*d]; for (int c=0; c<K; c++) f2 &= B[a+c*d]; if (f1 || f2) return false; } return true; }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

この手順は小さく、簡単で、簡単なので、それにこだわるのは意味がありません。



最後に、reduceプロシージャ：

 bool reduce( BSET & A, BSET & B ) { while ( 1 ) { bool flag = false; for (int a=0; a<N; a++) for (int d=1; a+d*(K-1)<N; d++) { int cnt1=0, cnt2=0; for (int c=0; c<K; c++) if (A[a+c*d]) cnt1 ++; for (int c=0; c<K; c++) if (B[a+c*d]) cnt2 ++; if (cnt1+cnt2<K) { if (cnt1 == K-1) for (int c=0; c<K; c++) if (!A[a+c*d]) { B[a+c*d] = true; flag = true; } if (cnt2 == K-1) for (int c=0; c<K; c++) if (!B[a+c*d]) { A[a+c*d] = true; flag = true; } } } if (!flag) break; if (!check( A, B )) return false; } return true; }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

1つを除くすべての要素が同じ色で塗られ、1つが塗られていない進行を単に探しています。 実際、反対の色でペイントします。 フラグ変数は自分で保持します-現在のパスに何かをペイントしました。 そうでない場合は終了し、そうでない場合は矛盾をチェックし、矛盾が存在しない場合は、すべての進行を繰り返します。

結果

コードはCore i5 4Gb RAMラップトップでテストされました。 パラメーター値N = 177 K = 5で2分で、次の例が見つかりました。



BBBABBBBABB?BAAABABBBA?AABAAAABAAAABBBABAAABBBBABBBBABB?BAAABABBBAAAABAAAABAABABBBABAAABA

BBABBBBABBABAAABABBBAAAABAAAABAABABBBABAAABABBABBBBABB?BAAABABBBABAABAAAABAABABBBABAAAB?







AとBは色です。 質問とは、どの色が特定の位置にあるかは重要ではないということです。 つまり、実際には、長さ177の32個もの例が見つかりましたが、長さ5の単色の算術級数はありません。



パラメーターN = 178 K = 5では、コードは20.5分間機能し、目的の算術的進行がないことを示しました。 一般的な場合、 ^2,178のオプションで悪くありません。



このコードは無限に最適化することができます-必要なデータ構造を選択してすばやく選択、確認および削減、分岐する要素を選択するためのより最適な戦略を探す、または少なくとも最初に選択した要素を1色だけでペイントすることができます。 しかし、これはすでにこの記事の範囲外です。



もちろん、このコードはw（2; 3）とw（2; 4）の計算にも使用できます（最初からすべてをテストしました）。



K = 6の場合はどうですか？ さらに最近（2008年）、w（2; 6）= 1132であることが証明され、200コアのクラスターで約250日間の計算が必要でした。 ところで、彼らのアルゴリズムの実装は、1コアで3秒未満でw（2; 5）= 178であることを証明しています。 K = 7の場合、質問は未解決のままです。

読む

1. Lectoriumでの分割 アルゴリズム （ビデオ、講義スライド）
2. グラフ内のすべてのクリックを見つけるためのブロンケルボッシュアルゴリズム （本質的に分割アルゴリズム）
3. ウィキペディアのDPLLアルゴリズム（ rus 、 eng ）
4. ファンデルワーデンの定理と数 （eng）
5. A.やあ、キンチン。 数論の三つの真珠
6. 聖書のコード、ラムジー理論、神の存在
7. ロナルド・L・グラハム、ジョエル・X・スペンサー。 ラムジー理論
8. RSスティーブンス、R。シャンタラム。 コンピューター生成ファンデルワーデンパーティション （英語、pdf）
9. Michal Kouril、ジェロームL.ポール。 ファンデルワーデンナンバーW（2.6）は1132 （英語、pdf）

PS私が深く読んだすべてのリンクではないので、どのリンクをとらないと、実際にはトピックから外れています。