問題タブ [constraint-programming]

超高層ビルとフェンスのパズルを解くための小さなプロローグ アプリケーションに取り組んでいます。

未解決のパズル:

解かれたパズル:

すでに解決済みのパズルをプログラムに渡すと、それを検証するのはほとんど瞬時に行われます。プログラムに非常に小さなパズル (たとえば、2x2、もちろん変更されたルール) を渡すと、解決策を見つけるのも非常に高速です。

問題は、「ネイティブ」サイズの 6x6 のパズルを計算することです。中止する前に、5時間ほど実行したままにしました。時間がかかりすぎます。

最も時間がかかるのは「高層ビル」ではなく「フェンス」であることがわかりました。"skyscrapers" を個別に実行すると、高速なソリューションが得られます。

フェンスのアルゴリズムは次のとおりです。

• 頂点は数字で表され、0 はパスがその特定の頂点を通過しないことを意味し、> 1 はパス内のその頂点の順序を表します。
• 各セルが適切な量の線で囲まれるように制約します。
  • つまり、2 つの頂点が連番を持つ場合、それらが接続されていることを意味します。たとえば、1 -> 2、2 -> 1、1 -> Max、Max-> 1 (Maxは、パス内の最後の頂点の番号です。 を介して計算されますmaximum/2) 。
• ゼロ以外の各頂点に、連番を持つ隣接する頂点が少なくとも 2 つあることを確認します。
• (はエッジに沿った頂点の数で、で計算されます)Maxと等しくなるように制約します。(BoardWidth + 1)^2 - NumberOfZerosBoardWidth+1NumberOfZeroscount/4
• nvalue(Vertices, Max + 1)の個別の値の数VerticesがMax(つまり、パス内の頂点の数) プラス1(ゼロ値)であることを確認するために使用します。
• a を含む最初のセルを見つけて、3効率を高めるためにパスを強制的にそこから開始および終了させます。

効率を上げるにはどうすればよいですか？参照用にコードを以下に示します。

skyscrapersinfences.pro

utils.pro

s1.pro

私は完全なCSPソルバーを探しています。つまり、解決策が存在する場合は常にそれを見つけ、解決策が存在しない場合はそれを通知します。グラフ彩色用に最適化されたソルバーが推奨されますが、必須ではありません。そこには多くの反復アルゴリズム/ソルバーがありますが、作業には完全性（？）が必要です。

ウィークコミットメント検索アルゴリズムを使用して独自のソルバーを実装しましたが、はるかに高速なソルバーを作成し、シミュレーションで使用できる変数の数を増やすことができる多くの最適化とスレッドベースの機能があると確信しています。私はそれが指数関数的に難しい問題であることを理解していますが、少しでも助けになります！

プロローグ制約ソルバーを使用して特定の問題を解決しようとしていますが、スタックしています：D問題要件のより一般的なバージョンは次のようになります。

そして、これは私が使用するクエリ/目標です：

そして、プログラムはXとYの値を計算します（この場合、X = 1、Y = 1が解です）。私が考えているのは、目標/クエリの引数の数が変わる可能性がある場合はどうなるかということです。この場合、私のプロローグプログラムでは、％line1と％line2でコメントされた行の代わりに動的に中断された目標を設定する必要があります。

質問は、どうすればこれらの表現を遅らせることができますか..？問題にこれらをハードコーディングしたくないので、2つの式だけがゴールを通過すると思います。

質問が明確であることを願っています。ありがとう。

私はプロローグに取り組んでいて、このシナリオに直面しました-私のクエリでは、次のようなものを渡します：

さて、私がやりたいのは、プロローグプログラムに不等式をキャプチャさせて、以下のような変数で上記の不等式を持つことができるようにすることです。

変数' Lhs'は2*X + 3*Y 変数' Rhs'になります3*Z 今、私は関係する不等式をどこかに（Opr ??と呼ばれる変数で）割り当てたいので、LhsOprRhsのようなことを言うことはまさに" 2*X + 3*Y >= 3*Z"を言うことを意味します。

これは、私が取り組んでいるシナリオの一般的な形式です。どういうわけか、関係する「不等式」を特定して、後でコードで使用できるようにしたいと思います。

私はICライブラリを使用してEclipse-CLPに取り組んでいます。

これは、プロローグでの私の算術不等式式です。

私はこのような統一用語マニピュレータを使用しました：

そして今、私は今Lhs = 2*X + 3*Y, Rhs as 4*Z and Op as > まですべてがうまくいっています。

私が欲しいのは、この式のためにEclipsePrologのICライブラリを使用して遅延目標を構築することです。たとえば、新しく作成した変数を次のように割り当てます。

さて、必要な不平等（この場合は>）がOpに格納されているので、私は使用していますがEq = (Lhs #Op Rhs)、eclipseはエラーを返しています。

演算子が変数Opから取得される場合、この遅延制約を作成するにはどうすればよいですか？ありがとうございました。

それぞれに幅と高さを定義したいくつかの抽象的な形状があるとしましょう (簡単にするために、それらを長方形にしましょう)。定義された幅と高さの単一のキャンバス (HTML5 キャンバスとは限らない単なる用語) にできるだけ多くのそれらを配置するにはどうすればよいですか?

明らかに、これはある種の制約充足問題ですが、どこから始めればよいかわかりません (ブルート フォースを除く)。グーグルは無関係な結果を表示するだけです（おそらく、何を検索すればよいかわからないためです）。良いアルゴリズムとは何か、またはこれを行うアルゴリズムを作成する良い方法は何か?

フィズがいい例です。図形 (この場合は円) はグループで表示され、互いに重ならず、互いの邪魔にならないようにします。私の使用例は、1 回限りのポジショニング取引です。もう 1 つの例は、特定の境界内にできるだけ効率的に配置するSpriteRightです。

私は表現をしていると思います、

私はそれがに減らされることを期待しています、

誰か提案はありますか？アルゴリズムへのポインタ？

Nota Bene： Karnaugh MapまたはQuine-McCluskeyは、ここではオプションではないと思います。これらのメソッドは灰色のケースを処理しないためです。つまり、表現は、AまたはA'または何もない、または黒または白または色の欠如のようなものである場合にのみ減らすことができます。しかし、皆さんが見ることができるように、ここでは灰色の色合いがあります。

解決策：このためのプログラムをClojureで作成しました。関数を値として含むマップのマップを使用しました。それは非常に便利で、いくつかの組み合わせに対するいくつかのルールがあり、あなたは良いです。有益な回答をありがとうございます。

制約プログラミング言語 ECLiPSe ( http://www.eclipseclp.org/examples/ ) で変数の合計をどのように行うのですか?

私はこの機能を取得しようとしています:

そして、私が得ているエラーは次のとおりです。

制約のある効率的なジョブスケジューリングを開発するには??

スケジューラには、次のメソッドが含まれている必要があります。

すべてのジョブには ID と時間パラメーターがあります。

この問題の可能な解決策は、技術的なバックトラッキングに基づいている可能性があります。ジョブは選択ポイントとして使用され、一時的な瞬間が選択肢として使用されます (最悪の場合、アクティビティの合計期間は作業期間の合計になり、完全に順次実行されます)。

あるいは、データを適切に表現してから、時間軸でスケジューリングを生成し、作業を制約の下に置き、制約が満たされない場合にジョブ (およびそれに依存するすべてのジョブ) を進める必要があります。しかし、Javaでこれを正確に行う方法がわかりません。

言い換えれば、説明されているジョブ管理において、強烈な後戻りアプローチを回避する方法を探しています。