問題タブ [symmetry]

Google or-tools のサンプルの 1 つは、n-queens 問題のソルバーです。 下部には、対称性を破る制約を制約ソルバーに追加することで実装を改善できることが示されています。

インターネットを見回すと、対称性が n-queens 問題の制約を破っていることがわかりましたが、それらを制約に変換して、それらを実装する Python コードにする方法を一生理解できません。

編集：これは悪い質問でした。更新しましょう...

私は何を試しましたか？

上記の最初のリンクからのセットアップは次のとおりです。

単純な制約をうまく実装できることはわかっています。ソリューションの最初の行の最初の列に常にクイーンがあることを確認したい場合は、次のように実装できます。

変数は最初の列のqueens[0]クイーンの位置を表し、この制約は、最初の列の最初の行にクイーンがある場合にのみ満たされます。もちろん、これは私がやりたいことではありませんが、ソリューションにコーナーセルが含まれていない可能性があるためです。

n-queens 問題の対称性の破れの制約を以下に示します。それらは、2 番目の段落のリンクから直接取得されます。

これらの制約がどのように機能するかを理解しています。この関数を n-queens ボードの各セルに適用して、状態を同等の状態に変換できるという考え方です。これらの状態の 1 つが、その状態の正規表現になります。これは、重複した評価を排除することによって、将来の処理を削減する方法として使用されます。

事後的にこれを実装するだけなら、上記で説明したことを正確に実行し、考えられる対称性を破る関数をそれぞれ使用して状態を変換し、ある種の状態ハッシュ (たとえば、各列で選択された行の文字列) を計算します。提案されたソリューションごとに最も低いものを選択します。以前に見たものについては、将来の処理をスキップします。

私の問題は、これらの変換を google or-tools 制約プログラミング ソルバーの制約に変換する方法がわからないことです。

d1(r[i] = j) => r[j] = i主対角線についての最も単純な反射を見てみましょう。私が知っているのは、変換をすべてのセルに適用し、現在の状態と比較して、セルが拡張されないようにする必要があるということです。ここで変換のためにどのような式が機能するかを理解するのにPythonについて十分に理解していません。また、この特定のソルバーの現在の状態と変換を比較する制約を作成する方法がわかりません。

i,j,k4 つの整数変数との対称性を見つけたいですl。対称性は次のとおりです。

1. 4 つの数字はすべて等しい: XXXX、
2. 3 つの数値が等しい: XXXY、XXYX、XYXX、YXXX
3. 等しい数の 2 つのペア: XXYY、XYXY、XYYX、...
4. 1 組の等しい数と 2 つの異なる数: XXYZ、XYZZ、XYZX、...
5. すべての数値が異なります。

すべての変数は、特定の非連続範囲内で実行されます。ネストされた if else ステートメントを使用します。最初の if は、すべての変数の不等式をチェックします。そうでない場合は、ケース 1 があります。次の if は、等しいペアがあるかどうかを確認します。そうでない場合は、ケース 5 です。次の if は、3 つの等しい数をチェックします。true の場合、ケース 2 になります。それ以外の場合、最後の if は 2 つの等しい数のペアをチェックします。true の場合はケース 3、それ以外の場合はケース 4。

これを行うより良い方法はありますか？このテストを何百万回も実行する必要があるため、パフォーマンスが向上するという意味で優れているという意味です。

f(a,b,c,d)次の順列対称性を持つスカラー関数があります

f(a,b,c,d) = f(c,d,a,b) = -f(b,a,d,c) = -f(d,c,b,a)

私はそれを使用して、4D 配列を完全に設定しています。以下のコード (python/NumPy を使用) は機能します。

しかし明らかに、対称性を利用して、このコード セクションの実行時間を短縮したいと考えています。私はもう試した：

これにより、実行時間が半分に短縮されます。しかし、私が試した最後の対称性のために：

これはうまくいきますが、2 倍のスピードアップは得られません。正しい理由で正しいとは思いませんが、理由がわかりません。

ここで、この特定の順列対称性をよりうまく活用するにはどうすればよいでしょうか?

目標:

• 対称および非対称のドット パターンのイメージを作成します。
• 上下鏡面対称（左右鏡）の左右対称画像
• 対称画像から作成された非対称画像 (左右をシャッフル)

たくさん作りたいのですが、骨組みが思いつかなくて困っています。現在、MATLAB または Python を使用して画像を生成しようとしていますが、代替ソリューションを歓迎します。