問題タブ [constraint-programming]

Mac OS X 10.7 で Objective C アプリケーションを作成していますが、算術制約の問題を解決する必要があります。たとえば、長方形の 2 つの方程式があり、a と b は辺の長さです。

私はこの問題を制約充足問題と特定しました。ユーザーは a と A を指定し、ソルバーに b と P を計算させる必要があります。http://mitpress.mit.edu/sicp/full-text/book/book-ZH-でこれの実装を見つけました。 22.html#%_idx_3516ですが、Objective C から LISP プログラムを呼び出すクリーンな方法があるかどうかはわかりません。Objective C インターフェイスをソルバーに提供できるものを探しているか、LISP をコンパイルできるものを探しています。 Objective C ライブラリにプログラムします。それ以外の場合は、最小限のオープン ソースの制約ソルバーが私のニーズに合っています。

Eclipse 制約プログラミング フレームワークの search/6 関数に関するこのドキュメントを理解するのに苦労しています。

選択パラメーターが基本的に値の順序に影響することを理解しています。

選択方法が変数の順序を選択しているようにも見えますが、そのすべてのオプションを完全には理解していません。

他のパラメータについてはよくわからないので、誰かが言葉で説明できるかどうか疑問に思っていました. 私は制約論理プログラミングの理論をかなりよく理解しているので、それらの概念を自由に参照してください。私はそのドキュメントの CS 専門用語の多くを理解していません (アリティなど)。

ありがとうございました

SMT-Solver は、制約の解決に使用できます。私たちが知っているように、CSP ソルバーは長年にわたって制約解決にも使用されてきました。では、CSP ソルバーに対する SMT ソルバーの利点は何でしょうか?

Microsoft Solver Foundation で、値が決定値に依存するパラメーターを追加できるかどうかを知りたいです。

つまり、TSP モデルに何かが必要ですが、あるポイントから別のポイントへのトラフィックも考慮に入れる必要があります。注意: トラフィックは、セールスマンがそのルートを移動する時間によって異なります。

モデルは次のとおりです。

都市間のすべての可能な組み合わせのマトリックスがあります。

Decision 変数はOrder、セールスマンのルートです。0 は最初、1 秒、...

値からルートが実行される時間を計算するプロパティtimeToTravelにバインドされたプロパティがあり、Orderその時間の交通量を含む移動時間を返します。

Solve関数が呼び出されると、パラメーター値が一度読み取られてキャッシュされるように思えますが、正しいですか? はいの場合、この問題を解決するための推奨事項はありますか?

もともと私は MSF フォーラムでこの質問をしましたが、スタック オーバーフローでもっと注目されるだろうと思っていました。また、MSF 以外のさまざまなソルバーにもオープンですが、.NET 環境にとどまりたいと思っています。

選択した制約ソルバーを使用してゼブラパズルを解く演習を行い、Prologclpfdライブラリを使用して試しました。

Prologでこの問題を解決する他の慣用的な方法があることを私は知っていますが、この質問は特にclpfdパッケージに関するものです！

だから私が解決しようとしているパズルの特定のバリエーション（それらがたくさんあるとすると）はこれです：

5軒の家があります

1. イギリス人は赤い家に住んでいます
2. スウェーデン人は犬を飼っています
3. デンマーク人はお茶を飲むのが好きです
4. 緑の家は白い家に残されています
5. 温室の所有者はコーヒーを飲みます
6. ポールモールを吸う人は鳥を飼っています
7. 真ん中の家でミルクを飲む
8. 黄色い家の所有者はダンヒルを吸う
9. ノルウェー人は最初の家に住んでいます
10. マールボロ喫煙者は猫の飼い主の隣に住んでいます
11. 馬の飼い主はダンヒルを吸う人の隣に住んでいます
12. ウィンフィールド喫煙者はビールを飲むのが好きです
13. ノルウェー人は青い家の隣に住んでいます
14. ドイツ人はロスマンを吸う
15. マールボロ喫煙者には、水を飲む隣人がいます

私は次のアプローチでそれを解決しようとしました：

家が持つことができる各属性は、「英国」、「犬」、「緑」などの変数としてモデル化されます。属性は、それらが発生する家に応じて、たとえば変数の場合、1〜5の値を取ることができます。 「犬」は値3を取り、犬は3番目の家に住んでいます。

このアプローチにより、次のような隣接制約のモデル化が容易になります。

しかし、どういうわけか、clpfd（IMO）問題が正しくモデル化されていても、パッケージは解決策を生成しません（Choco制約ソルバーでまったく同じモデルを使用し、結果は正しいものでした）。

完全なコードは次のとおりです。

内の概念を誤解しましたかclpfd、それともここで明らかな何かを単に見逃していますか？それが役立つ場合は、ここでChocoとScalaを使用して実装された同じアプローチを見つけることができます。

編集：ソルバーが問題を解決できないと私が信じる理由は、変数の明確な値が出てこないためですが、「魚1..3 \/5」などの範囲のみが出てくるからです。

問題文

N 人の面接を希望する雇用主が 1 人いるため、N 人の面接枠を作成します。すべての人は、それらのスロットの空き時間スケジュールを持っています。可能であれば N 人を N スロットにスケジュールするアルゴリズムを与え、それが不可能な場合はフラグ / エラー / などを返します。可能な限り最速の実行時の複雑さは?

これまでの私のアプローチ

ナイーブ: N あります! N 人をスケジュールする方法。それらすべてを調べて、順列ごとに実行可能かどうかを確認します。の上！ ）

バックトラッキング:

1. 1 人しか参加できない面接の時間枠を探します。その人をスケジュールし、候補者のリストから削除し、スロットを削除します。
2. 1 つのスロットにのみ入ることができる候補者を探します。その人をスケジュールし、候補者のリストから削除し、スロットを削除します。
3. そのような組み合わせがなくなるまで、1と2を繰り返します。
4. 人を選び、利用可能なスロットの 1 つにランダムにスケジュールします。この操作を覚えておいてください。
5. スケジュールが決まるまで、または解決できない競合が発生するまで、1、2、3 を繰り返します。スケジュールがある場合は、それを返します。解決できない競合がある場合は、バックトラックします。

これは O( n! ) の最悪のケースだと思います - これ以上良くはありません。

DP ソリューションもあるかもしれませんが、まだ見ていません。

他の考え

問題は NxN マトリックスで表すことができます。行は「スロット」、列は「人」、値は空きの「1」とビジーの「0」です。次に、この行列内で行と列が入れ替わった恒等行列を探します。ステップ 1 と 2 は、「1」が 1 つしかない行または列を探しています。(行列の階数が = N の場合、I は解があることを意味します。しかし、その逆は成立しません) 別の見方として、行列を重み付けされていない有向グラフ エッジ行列として扱うこともできます。次に、ノードはそれぞれ 1 つの候補と 1 つのスロットを表します。次に、グラフ内のすべてのノードが 1 つの出力エッジと 1 つの入力エッジを持つようにエッジのセットを探します。または、ノードが 2 つある場合は、2 部グラフになります。

マトリックスの例:

私は機能を持っています

クエリを実行すると

X の値を取得できますが、そうすると

次のようなクエリごとにエラーが発生します

未処理の例外: 不明なメッセージ: type_error(nf(_G353**1,_G351),1,数値式,_G353**1)

私は他の演算子を試してみましたが、それらはすべて機能します。** は特別だと思いますが、正確にはどのように処理すればよいのでしょうか?

次の不等式システムは、整数上のx1とx2について解かれます。

x1 + x2 = l

x1> = y1

x2> = y2

x1 <= z1

x2 <= z2

l-z1 <= x2

l-z2 <= x1

l、y1、y2、z1、z2は任意ですが、固定されており、>=0です。

値の例を使用

l = 8

y1 = 1

y2 = 2

z1 = z2 = 6

システムを解いて、次の方程式を取得します。

2 <= x1 <= 6

x2 = 8-x1

WolframAlphaに整数で解決するように指示すると、可能なすべての値のみが出力されます。

私の質問は、任意のl、y1、y2、z1、z2のx1とx2の方程式/範囲をプログラムで導出できるかどうかです。この問題は制約プログラミングに関連しており、この問題に関する古い論文を見つけました。Harveyetal。による「Projectionを使用した制約解決のコンパイル」です。

このアプローチは、最新の制約解決ライブラリで使用されていますか？

私がこれを尋ねる理由は、上記のようなシステムを異なるパラメータで数千回解決する必要があり、システム全体を何度も読み取り/最適化/解決する場合、これには長い時間がかかるためです。したがって、パラメータ化されたシステムを一度コンパイルしてから、コンパイルされたバージョンを使用することができれば、大幅な速度の向上が期待できます。

Javaで以下の問題をプログラミングする際に問題があります。これは制約充足の問題です:

次のような制約がある場合:

1. x1 + x2 > x3
2. x2 - x4 = 2
3. x1 + x4 < x5

x1～のそれぞれがx5ドメイン内にある{0,1,2}

{(0,0,0), (0,0,1), (0,1,0),(0,1,1),(1,0,0), ......}タプルのセットが次のようになるように、さまざまな組み合わせをプログラムするにはどうすればよいですか。

これはインスタントの制約1であり、次のようなタプルのドメインがあります{(0,0,0), (0,0,1), (0,1,0),(0,1,1),(1,0,0),(0,1,2),(2,0,1) ......}

どの言語でも返信が必要ですが、できれば Java でお願いします。

すべてのソリューションを見つけて (gecode を使用)、統計を出力したい minizinc モデルがあります。これは簡単です。

しかし、このモデルは何千もの解を生成し、解ごとに区切り記号が出力されます。

これらの区切り記号を削除し、統計のみを出力する必要があります。方法はありますか？

==アップデート==

Gecodeソースを変更することでこれを解決できました

外したところ

もっと良い解決策があるかもしれませんが、これは私にとってはうまくいきました。