perl - 如何解决 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 等)来修剪搜索空间

最好的策略是从全套约束中提取尽可能多的线性约束，尝试推断边界(使用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>>

在 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

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

• '...
• '... > 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) 可能是也可能不是一个好主意。元组已经被测试过，以避免再次测试它们，当且仅当:

• 正在测试的方法比哈希查找更昂贵(这不是您上面提供的示例代码的情况，但可能是也可能不是您的真实代码的问题)
• 散列不会增长到巨大的比例(要么所有变量都受到有限间隔的约束，其乘积是一个合理的数字 - 在这种情况下检查散列大小可以表明你是否已经完全探索了整个空间 - 或您可以定期清除散列，因此至少一次可以在一个时间间隔内进行一些冲突检测。)
  • 最终，如果您认为上述内容适用于您，您可以对各种实现选项(带或不带哈希)进行计时，看看是否值得实现。