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>

例如，给定三个变量 、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,C2等是常数，可能等于 0。

例如，给定...

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

...将所有变量（及其系数）移到不等式的左侧，将单独的常数移到不等式的右侧：

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

...并调整约束，以便只使用=,<=和>=(in) 等式（假设我们的变量是离散的，即整数值）：

  • '... < 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)

  • 正在测试的方法比哈希查找更昂贵（您上面提供的示例代码不是这种情况，但您的真实代码可能有问题，也可能没有问题）
  • 散列不会增长到很大的比例（所有变量都受有限区间的约束，其乘积是一个合理的数字 - 在这种情况下，检查散列大小可以表明您是否已经完全探索了整个空间 - 或者您可以清除定期散列，因此一次至少有一个时间间隔，您确实有一些碰撞检测。）
    • 最终，如果您认为上述内容适用于您，您可以对各种实施选项（有和没有散列）计时，看看是否值得实施。
于 2009-02-22T23:48:21.433 回答
3

我使用Data::Constraint。您编写实现各个约束的小子程序，然后依次应用您想要的所有约束。我在“Dynamic Subroutines”一章的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
a = 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
一个 = 6 | b = 28 | c = 20
    失败 a_is_odd_between_10_18

如果你想要更硬核的东西，我的Brick模块可以处理约束树，包括修剪和分支。这些事情对于更大的系统是有意义的，因为大多数代码都在设置约束对象，因此您将针对不同情况混合和匹配各种约束。如果你只有一种情况，你可能只想坚持你所拥有的。

祝你好运， ：）

于 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 回答