問題タブ [constraint-programming]

これは純粋なプログラミングの質問です。私は単語の配列を持っています。単語の後には、さまざまな長さ (ほとんどゼロ) の休止があります。各単語には確実性スコアもあります。先読みウィンドウから単語の最適なスパンを選択したい。

• 全体的な確実性が低いほど良い (または、確実性の 33 パーセンタイルが低いほど良い)。
• エッジでの一時停止が長ければ長いほど、より良い結果が得られます (厳密な最小値を使用)。
• 最適な長さ (5 秒など) があります。それに近いほど良いです。最小長と最大長には厳しい制限があります。

べね、これは JavaScript で書いているので、サポート ベクター マシンなどを使う余裕はありません。:-) パフォーマンスについては、2 分間の長さ (250 ワード程度) のウィンドウで 1 分ごとに計算されます。

興味のある方への 2 番目の注意事項: これは、自動音声認識によって生成された単語のスパンを選択して、手動で書き起こします (アクティブ ラーニング)。

これにどのようにアプローチしますか？

ドキュメントで矛盾したことを読んでいます。

一方では、この一節は、継続的な計画変数が可能であることを示しているようです。

計画値範囲は、計画変数の可能な計画値のセットです。このセットは、不連続 (たとえば、行 1、2、3、または 4) または連続 (たとえば、0.0 と 1.0 の間の任意の double) にすることができます。

一方、計画変数を定義するときValueRangeProviderは、値セットに使用するフィールドに注釈を指定する必要があります。

Solution 実装には Collection を返すメソッドがあります。そのコレクションからの任意の値は、この計画変数の可能な計画値です。

これらのスニペットはどちらもドキュメントの同じセクションにあります ( http://docs.jboss.org/drools/release/latest/optaplanner-docs/html_single/#d0e2518 )

それで、それはどれですか？計画変数としてフルを使用できますか?それともdouble、その範囲を特定の の値に制限する必要がありますCollectionか?

提供されている実際のアルゴリズムを見ると、実際に連続変数の最適化に適したものは見当たらないので、それが可能かどうかは疑問ですが、それを明確にして明示することをお勧めします。

C++ または C# の optaplanner/drools planner に匹敵する代替手段はありますか? 2007 年の非常に古い C# ポーションしか見つかりませんでした。または、C++/C# で NP 困難な最適化問題をどのように解決しますか?

制約プログラミングで次の制約を記述するにはどうすればよいですか? （できればGurobiまたはCometで）。

S は、サイズ n の整数の配列です。配列を埋めるために使用できる整数のセットは、1 から k の範囲です。使用できる整数ごとに制約ciがあります。ciは、連続する整数iの最小数を示します。

たとえば、c1 = 3、c2 = 2 の場合、1112211112111 は有効なシーケンスではありません。これは、2 つの連続する 2 が必要なためです。一方、1112211122111 は有効なシーケンスです。

次の制約に従って値のマトリックスのような (リストのリスト) を配置する (またはそれが不可能であると判断する) 驚くほど困難な問題に遭遇しました。

最大 n 個の異なる値 (行内での繰り返しなし) を持つランダムに生成された m 行のマトリックスは、次のようにマトリックスを配置します (可能な場合)。

1) 行列は「下三角」でなければなりません。「ギャップ」だけが右上隅にあるように、行は長さの昇順で並べる必要があります。

2) 値が複数の行に表示される場合、同じ列にある必要があります (つまり、行内の値の順序を並べ替えることができます)。

問題/解決策を関数型言語 (Scala など) で表現することが望ましい。

例 1 - 解決策がある

AB
CED
CAB

となる（ひとつの解として）

AB
EDC
ABC

A、B、および C はすべて、それぞれ列 1、2、および 3 に表示されるためです。

例 2 - 解決策がない

ABC
ABD
BCD

制約により、3 番目の行の 3 番目の列に C と D を含める必要があるため、解決策はありませんが、これは不可能です。

2 つの異なるアーク整合性アルゴリズム (AC3 と AC2001) の比較テストを行うために、ランダム CSP のジェネレーターを実装しています。インスタンスは、変数の数、ドメインのサイズ (すべての変数で同じ)、制約の数、および各制約によって拒否される値のペアの数 (すべての制約で同じ) のパラメーターを使用して生成されます。

私の実装では、変数 (名前とドメイン (リスト) の 2 つのフィールドを持つ構造体)、2 つのフィールドを持つ構造体、関連する変数と制約関数) を構築します。各制限に関係する変数をキーとして、値として、その制約によって拒否されたペアのリストを持つハッシュ テーブルを作成します。各制約を使用すると、変数に指定された値が拒否された値のリストに含まれているかどうかがチェックされます。

この実装は「機能」しますが、生成されたインスタンスのほとんどがアーク削減を必要とするため、テスト目的にはほとんど役に立ちません。コードは次のとおりです。

この関数は制限を作成し、拒否された値です

この関数は、拒否された値のハッシュ テーブルを作成します

そして、ソルバーが使用するグローバル パラメータを作成するメイン関数

関数「pertenece」は、要素がリスト にあるかどうかをチェックします。スペイン語の名前でも理解できると思います。そうでない場合は、完全に翻訳できます。

では、私の恐ろしい Lisp コーディング スキルはさておき、生成されたインスタンスの品質を向上させるために修正できるエラーや改善できるエラーはありますか?

clpfd は、SWI Prolog の整数に対する制約プログラミング ライブラリです。セット用の同様のライブラリはありますか? そうでない場合、そのようなライブラリを実装するのに役立つ記事を知っていますか?

それはまったく実行可能ですか？私のグーグルは興味のあるものを何も返さなかったので、私は本当にあらゆる種類の入力を探しています。

編集: 検索時に引用符を使用すると、より良い結果が得られます (doh!)。うーん... とにかくフィードバックをいただけてうれしいです。

編集：これを正確に行うB-Prolog（clpset）に含まれるライブラリがあります。