6

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

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

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

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

R_CONFLICT={ A: [B,C,D] }
R_DEPENDS ={ X: [ [Y,Z], W, .. } # means: A depends on either Y or Z, and W
R_MIN     ={BAR: n, BAZ: m}
R_MAX     ={BAR: o, BAZ: p}
# now just loop over lists to check them..

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

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

4

1 に答える 1

4

簡単な答え-はい、これは制約プログラミングを使用してチェックできます。実際には、ソルバーに一致するソリューションの可能性のドメインを検索させるのではなく、ソリューションを提供して制約に対してチェックします。特に、これらの種類の条件を非常に簡単にチェックできるPythonを使用している場合は、どのような種類の制約プログラミングがやり過ぎになりますか。

私はこのマシンにPythonを持っていないので、このコードにタイプミス/エラーがあるかもしれませんが、制約プログラミングに関与する必要なしに、あなたが何を求めているかを示しています。

conflict = set([B, C , D])
foos = set([x.foo for x in list])
if A in foos:
    if len(foos & conflict): #Set intersection
         return false

len([x for x in list where x.foo == BAR]) #Gives you number of occurances of BAR

基本的に、制約がはるかに複雑になるか、単にテストするのではなく解決策を見つけたいと思わない限り、制約プログラミングではなくコードに固執します。

于 2010-09-13T14:35:57.867 に答える