10

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: ここでの制約は、力ずくで簡単に解決できます。ただし、可能な値の範囲が広い変数が多数ある場合、ブルート フォースは選択肢になりません。

4

6 に答える 6

15

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

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

最良の戦略は、制約の完全なセットから可能な限り多くの線形制約を抽出し、(線形計画法の手法を使用して、以下を参照してください) 境界の推測を試みてから、完全な (または非決定論的な) 試行錯誤テストを実行することです。刈り込まれた変数空間。

典型的な線形計画問題は次の形式です。

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

たとえば、3 つの変数 、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>>

Perlでは、この目的のためにMath::LPを使用できます。

例

線形制約の形式は " C eqop C1×$V1 ± C2×$V2 ± C3×$V3 ..." です。

  • eqop<、、、、>のいずれか==です>=。<=
  • $V1など$V2は変数であり、
  • C、などは定数でC1、C20 に等しい可能性があります。

たとえば、与えられた...

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

...すべての変数 (およびその係数) を不等式の左側に移動し、唯一の定数を不等式の右側に移動します。

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

=...そして、 、<=および>=(in)equals のみが使用されるように制約を調整します(変数に離散値、つまり整数値を想定):

  • 「... < 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...) と任意の係数C1, C2, ... (例: -1, 1, 0, 123 など) に一般化できます。 ) および任意の定数値C(例: -1、1、30、29 など) は、制約式を次のような対応する行列表現に解析できる場合に提供されます。

   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

ノート

補足として、非決定論的 ( に基づく) テストを実行する場合、再テストを回避するために、どのタプルが既にテストされているrandかを (たとえばハッシュで) 追跡することは良い考えかもしれませんし、そうでないかもしれません。そして次の場合のみ:($a,$b,$c)

  • テストされているメソッドは、ハッシュ ルックアップよりもコストがかかります (これは、上記で提供したサンプル コードには当てはまりませんが、実際のコードでは問題になる場合とそうでない場合があります)
  • ハッシュは膨大な割合に成長しません (すべての変数が有限の間隔で束縛され、その積が妥当な数になります。この場合、ハッシュ サイズをチェックすると、スペース全体を完全に探索したかどうかを示すことができます)、またはクリアすることができます。ハッシュは定期的に行われるため、少なくとも一度に 1 つの時間間隔で衝突検出が行われます。)
    • 最終的に、上記が当てはまると思われる場合は、さまざまな実装オプション (ハッシュの有無にかかわらず) の時間を計り、実装する価値があるかどうかを確認できます。
于 2009-02-22T23:48:21.433 に答える
3

私はData::Constraintを使用します。個々の制約を実装する小さなサブルーチンを作成し、必要なすべての制約を順次適用します。これについては、「動的サブルーチン」の章のMastering Perlで少し説明しています。

#!perl
use v5.20;

use Data::Constraint 1.121;
use experimental qw(signatures);

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

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

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

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

Data::Constraint->add_constraint(
    'a_is_odd_between_10_18',
    run         => sub ( $c, $t ) {
        return 0 if( $t->[0] < 10 or $t->[0] > 18 );
        return 0 unless $t->[0] % 2;
        return 1;
        },
    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 30;
    my $a = int rand 30;
    return ($a, $b, $c);
    }

このようにすると、全体的な失敗ではなく、何が失敗したかを確認するために結果を簡単に調べることができます。

= 25 | b = 11 | c = 23
    失敗しました a_is_odd_between_10_18
    失敗しました a_less_than_b
    失敗した b_greater_than_c
= 17 | b = 0 | c = 9
    失敗しました a_less_than_b
    失敗した b_greater_than_c
= 1 | b = 5 | c = 29
    失敗しました a_is_odd_between_10_18
    失敗した b_greater_than_c
= 26 | b = 21 | c = 16
    失敗しました a_is_odd_between_10_18
    失敗しました a_less_than_b
= 24 | b = 20 | c = 19
    失敗しました a_is_odd_between_10_18
    失敗しました a_less_than_b
= 27 | b = 20 | c = 12
    失敗しました a_is_odd_between_10_18
    失敗しました a_less_than_b
= 18 | b = 25 | c = 13
    失敗しました a_is_odd_between_10_18
= 26 | b = 10 | c = 11
    失敗しました a_is_odd_between_10_18
    失敗しました a_less_than_b
    失敗した b_greater_than_c
= 14 | b = 27 | c = 0
    失敗しました a_is_odd_between_10_18
a = 6 | b = 28 | c = 20
    失敗しました a_is_odd_between_10_18

もっとハードコアなものが必要な場合は、私のBrickモジュールが、剪定や分岐などの制約のツリーを処理します。ほとんどのコードが制約オブジェクトを設定しているため、これらのことは、さまざまな状況でさまざまな制約を組み合わせて一致させる大規模なシステムでは理にかなっています。状況が 1 つしかない場合は、現在の状況に固執したいと思うでしょう。

幸運を、 ：）

于 2009-02-23T18:16:07.977 に答える
2

これに対する簡単な答えが見つかるかどうかはわかりません (ただし、間違っていることを証明したいと思います!)。

あなたの問題は遺伝的アルゴリズムに適しているようです。フィットネス関数は簡単に記述できるはずです。満たされた制約ごとにスコア 1 を付け、それ以外の場合は 0 を付けるだけです。 AI::Geneticは、コードを記述し、何を記述する必要があるかを理解するのに役立つモジュールのようです。

これは、力ずくの方法よりも高速である必要があります。

于 2009-02-22T20:08:30.073 に答える
1

「本当の」答えには、式の解析と関係についての推論が必要です。それを除けば、ランダムに値を試すのではなく、値空間の体系的な走査を使用することをお勧めします。例えば、

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;
        }
    }
}

最も個別の制約を持つ変数を最も外側のレベルに配置し、次に最も制約のある変数を次に配置します。

少なくともこの構造では、同じ組み合わせを複数回テストすることはありません (ランダム バージョンでは可能性が非常に高いため)。また、実行を監視すると、実行を短くするパターンが出現することがわかる場合があります。

于 2009-02-22T19:58:32.670 に答える
0

Simo::Constrainが必要なようです

于 2009-02-22T19:48:43.537 に答える
0

代わりに、ランダムに生成されたかどうかにかかわらず（自明なはずです）、有効なリストの束を生成するアルゴリズムを作成し、それらをファイルに書き込み、そのファイルを使用してテストプログラムにフィードします。欲求。

于 2009-02-22T20:31:48.237 に答える