問題タブ [constraint-programming]

私は現在、いくつかのCSP（制約充足）理論に関することを学んでおり、このライブラリを使用してXMLファイルを解析しています。XcodeをIDEとして使用しています。

私のプログラムは正常にコンパイルされますが、ファイルをリンクしようとすると、XMLParser_libxml2.hhファイルで重複シンボルエラーが発生します。私のファイルは次のように分離されています。

上記のXMLParserファイルを含むクラスヘッダーファイルクラスヘッダーファイルを含む
クラス実装ファイルクラスヘッダーファイル
を含むメインファイル

main.oとclassfile.oで重複するシンボルが発生していますが、私が知る限り、その.hhファイルを実際に2回追加しているわけではありません。

完全なエラー：

クラスの実装をメインファイルにコピーし、クラス実装ファイルをコンパイルターゲットから削除すると、エラーが削除されますが、これはまとまりのない混乱であり、すぐにクラスを追加する予定です（それらを別々のファイルに入れてください）。

私が理解したように、これはファイル（XMLParser_libxml2.hh）が1つのファイルにクラスと関数の定義と実装の両方を持っていることが原因です（そして、テンプレートの使用のためにこれが必要だったようですその「ヘッダー」ファイル）。main.cppにすべてのクラスファイルを貼り付ける方法について何かアイデアはありますか？（私は試しましたが#ifdefs、機能しません）。

以下について少し調べてみましたが、うまくいきませんでした。誰かが以前に遭遇した場合に備えて、ここで質問したいと思います。

私は、ボランティアが運営するラジオ局の技術的なニーズを支援しています。出てきた主なものの 1 つは、広告をプログラマティックにスケジュールしたいということです。

広告用のきちんとした複雑なルール エンジンはたくさんありますが、必要なのはかなり単純なものだけです (検討に値する経験も含めて)。

これらのエンティティを処理するために、可能であれば SQL で何かを書きたいと思います。理想的には、誰かが他の広告媒体 (Web など) についてこのようなことを書いていれば、それは本当に役に立ちます。

エンティティ:

• 広告 (カテゴリ、1 日あたりの再生回数、開始日、終了日、または永続的な再生で構成される)
• 広告カテゴリ（レストラン、健康、食料品店など）

問題を単純化しすぎると、これは洗練された SQL ステートメントになります。そこに着く... :)

上記の 2 つのエンティティを使用して、1 日あたりのプレイリストを生成できるようにしたいと考えています。

• 同じカテゴリの 2 つの広告が、互いに x 個の広告の間に再生されることはありません。
• （あるといい）プロモーション性の高い広告をプッシュできます

現時点では、埋める「広告スロット」はありません。「時刻」に関する考慮事項はありません。

私たちはその日の広告をキューに入れ、曲やショーなどの合間にそれらを調べます。1 時間あたりにどれだけ広告を埋めなければならないかなどを把握しています。

考え/アイデア/リンク/例はありますか? 長い道のりを学ぶのではなく、探し続けて、うまくいけば何かに出くわすつもりです.

属性fooを持つ同じクラスのインスタンスを含む多くの可変サイズのリストがあり、すべてのリストに次のようなルールを適用する必要があります。

• 要素foo=Aがある場合、[B、C、D]にfooを持つ要素はありません。
• 要素foo=Xがある場合、[Y、Z]にfooを含む要素が少なくとも1つ存在する必要があります。
• MIN要素とMAX要素の間に存在する可能性がありますfoo=BAR

上記の3つのルールを組み合わせると、私が必要とする同様の制約を表現するのにおそらく十分です。これはソフトウェアパッケージの依存関係チェックのようなものですが、数量があり、バージョンが不足しています:)

ナイーブなアプローチは次のようになります。

これは制約プログラミングの問題ですか？結果を得るために実際に何かを解決する必要はありません。いくつかの制約に対してリストを検証し、それらが満たされているかどうかを確認する必要があります。この問題をどのように分類し、どのように解決しますか？

価値があるので、私はPythonでコーディングしていますが、ジェネリックプログラミングの答えを歓迎します:)制約プログラミングを掘り下げなければならないことが判明した場合は、おそらくpython-constraintを試すことから始めます。

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）？

Constraint プログラミングについて学び始めましたが、Haskell でうまく機能するものだと感じています (Haskell の使用も楽しんでいます)。

Haskell 用の成熟した制約フレームワークはありますか?

PHP用の制約プログラミングライブラリはありますか？このような状況を処理できるもの。

おそらくばかげた質問が1つあります。私は現在、CSPソルバーchocoとjacopをテストしています。アプリのプロファイリング（グラフ彩色、約3000ノード）を実行すると、結果が完全に理解できません。

プロファイラーによって宣言された使用済みヒープスペースは、約1GBのメモリです。作成されたすべてのオブジェクトの合計は100MB未満です。他の900MBのRAMはどこにありますか？

メソッド呼び出し（ソルバーはおそらく大規模なバックトラッキングを使用します）がスタックに配置されていると思うので、ここでは問題はないはずです。Xmx paramを使用して最大メモリを減らすと、アプリは例外で失敗します。

スレッド「メイン」の例外java.lang.OutOfMemoryError：GCオーバーヘッド制限を超えました

したがって、残りは未使用の未収集メモリではないようです（この場合、GCがメモリの割り当てを解除するため（失敗しないため））。

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

私はこのツールに代わるコードとオープン ソースによる SMT Z3 の使用法 (DbC など) の実用的な例に興味を持ち、探しています。実際、同様の Z3 形式解法ツールに興味がありますが、

• オープンソースでなければならない
• 低レベル (API) と高レベル (テキスト スクリプト) の両方の対話を提供する
• SMT-LIBをサポート
• Java、Python、Ruby、Vala 、およびHaskell以外の言語のツール/書き込み/言語に適している (使用可能)
• 契約による設計（DbC）、静的型検証など、それに基づく安定した（実際に使用できる）ツールがあります。

SMT-LIB ホームページ (詳細については bit.ly バンドルを参照) によると、2010 SMT ソルバーのリストは次のとおりです。 UCLID、veriT、Yices、Z3."

それらのいずれかを実際に使用することについてフィードバックをお寄せください (コード例が最適です)。

最後に、それとGHCの可能性との比較に関する情報は役に立ちますが、実装例(言語の「機能」ではない)がある場合に限ります。

Z3 に関する詳しい情報はこちらhttp://bit.ly/bundles/ewiger/1

私は、ドライバーと乗客のリストとその場所を受け取り、次の制約に従って、ドライバーに割り当てられた乗客の数を最大化するドライバーへの乗客の割り当てのリストを返す関数を作成しています。

1. 乗客は1台の車にのみ乗ることができます

2. 各車両に割り当てられた乗客の数は、車両内の指定された座席数を超えることはできません

3. すべての乗客を乗せる各ドライバーの移動距離は、任意の定数を超えることはできません

私が抱えている問題は、最初の制約を追加することです。私はhttp://uswaretech.com/blog/2009/03/constraint-programming-in-python/のチュートリアルに従っており、彼らが魔方陣の問題を解決する方法と同様のスタイルを使用しました: 乗客の割り当てはタプル (ドライバー、パッセンジャー) として格納され、これらのタプルはリストに格納されます。ドライバーと乗客の実際の詳細は、ID、緯度と経度、および各ドライバーの車の座席数を含むクラスに保存されます。ファイルからテストデータを抽出して、問題を構築するために使用したコードは次のとおりです。

これをインタラクティブに実行したところ、制約を追加する前に getSolutions() を実行できることがわかりましたが、全体を実行すると次のエラーが発生します。

getSolutions() メソッドの実行中に、最初のタプルの最大値が 1 であっても (2,0) を検索しようとするようです (データ セットには 2 つのドライバーしかありません)。ExactSumConstraint ではなく MaxSumConstraint を使用していることを除けば、エラーが発生するほどコードがどのように異なるのかわかりません。

私は人工知能のいくつかのトピックを説明するコースを書いています。現在、「制約処理」の部分に取り組んでいます。制約処理を説明するために、簡単な例を含めたいと思います。この例には、次の品質が必要です。

• 例にそれほど多くの変数とオプションを含めることができないように、ORツリーを描画したい
• ノードの一貫性、バックトラッキング、バックジャンプ、バックマーキング、弱い緩和、アークの一貫性を示しています。（例は、これらの方法が理にかなっており、制約処理に何らかの価値を追加することを示しているはずです）。
• 理解しやすく、表現しやすい。（2ページの長さの制約の配列ではありません）。

私はしばらくの間Webを閲覧してきましたが、今ではすべての例がこれらの品質を満たしていません。（私はまた、既存の問題を単純化しようとしました）。

これらの方法/技術を説明するための典型的な例はありますか？2つの異なる例を挙げて、これら2つの例にテクニックを分散させることも問題にはなりません。