問題タブ [constraint-satisfaction]

制約充足問題で割り当てられた変数の数を最大化する割り当てを見つけるための既知のアルゴリズム (またはアルゴリズムを見つけるためのリソース) は何ですか (満足のいく割り当てが存在しない場合)?

問題文：

与えられた 4 つの単語を、グリッドの領域ができるだけ小さくなるように、正方形の amxn グリッド内に配置します。

単語は、グリッド内で左から右、上から下に実行する必要があります。文字は重複することがありますが、追加の単語を形成することはできません。すべての単語は、1 つの巨大なチェーンで相互にリンクする必要があります。

「一、二、三、四」という四つの単語で形成できる格子の例。最後のグリッドが最も最適化されていることに注意してください。

私はPythonを学ぼうとしていますが、これは私の歯を切るのに良いアプリケーションだと思いました.

このような問題を解決するためにデータとアルゴリズムを構造化する方法はありますか? 私は率直な答えを探しているわけではありませんが、次のようなヒントがあります。

このライブラリ、このクラス、またはこのデータ構造を使用してください。または、利用可能なスペースを通してこのように繰り返します。

Scheme でバックトラッキング検索を実装しようとしています。これまでのところ、私は次のものを持っています：

私の関数の割り当て完了と選択-u は単体テストに合格します。引数代入は(make-hash)でハッシュテーブルmakeなので問題ないはずです。

私が抱えている問題は、再帰が false 以外の値を返さない場合 (有効な割り当てである必要があります)、ループの最後に false を返すことに関連していると思います。明示的な return ステートメントに相当するスキームはありますか?

Google or-tools Java APIを使用したいのですが、制約を分離できません。私はこのように実装しようとしています: (A==1 OR B==1) AND ((C==1 OR D==1))... どうすればそれを行うことができますか?

もう 1 つの質問は、makeSumLessOrEqual(IntVar[] VARS, int limit) 関数しかないため、どのように makeSumLessOrEqual(IntVar[] VARS, IntVar limit) を実装できるかということです。

ご協力ありがとうございました！

(充足可能な) (線形) 整数充足可能性問題があります。この問題には、とりわけ、ブーリアン値の変数が多数含まれており、それらを x ₁ ...x _nと呼びます。制約の 1 つは、sum(x ₁ ...x _n ) = C です。これらの変数の固定値と、これらの変数の固定値 (すべての可能なソリューションで、これらの変数のどれが特定の値 (0 または 1、これらはブール値であるため) を取るかなど)。

私は実用的な解決策を持っていますが、それはただ遅いです（穏やかに言えば）：

1. _{x 1} == 0という制約を追加します
2. 問題が解決可能かどうかを確認する
3. 手順 1 で追加した制約を削除します。
4. x ₁ == 1という制約を追加します
5. 問題が解決可能かどうかを確認する
6. 手順 4 で追加した制約を削除します
7. 2 と 5 の少なくとも 1 つが成功したことをアサートします。
8. 両方が成功した場合、変数は固定されません。それ以外の場合、変数は、問題がまだ満足できる制約に固定されます。
9. _{x 2} ...x _nに対して 1...8 を繰り返す

これの問題は、遅いことです。特に、問題を O(n) 回、つまり 2*n 回解く必要があります。（ソルバーをウォームスタートするために以前のソリューションを渡していますが、ソルバーを開始するだけでほとんど時間がかかります。）

もっと速い方法はありますか？特に、ソルバーの呼び出し回数を減らす必要があるものは?

_{私が考えていたことは、残念ながらそのままでは機能しません}が、それを ILP 問題に変えて 2 回解決すること_です。同じものを最小化し、どの変数が変化するかをチェックします。残念ながら、これは一般的には機能しません。(カウンター) の例: ブール変数and 、 where . どちらの変数も固定されていなくても、最大化と最小化を行っても同じ結果が得られます。xyx+y=1

このリンクで説明されている方法を使用して、すべてのソリューションを見つける方法を見つけました。

これは正常に動作していますが、遅いです。最初から制約を再計算するため、i_e は以前の計算を利用しません。

さて、この リンクで、MiniSat をライブラリとして使用してすべての解を見つけるより効率的な方法があることを確認しました。しかし、その方法はそこには記載されていません。

すべての SAT ソリューションを効率的に見つけるための適切なドキュメントを教えてください。

ありがとう。

Gecode はSpaces を使用して、進行中の制約充足問題を表します。決定点に到達するたびに、Spaceがコピーされます。

進行中のこれらのスペースの分析を実行したいと考えています。特定のに登録されている変数、制約などのリストを取得する方法はありますSpaceか? API ドキュメントは、そのようなメソッドを提供していないようです。

AC-1、AC-2、および AC-3 アルゴリズムを説明できる人はいますか? それらを理解し、コードで実装する必要があります。でも、まずは本当によく理解したいのですが、難しすぎて私には理解できません。何か助けてください。ところで、私はバックトラックにあまり慣れていません。私はそれについてのビデオを読んだり見たりしようとしましたが、それでも同じです! ありがとう、

私は次のようなセットのペアを持っています

...そして、セットメンバーを次のようにリンクする方法を知るために、既知の適切なデータに基づいてアルゴリズムを自動的にトレーニングしたいと考えています

... どちらかのセットの各要素に対して最大で 1 つの一致があります。セットは同じサイズである必要はなく、オーバーラップについての保証もありません。一致しない場合もあれば、すべて一致する場合もあれば、一致するものと一致しないものが混在する場合もあります。しかし、多くの場合、人間を識別できる一致が期待されており、コンピューターはそれを近似する必要があります。

これまでに試した

H(a, b, w1, w2, w3)ここで、、、およびは手作りで<a1, a2, a3>、、、およびはパラメータ化された重みです。すべてのペアをスコアで並べ替え、どちらのメンバーもスコアの高いペアで表されていないペアを取得します。トレーニング データが期待するように、結果のペアがマッピングされるように、大まかな山登り法を使用して重みをトレーニングします。完全な重み付け構成には、正しいペア スコアと正しくないペア スコアを区別するしきい値があります。このアルゴリズムは、約 800 のトレーニング データを数百または数千回繰り返した後、完璧な構成を定期的に見つけます。A<b1, b2, b3>Bf1(a1, b1) * w1 + f2(a2, b2) * w2 + f3(a3, b3) * w3f1f2f3w1w2w3A × BtS_ab(A, B)合計 2500 ペアの 8 アップルをセットします (図の 3 アッププルの代わりに)。このメソッドがどれだけオーバーフィットしているかを調べるために、まだ検証データセットを提供する必要があります。

問題のセットネスの側面のハードコーディングされた処理には満足していません。ペアをスコアリングするための機械学習手法しか想像できませんが、その後のマッピングは手作りであり、セット マッピング全体を考慮する理想的なソリューションほどスマートではない可能性があります。機械学習の部分はセット全体を考慮していないため、より良い決定を下すために使用できる情報を見逃しているように思えます。

上記の図をリファクタリングして、最初に (n タプルの場合) すべてのペアをスコアリングしA × B、S_ab = < f1(a1, b1), f2(a2, b2), ..., fn(an, bn) >次に各[n, ?, 1]S_ab による一致と不一致でニューラル ネットワーク トレーニングを使用できると思います。これはペアを考慮し、一致/不一致を出力し、セット全体を考慮することは何もしません。

ニューラル ネットワークが可変サイズの入力を処理しないことは理解していますが、上限を選択して、未使用のノードをパディングするための中立的なエンコーディングを見つける||A||ことができるかもしれません。出力は、たとえば、側面と底面に沿っ||B||た要素にインデックスを付ける軸に沿った一致のマトリックスになる可能性があります。しかし、それでもネットは要素の順序に敏感ですよね?AB

そう ...

この方法でセットをセットに確実にマッピングできる機械学習手法はありますか? それは明らかな方法でレコードのリンケージに関連しています。これは、各要素が最大 1 回しか一致しないという制約充足問題です。将来の結果を改善するためのフィードバックとして、人間による結果の修正を組み込むことができれば理想的です。私は機械学習の概念に精通していないので、方法があれば詳しく教えてください。