問題タブ [constraint-satisfaction]

次の問題がNP完全であるかどうか、または単純なブルートフォースの組み合わせチェックよりも実際に優れた/簡単な解決策があるかどうかを誰かに確認してもらいたいのです。

ソフトウェアにある種のリソース割り当ての問題があります。例を挙げて説明します。

日中は4人で仕事をする必要があるとしましょう。この数と、それが「デイシフト」であるという事実は、私たちのデータベースに記録されています。

ただし、これらのスポットを埋めるのに誰もが必要なわけではありません。法案に合わせるために満たす必要のある要件がいくつかあります。

それらの4つのうち、2つは看護師でなければならず、1つは医師でなければならないとしましょう。

医師の1人も特定のチームの一員として働く必要があります。

したがって、次の一連の情報があります。

デイシフト：4
   1人の医師
   1人の医師、チームAで働く必要がある
   1人の看護師

上記は問題ではありません。問題は、私たちが日勤で働く人々を選び始め、これまでに選んだ人々が実際に基準を満たすことができるかどうかを理解しようとするときに起こります。

たとえば、James、John、Ursula、Maryを選んで仕事をするとします。ここで、JamesとUrsulaは医師、JohnとMaryは看護師です。

UrsulaはチームAでも働いています。

さて、私たちが法案に適合させようとする順序によっては、さまざまな組み合わせを試し始めない限り、適切な人材がいるかどうかを推測してしまう可能性があります。

たとえば、リストを下に移動して最初にUrsulaを選択すると、彼女を「1人の医師」の基準に一致させることができます。次に、ジェームズに行きます。彼はチームAで働いていないため、「1人の医師、チームAで働く必要がある」に関する他の基準を彼で満たすことができないことに気付きました。他の2人は看護師であるため、その基準にも適合しません。

したがって、最初にジェームズをバックトラックして試してみると、彼も最初の基準に適合でき、次にウルスラはそのチームを必要とする基準に適合できます。

したがって、すべてを試すまでさまざまな組み合わせを試す必要があるため、問題が発生します。この場合、動作しているヘッドの総数が合計と同じであっても、まだ満たされていない基準がいくつかあります。必要なヘッドの数、または機能する組み合わせを見つけました。

これが唯一の解決策ですか、誰もがより良い解決策を考えることができますか？

編集：いくつかの説明。

この質問へのコメントは、この少数の人々と一緒に、力ずくで行くべきであると述べています、そして私は同意します、それはおそらく私たちができることであり、ある種の最適化がデータサイズが小さい場合は、データを選択し、初期オーバーヘッドが少ないさまざまなソートアルゴリズムを選択します。

ただし、問題は、これが名簿計画システムの一部であり、「当日シフトにはX人が必要」と「このY人のプールがある」の両方で、かなりの数の人が関与する可能性があることです。それはそれを行うでしょう」、そして大きな「私たちはこれらのY人と何らかの形で一致しなければならないそれらのX人のためのZ基準のこのリストを持っています」の可能性と同様に、そしてあなたは私たちが持っているという事実に追加しますリーダーが名簿を調整するのと同じ計算をリアルタイムで行うのに何日もかかり、その後、迅速な解決策の必要性が出てきました。

基本的に、リーダーには、日中シフト全体でまだ行方不明になっている人の数、さまざまな基準に適合している人の数、実際に何人の人がいるかを示すライブ合計情報が画面に表示されます。私たちが持っているものに加えて、ned。この表示は、リーダーが「ジェームズがウルスラの代わりにデイシフトを取り、ウルスラがナイトシフトを行う場合」で名簿を調整している間、セミライブを更新する必要があります。

しかし、これまでにこれに答えてくれた人々のおかげで、制約充足問題は私たちが進むべき道のように聞こえますが、ここではすべてのリンクとアルゴリズム名を確実に調べます。

これが私がStackOverflowが大好きな理由です:)

Java Constraints Libraryを使用してCSPロジックの問題を解決する必要があります。今のところ、問題のいくつかの制約を表すことができました。それらのほとんどは、「等しい」および「等しくない」バイナリ制約に基づいています。私の疑問は、追加ベースの制約を表現する方法ですか? 例：

• variable1 は DomainA に属します
• variable2 は DomainB に属します
• variable3 は DomainA に属します
• variable4 は DomainB に属します

制約は次のとおりです。

• variable1 と variable2 の合計は、variable3 と variable4 の合計より大きくなります。

観察: これらの変数はお金を表しているため、追加できます。

n個の実数のセットがあります。私はまた、一連の機能を持っています、

これらの各関数は、引数として数値のリストを取ります。私はmの範囲のセットも持っています、

k個の要素のサブセット{r_1、r_2、...、r_k}を繰り返し選択したい

機能がスムーズであることに注意してください。{r_1、r_2、...、r_k}の1つの要素を変更しても、f_i（{r_1、r_2、...、r_k}）はそれほど変更されません。平均と分散は、一般的に使用される2つのf_iです。

これらは私が満たす必要のあるm個の制約です。

さらに、これを実行して、選択したサブセットのセットが、これらのm個の制約を満たすサイズkのすべてのサブセットのセット全体に均一に分散されるようにします。それだけでなく、これを効率的にやりたいと思っています。実行速度は、考えられるすべてのソリューションの空間内のソリューションの密度によって異なります（これが0.0の場合、アルゴリズムは永久に実行できます）。（f_i（任意のi）は一定の時間で計算できると仮定します。）

nは十分に大きいため、問題を総当たり攻撃することはできません。つまり、すべてのk要素のサブセットを反復処理して、m個の制約を満たすサブセットを見つけることはできません。

これを行う方法はありますか？

このようなCSPには、どのような手法が一般的に使用されていますか？誰かが私にこのような問題について話している良い本や記事の方向を示すことができますか（一般的なCSPだけでなく、離散値ではなく連続的な値を含むCSP）？

シミュレーテッドアニーリング（Bean検索を使用）と遺伝的アルゴリズムのパフォーマンスとユースケースの点で、関連する違いは何ですか？

SAは人口サイズが1つしかないGAと考えることができることは知っていますが、2つの主な違いはわかりません。

また、SAがGAを上回ったり、GAがSAを上回ったりする状況を考えています。私が理解するのに役立つ簡単な例を1つだけで十分です。

私はCSPに比較的慣れておらず、変数間に課せられた==、>、<、および！=制約に基づいて、それぞれのドメインからすべての変数の値を見つけようとしています。私はChocoとJacopを見ましたが、これらのタイプの問題を解決することについてこれ以上知ることができませんでした。この例の実装を見つけることができる場所を教えていただけますか？私はPrologを使用してこれを解決しましたが、これを行うためにOOPを使用したいと思います。

ありがとうございました。

変数classes（〜100）、rooms（20）、terms（8）、およびweekdays（5）で構成される古典的なタイムテーブルの問題があります。

問題を単純化するために、以下に制約を減らします。

1日は9時間です。

一部のクラスは学生に必須であり、用語1、3、5、7（および2、4、6、8）の必須クラスは互いに重複してはなりません。

クラスの重みは時間で異なり、2時間のものもあれば、3時間のものもあります。

一部のクラスは特定の部屋で行う必要があります。

同じクラスで同時に2つの講義を行うことはできません。

logilabspython制約モジュールを使用します。また、変数とドメインを適切に選択すると、問題を解決するための時間が短縮されることを認識しています。問題は、これまで制約プログラミングを行ったことがなく、どこから何から始めればよいかを見つけるために問題を構築するのに苦労していることです。例えば：

「同じ部屋に2つのクラスがなく、同じ日にお互いの時間枠が重なることはありません」などの制約を設定できます。または、「同じ日に9時間以上予約できる部屋はない」から始めて、ソリューションドメインを減らして続行します。私は、最初の制約が他の制約よりも解決にはるかに長い時間がかかると見積もっています（試していませんでした）。しかし、それはまた（私が推測する）変数とソリューションドメインの変更またはより小さな問題の再構築を必要とします。私はすでに変数、ドメイン、間隔、実装などで少し迷っています。

簡単に言えば、問題を構築するためのいくつかのポインタ、ソリューションドメイン、変数の賢明な選択などが必要です。

ありがとう

アップデート

logilab-constraintパッケージを使用して、基本的なアプリケーションを作成し、それをgithubにアップロードしました

次の制約処理タスクを解決しました。正しいかどうかご確認いただけますでしょうか。

これが私の解決策であり、どこが間違っているのかを確認してほしい:

MY CONSTRAINTS
カメラのビューが、時間が偶数のときは交互に変更され、時間が 1 のときは囚人だけが移動できるように制約を宣言しました。

みんな、私は何か間違ったことをしていることを知っているので、それを修正するのを手伝ってください。

ご協力いただきありがとうございます。昨日同様の質問を投稿したので、変数と制約の構文を知りたい場合は、次のリンクを参照してください: Variable and Constraint syntax in this post

ご協力いただきありがとうございます

ですから、私の目標は数独パズルを解くメソッドを書くことです。メソッドスタブ「publicint [] []solve（int [] []board）」が与えられました。解決策を見つけるために、アークの一貫性とドメイン分割を使用することになっています。

-私が始めた方法は、ボード上のポイント（キー）とその現在のドメイン（指定されていない限り1..9に初期化）のハッシュマップを作成することでした->HashMap<Point, ArrayList<Integer>> curDomains = new HashMap<Point, ArrayList<Integer>>();これが最適なデータ構造であるかどうかはわかりませんが使用する。

-私の質問は、円弧と拘束をどのように表現するかです。アルゴリズムの擬似コードがありますが、Javaで制約/アークを表現する方法がわかりません。C：満たすべき制約のセット（数独ボード上の有効な配置）と、アークA <X、c>（Xはポイント、cは制約）を表すための最良の方法は何ですか。

有益なコメントをよろしくお願いします。

抽象的な問題の説明:

私の見方では、解析解除とは、AST からトークン ストリームを作成することを意味し、再度解析すると同等の AST が生成されます。

そう parse(unparse(AST)) = ASTです。

これは、同じ AST を生成する有効な解析ツリーを見つけることと同じです。

この言語は、 eBNFバリアントを使用した文脈自由な S 属性文法によって記述されます。

そのため、アンパーサーは、すべての文法制約が保持されるトラバースされたノードを通る有効な「パス」を見つける必要があります。これは基本的に、文法生成規則に対するASTノードの有効な割り当てを見つけることを意味します。これは一般に制約充足問題 (CSP)であり、O(exp(n)) でバックトラックすることにより、解析と同様に解決できます。

幸いなことに、これはGLRを使用して O(n³) で実行できます(または文法をより適切に制限します)。AST構造は文法生成規則構造に非常に近いため、ランタイムが解析よりも悪い実装を見て本当に驚きました。XTextは解析にANTLRを使用し、解析解除にバックトラッキングを使用します。

質問

1. 文脈自由な S 属性文法は、パーサーとアンパーサーが共有する必要があるすべてのものですか、それとも、構文解析手法やパーサーの実装など、さらに制約がありますか?
2. この問題は一般的に O(exp(n)) ではないと感じています - 天才がこれを手伝ってくれるでしょうか?
3. これは基本的に文脈依存の文法ですか？

例1:

したがって、ASTを含む場合

AnyObject -> AnyObject -> Vehicle [name="Car"] ルートがAreaになる可能性があることはわかっています。これを次のように解決できます

したがって、(Highway | Pedestrian) の決定は、サブツリーの決定に依存します。リーフが一見、いくつかのタイプの 1 つであっても、後で有効なパスを形成するために特定のタイプでなければならない場合、問題はさらに悪化します。

例 2:

したがって、型付けされていないオブジェクトを返す S 属性ルールがある場合、いくつかの属性を割り当てるだけです。

したがって、AST に

私はそれを分解することができます

「C」をCに解決できた直後。

AST をトラバースしている間、文法から生成できるすべての制約は、「C」を押すまで、ルール A と X の両方で満たされます。これは、

ツリーの両方のソリューション

は有効であり、それらは同等のセマンティクス (例: シンタックス シュガー) を持っていると見なされます。

さらに詳しい情報：

• XText での解析解除

• 構文解析を解除するための文法の制約については、「シリアライザー: 具体的な構文の検証」を参照してください。

こんにちは私は問題の同じ入力で異なる解決策が必要なので、非決定論的制約充足問題ツールが必要です。誰かがこの特徴を持つツールについて知っていますか？

私は、Gecode（c ++）、Choco（Java）、Curry（Haskell）のような、決定論的な方法で機能すると思うツールしか知りません。