問題タブ [eclipse-clp]

eclipseclpを使用してプロローグで CLP を使用して単純なルート プランを作成しようとしており 、clpfd プロローグ ライブラリを使用したいのですが、コンパイラがそれらを認識しません。次のエラーが表示されます。

eclipseCLP のすべてのサード・パーティー・ライブラリーをインストールしましたが、この問題を解決できません。

すべての数字には 9 つの位置があるという観点で数独を解こうとしています。これは私の数独の表現です:

表から、番号5の数独の位置 (Row,Col) は (2,8)、(4,2)、(6,5) であることがわかります。

説明で行に言及する場合、次のような行を意味します。

たとえば、上の行 は行1です。

私がやったことは次のとおりです。

• すべての行について、その行のすべての ROW-Value がalldifferentfromを使用して異なるかどうかを確認しic_globalます。
• 上記と同じことを行いますが、次に COLUMN-Values に対して行います。
• 行ごとに、平方数が異なるかどうかを確認します (毎回行と列の値を使用して計算されます) alldifferent。もう一度使用します。

上記のことは正常に機能し、数独の解決策は得られますが、正しい解決策ではありません。これは、もう 1 つ確認する必要があるためです。すべての位置が異なる必要があります。私のソルバーの現在の状態では、同じ位置に複数の数字がある解を得ることができました。fe: 2と3は両方とも位置(5,7)にある可能性があります。これは、すべての位置が異なるかどうかを確認していないためです。

この問題にどのように対処しますか？タプル形式の 1 つのリスト内のすべての位置を取得してから、すべてのタプルが異なるかどうかを確認しようとしましたが、何時間も苦労しており、本当に必死になっています。ここで解決策を見つけられることを願っています。

編集：コードを追加

次のパズルを考えてみましょう:

セルは、マークされているかマークされていないかのいずれかです。パズルの右側と下側に沿った数字は、特定の行または列の合計を示します。セルは、その行と列の合計に貢献します (マークされている場合): 位置にあるセルは、列の合計と行の合計に(i,j)貢献します。たとえば、上の図の 1 行目では、1 番目、2 番目、5 番目のセルがマークされています。これらは行の合計 (合計 8​​) に寄与し、列の合計にはそれぞれ 1 つずつ寄与します。ij1 + 2 + 5

ECLiPSe CLP でソルバーを作成しました。それは完全に機能しますが、さまざまな値/変数の選択方法で非常に奇妙な動作を示し、その理由がわかりません。(注: パズルの各フィールドはドメイン [0,1] の決定変数で、マークされている場合は 1、マークされていない場合は 0 です。制約は明らかです。)

input_order ( search/6を参照)、first_fail、occurrences、または max_constrained を使用すると、ほとんどメモリを使用せずにパズルがほぼ瞬時に解決されます。最大または最小の anti_first_fail を使用すると、パズルが完了するまでに数分かかり、最大16GB の RAM を消費する可能性があります。なんで？これらのメソッドに対して、ほとんどの制約が非常に長い間アクティブのままなのはなぜですか?

たとえば、smallest と first_fail に違いがあるのはなぜですか? ドメインが 2 つの要素のみで構成され、すべての変数が同じドメインを持つ場合、first_fail、anti_first_fail、largest、smallest、most_constrained は同等であるはずです。ドメイン内の 1 つの値を削除すると、その変数に 1 つの値がアタッチされるため、それ以上の伝播は必要ありません。したがって、この場合の検索では、ドメインがちょうど 2 つの項目で構成される変数が常に処理されます。いいえ？

ECLiPSe CLP 言語のアクティブ制約とパッシブ制約の違いは何ですか? そして、いつ/どのように使用できますか?

より大きな問題のサブセットとして、NxN ボード (N² セルを含む) に対して次の 2 つの制約を記述しようとしています。

• 各行/列には、定義済みのヒントで指定された整数 K が正確に N 回出現します
• 2x2 ブロック (ボード上のどこでも) に整数 K が 1 回以上出現することはありません

ボード上では、いくつかのセルが事前に入力されており、この SO の質問の制約では無視する必要があります。したがって、整数 2 を使用してこれらのセルを表し、未知のセルをモデル化してバイナリ ブール値の有限領域を持たせます。

それぞれコード内の制約:

パズルの単純な実行の場合:

8x8 パズルの場合、最初の解はほぼ瞬時に見つかります。

ただし、20x20 インスタンスの場合、結果が得られずに約 5 分間実行したままにしました。

1 つの制約が他の制約よりも大幅にコストがかかるかどうかを調べるために、両方を別々に実行しました。

block_constraints/2 ではなく、hint_constraints/4 を使用すると、次のようになります。

すべての行/列のオカレンスが満たされていることを確認できます。逆に、block_constraints/2 を使用し、hint_constraints/2 を使用しない場合:

2x2 ブロック制約が正常に保持されていることをもう一度確認できます。残念ながら、両方の制約を一緒に使用すると、プログラムは 5 分以内に終了しないようです。両方の制約が別々に非常に高速に機能するように見えるため、この動作には少し混乱しています。プロセス全体でブロック制約を満たしながら、各行/列の正しいオカレンスが存在することを確認するために、内部で多くのチェックを行う必要があることは理解していますが、5 分以上かかるという事実は、何か他のことが必要であると考えさせました。ブロック制約の記述方法が間違っている可能性があります。

ブロック発生制約の実装を最適化する方法について誰か考えがありますか?

前もって感謝します！

パズルインスタンス

パズル(8, 簡単, [1,2,1,1,1,3,1,2], [2,1,1,1,3,0,3,1], [1-8, 2-1] 、2-4、2-8、5-5、6-1、6-2、6-6、6-8、7-2、7-4、7-7])。

パズル(20,中,[5,2,6,2,7,1,6,3,5,4,5,3,4,2,4,3,5,4,4,5], [5 ,4,3,3,6,3,4,5,2,4,4,4,2,7,1,5,3,6,3,6]、[1-6、1-15、2 -3、2-6、2-8、2-14、2-18、2-19、3-1、3-5、3-11、4-8、4-9、4-11、4-19 、4-20、5-6、5-9、5-15、5-16、5-19、6-1、6-11、6-15、7-1、7-6、7-15、8 -5、8-10、8-15、8-18、9-1、9-10、9-13、9-15、9-17、9-20、10-1、10-7、10-17 , 10-19, 11-5, 11-7, 11-11, 11-13, 11-20, 12-5, 12-18, 13-6, 13-11, 13-18, 14-1, 14 -5、14-6、14-10、15-3、15-12、16-6、16-13、16-17、16-18、16-19、17-2、17-5、17-7 , 17-15, 18-3, 18-9, 18-10, 18-12, 18-18, 19-1, 19-6, 19-20, 20-3, 20-9, 20-11, 20 -12, 20-15, 20-19])。

誰かがチャネリング制約の簡単な例を提供できますか?

チャネリング制約は、制約問題の観点を組み合わせるために使用されます。Handbook of Constraint Programming は、それがどのように機能し、なぜ便利なのかをよく説明しています。

検索変数は、ビューポイントの 1 つ、たとえば X1 の変数にすることができます (これについては後で詳しく説明します)。検索が進むにつれて、制約 C1 を伝搬すると、X1 の変数のドメインから値が削除されます。チャネリング制約により、X2 の変数のドメインから値を削除できます。2 番目のモデル C2 の制約を使用してこれらの値の削除を伝播すると、これらの変数からさらに値が削除される可能性があり、これらの削除はチャネリング制約によって最初の視点に変換されます。最終的な結果として、制約 C1 のみによる場合よりも視点 V1 内でより多くの値が削除され、検索の削減につながる可能性があります。

これがどのように実装されているかわかりません。これらの制約とは正確にはどのようなもので、実際の問題ではどのように見えるのでしょうか? 簡単な例は非常に役に立ちます。