Perlで一連の制約を解決するにはどうすればよいですか？

Question

は、私はPerlで制約（制約のちょうどサンプルセットではなく、私は本当に必要なもの）の次のセットがあります。

$a < $b 
$b > $c 
$a is odd => $a in [10..18] 
$a > 0 
$c < 30 

をそして私は制約を満たすリスト($a, $b, $c)を見つける必要があります。私の素朴な解決策は、

sub check_constraint { 
    my ($a, $b, $c) = @_; 
    if !($a < $b) {return 0;} 
    if !($b > $c) {return 0;} 
    if (($a % 2) && !(10 <= $a && $a <= 18)) {return 0;} 
    if !($a > 0) {return 0;} 
    if !($c < 30) {return 0;} 
    return 1; 
} 

sub gen_abc { 
    my $c = int rand 30; 
    my $b = int rand $c; 
    my $a = int rand $b; 
    return ($a, $b, $c); 
} 

($a, $b, $c) = &gen_abc(); 
while (!&check_constraint($a, $b, $c)) { 
    ($a, $b, $c) = &gen_abc(); 
} 

です。ここでは、この解決策は保証されておらず、一般的にかなり非効率的です。 Perlでこれを行うより良い方法はありますか？

編集：ランダムテストジェネレーターにはこれが必要なので、ソリューションにはrand()などのランダム関数を使用する必要があります。

@solutions = &find_allowed_combinations(); # solutions is an array of array references 
$index = int rand($#solutions); 
($a, $b, $c) = @$solution[$index]; 

編集2：ここ制約がで解決するのは簡単です、そのソリューションは私に可能な組み合わせのリストを与えることができれば、私はランダムにインデックスを選択することができますが、完全に決定論的なソリューションは、十分ではありません強引な。しかし、可能な値の範囲が広い多くの変数がある場合は、ブルートフォースはオプションではありません。

Answer 1

この最適化問題の主な課題は、性質上数学的な問題です。

あなたの目標は、gen_abcメソッドの定義から推測できるように、さまざまな変数（$a、$bなど）の境界間隔を見つけることによって検索スペースを削減することです。）

は

最善の戦略はtrial-）、linear programming技術を使用して境界を（推測しようとする試みは、網羅（または非決定論を進め、下記参照）制約のあなたの完全なセットからできるだけ多くリニア制約を抽出することですプルーニングされた変数空間に対するエラーとエラーのテスト

典型的なlinear programming problemの形式は次のとおりです。

例えば

minimize (maximize) <something> 
subject to <constraints> 

、三つの変数、a、bとc、および以下の線形制約与えられた：

<<linear_constraints>>:: 
    $a < $b 
    $b > $c 
    $a > 0 
    $c < 30 

あなたは、上側見つけることができますし、 $aの下限、$bおよび$cの下限：

lower_bound_$a = minimize $a subject to <<linear_constraints>> 
upper_bound_$a = maximize $a subject to <<linear_constraints>> 
lower_bound_$b = minimize $b subject to <<linear_constraints>> 
upper_bound_$b = maximize $b subject to <<linear_constraints>> 
lower_bound_$c = minimize $c subject to <<linear_constraints>> 
upper_bound_$c = maximize $c subject to <<linear_constraints>> 

この場合、Math::LPを使用することができます。

---

例

線形制約が

• eqopを<の一つ、>、==、>=あるフォーム "C eqop C1×$V1 ± C2×$V2 ± C3×$V3 ..."、である、<=
• $V1 、$V2等は、変数、及び
• C、C1、C2等である...

  $a < $b 
  $b > $c 
  $a > 0 
  $c < 30 
  

  与えられ、例えば、0

におそらく等しい定数、...ているすべての移動不等式の左側の変数（係数を持つ）と不等式の右側の孤立定数：

$a - $b  < 0 
    $b - $c > 0 
$a   > 0 
      $c < 30 

...と（私たちの変数に対する離散すなわち整数値を仮定して）使用されているだけ=、<=と>=等式（中）となるような制約を調整します

• 「... < Cは」」になります。 .. < = C-1'
• '...> C' となる」...> = C + 1'

...つまり、

$a - $b  <= -1 
    $b - $c >= 1 
$a   >= 1 
      $c <= 29 

...そして、このような何か書く：もちろん

use Math::LP qw(:types);    # imports optimization types 
use Math::LP::Constraint qw(:types); # imports constraint types 

my $lp = new Math::LP; 

my $a = new Math::LP::Variable(name => 'a'); 
my $b = new Math::LP::Variable(name => 'b'); 
my $c = new Math::LP::Variable(name => 'c'); 

my $constr1 = new Math::LP::Constraint(
    lhs => make Math::LP::LinearCombination($a, 1, $b, -1), # 1*$a -1*$b 
    rhs => -1, 
    type => $LE, 
); 
$lp->add_constraint($constr1); 
my $constr2 = new Math::LP::Constraint(
    lhs => make Math::LP::LinearCombination($b, 1, $c, -1), # 1*$b -1*$c 
    rhs => 1, 
    type => $GE, 
); 
$lp->add_constraint($constr2); 

... 

my $obj_fn_a = make Math::LP::LinearCombination($a,1); 
my $min_a = $lp->minimize_for($obj_fn_a); 
my $max_a = $lp->maximize_for($obj_fn_a); 

my $obj_fn_b = make Math::LP::LinearCombination($b,1); 
my $min_b = $lp->minimize_for($obj_fn_b); 
my $max_b = $lp->maximize_for($obj_fn_b); 

... 

# do exhaustive search over ranges for $a, $b, $c 

を、上記のいずれかと、変数V1、V2、...（例えば$a、$b、$c、$d、...）の任意の数に一般化することができます制約式を解析して（例えば、-1,1,0,123など）、任意の定数値C（たとえば、-1,130,29など）を指定すると、C1、C2、...対応する行列表現：

V1 V2 V3  C 
[ C11 C12 C13 <=> C1 ] 
[ C21 C22 C23 <=> C2 ] 
[ C31 C32 C33 <=> C3 ] 
... ... ... ... ... ... 

あなたが提供した例に適用

、サイドノートとして

$a $b $c  C 
[ 1 -1 0 <= -1 ] <= plug this into a Constraint + LinearCombination 
[ 0 1 -1 >= 1 ] <= plug this into a Constraint + LinearCombination 
[ 1 0 0 >= 1 ] <= plug this into a Constraint + LinearCombination 
[ 0 0 1 <= 29 ] <= plug this into a Constraint + LinearCombination 

---

NOTE

、非決定論的（randベース）のテストを行うことは、それはまたはであってもなくてもよい場合トラックを維持することをお勧めします（例：それらを再度テストを避けるために($a,$b,$c)タプルはすでに、テストされているのハッシュ）で、と場合にのみ、次の場合にテストされている

• 方法は、ハッシュ・ルックアップよりも高価である（これはそうではありません
• ハッシュは膨大な割合にはなりません（すべての変数は有限の間隔でバインドされていますが、その製品は妥当な数である - つまり、実際のコードでは問題ありません）。どのケースがハッシュサイズをチェックするかは、スペース全体を完全に調査したかどうかを示すことができます。あるいは、ハッシュを定期的にクリアすることができます。
  • 最終的には、上記のことが当てはまる場合は、さまざまな実装オプション（ハッシュの有無にかかわらず）を実行し、実装する価値があるかどうかを確認できます。私はData::Constraintを使用

Answer 2

Simo::Constrainはあなたが関係についての表現や推論を解析する必要になる

Answer 3

「本物」の答えを望むものであるようです。つまり、値を無作為に試行するのではなく、値空間の体系的なトラバースを使用することをお勧めします。例えば、

my $count = 0; 
for (my $c = 0; $c < 30 && $count < $SOMELIMIT; ++$c) { 
    # check all other constraints on only $c here 
    # next if any fail 
    for (my $b = $c + 1; $b < $UPPERLIMIT && $count < $SOMELIMIT; ++$b) { 
     # check all other constraints on only $b and $c here 
     # next if any fail 
     for (my $a = 1; $a < $b && $count < $SOMELIMIT; ++$a) { 
      #check all remaining constraints on $a, $b, and $c here 
      # next if any fail 
      # now use surviving combinations 
      ++$count; 
     } 
    } 
} 

は、私は次の最もなど

少なくとも、このような構造を持つあなたが同じ組み合わせをテストしません、次の制約、最も外側のレベルでは、ほとんどの個々の制約の変数を入れたいです複数回（ランダムバージョンは非常に実行可能性が高いため）、実行しているのを見れば、実行を短くするパターンが出現することがあります。

Answer 4

私はあなたがこれに簡単な答えを見つけるつもりはないと確信しています（私は間違っていると証明したいと思いますが）。

あなたの問題はgenetic algorithmに適しているようです。フィットネスの 関数は書くのが簡単でなければなりません。満足している制約ごとに1点、そうでなければ0点です。 AI::Geneticは、コードを書いたり、書く必要があることを理解するのに役立つモジュールです。

これは、ブルートフォース方式よりも速くなければなりません。

Answer 5

代わりにランダムに生成されたかどうか（些細なことであろう）、有効なリストの束を生成し、ファイルに書き込んだ後、テストプログラムを供給するためにランダムに希望するリストを選んでください。

Answer 6

。個々の制約を実装する小さなサブルーチンを作成し、必要なすべての制約を順番に適用します。 「動的サブルーチン」の章のMastering Perlに少し触れておきます。それをやって

 
use Data::Constraint; 

Data::Constraint->add_constraint(
    'a_less_than_b', 
    run   => sub { $_[1] < $_[2] }, 
    description => "a < b", 
    ); 

Data::Constraint->add_constraint(
    'b_greater_than_c', 
    run   => sub { $_[2] > $_[3] }, 
    description => "b > c", 
    ); 

Data::Constraint->add_constraint(
    'a_greater_than_0', 
    run   => sub { $_[1] > 0 }, 
    description => "a > 0", 
    ); 

Data::Constraint->add_constraint(
    'c_less_than_30', 
    run   => sub { $_[3] < 30 }, 
    description => "c < 30", 
    ); 

Data::Constraint->add_constraint(
    'a_is_odd_between_10_18', 
    run   => sub { 
     return 1 if($_[1] < 10 or $_[1] > 18); 
     return 0 unless $_[1] % 2, 
     }, 
    description => "a is odd between 10 and 18", 
    ); 

for (1 .. 10) 
    { 
    my($a, $b, $c) = gen_abc(); 
    print "a = $a | b = $b | c = $c\n"; 

    foreach my $name (Data::Constraint->get_all_names) 
     { 
     print "\tFailed $name\n" 
      unless Data::Constraint->get_by_name($name)->check($a, $b, $c), 
     } 
    } 

sub gen_abc { 
    my $c = int rand 30; 
    my $b = int rand $c; 
    my $a = int rand $b; 
    return ($a, $b, $c); 
} 

この方法は、それが代わりに全体の障害の失敗したものを見るために、結果を検査するのは簡単です意味：

 
a = 2 | b = 4 | c = 5 
    Failed a_less_than_b 
    Failed b_greater_than_c 
a = 0 | b = 0 | c = 2 
    Failed a_greater_than_0 
    Failed a_less_than_b 
    Failed b_greater_than_c 
a = 0 | b = 0 | c = 2 
    Failed a_greater_than_0 
    Failed a_less_than_b 
    Failed b_greater_than_c 
a = 7 | b = 14 | c = 25 
    Failed a_less_than_b 
    Failed b_greater_than_c 
a = 0 | b = 0 | c = 29 
    Failed a_greater_than_0 
    Failed a_less_than_b 
    Failed b_greater_than_c 
a = 0 | b = 0 | c = 20 
    Failed a_greater_than_0 
    Failed a_less_than_b 
    Failed b_greater_than_c 
a = 0 | b = 4 | c = 22 
    Failed a_greater_than_0 
    Failed a_less_than_b 
    Failed b_greater_than_c 
a = 4 | b = 16 | c = 28 
    Failed a_less_than_b 
    Failed b_greater_than_c 
a = 0 | b = 22 | c = 26 
    Failed a_greater_than_0 
    Failed a_less_than_b 
    Failed b_greater_than_c 
a = 0 | b = 3 | c = 6 
    Failed a_greater_than_0 
    Failed a_less_than_b 
    Failed b_greater_than_c 

あなたはもっと何かハードコアをしたい場合は、私のBrickモジュールは、制約の木を処理し、プルーニングと分岐を含む。これらのことは、大部分のコードが制約オブジェクトを設定しているため、さまざまな状況に対してさまざまな制約を混在させて一致させる、より大きいシステムには意味があります。あなたの状況が1つしかない場合は、おそらく自分が持っているものに固執するだけです。

幸運にも、:)