如何在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： 这里的限制条件可以通过蛮力法简单地解决。然而，如果存在许多具有大量可能值范围的变量，则蛮力法不是一个选择。

- Nathan Fellman

---

这个问题的主要挑战在于数学本质上。您的目标是通过为变量（如$a$，$c$）找到值区间，然后计算依赖变量（如$c$）的边界区间来剪枝搜索空间。 - vladr

Answer 1

这个优化问题的主要挑战是数学性质的。从你对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

我将为您翻译编程相关内容。请调整约束条件，仅使用=、<=和>=（不等式），假设我们的变量是离散的即整数值：

• '... < 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)元组（例如在哈希中），以避免再次测试它们，前提是只有：

• 被测试的方法比哈希查找更昂贵（这在您提供的示例代码中不适用，但在您的实际代码中可能是一个问题或不是问题）
• 哈希表不会变得非常庞大（所有变量都受有限区间的约束，其乘积是一个合理的数字 - 在这种情况下，检查哈希表大小可以指示您是否已完全探索了整个空间 - 或者您可以定期清除哈希表，以至少在一个时间间隔内进行一次冲突检测。）
  • 最终，如果您认为以上内容适用于您，则可以计时各种实现选项（使用和不使用哈希表），并查看是否值得实施。

- Vlad Romascanu

---

非常棒的答案。基本上这就是我所想的，但我没有写下来，也不知道要使用哪些正确的库。 :) - Robert P

Answer 2

我使用 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);
    }

以这种方式进行操作意味着容易检查结果以查看失败的情况，而不是整体的失败：

a = 25 | b = 11 | c = 23
    a_is_odd_between_10_18 失败
    a_less_than_b 失败
    b_greater_than_c 失败
a = 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 失败
a = 26 | b = 21 | c = 16
    a_is_odd_between_10_18 失败
    a_less_than_b 失败
a = 24 | b = 20 | c = 19
    a_is_odd_between_10_18 失败
    a_less_than_b 失败
a = 27 | b = 20 | c = 12
    a_is_odd_between_10_18 失败
    a_less_than_b 失败
a = 18 | b = 25 | c = 13
    a_is_odd_between_10_18 失败
a = 26 | b = 10 | c = 11
    a_is_odd_between_10_18 失败
    a_less_than_b 失败
    b_greater_than_c 失败
a = 14 | b = 27 | c = 0
    a_is_odd_between_10_18 失败
a = 6 | b = 28 | c = 20
    a_is_odd_between_10_18 失败

如果你想要更加高级的东西，我的 Brick 模块可以处理约束树，包括修剪和分支。这些在更大的系统中是有意义的，在那里您将混合和匹配不同情况下的各种约束，因为大部分代码都是设置约束对象。如果您只有一个情况，您可能只需要坚持您所拥有的。

祝你好运，:)

- brian d foy

---

这比我在问题中建议的天真实现更好，因为它更通用，使添加新约束更容易。然而，如果存在解决方案，它并不能保证解决方案。例如，如果rand()被破解并始终返回相同的值，则所有迭代将相同。 - Nathan Fellman

这只是为了更容易地检查当前迭代是否符合约束条件。 - Nathan Fellman

输入不是我的问题。给定输入，我告诉你它们是否满足条件。我只是用rand()作为一个例子。如何生成输入取决于你。这可能意味着使用Set::CrossProduct或其他迭代器。 - brian d foy

这个Data::Constraints模块似乎有问题。我只在perl-5.28.0上测试过它，但它似乎只会向run子例程发送两个参数：$[0]是类对象，而$[1]是您的check()参数中的第一个，其余参数则不会被发送。此外，如果您尝试将数组引用作为唯一传递的值，整个过程将悄无声息地崩溃。 - sail0r

我可能是用早期版本的模块发布了这篇文章，但没什么大不了的。我已经根据模块现在的功能进行了更新。谢谢！ - brian d foy

Answer 3

我不确定你能找到一个简单的答案（虽然我很想被证明是错的！）。

看起来你的问题非常适合使用遗传算法。适应度函数应该很容易编写，对于每个满足约束条件的情况得分为1，否则为0。AI::Genetic似乎是一个可以帮助你编写代码并理解你需要编写的内容的模块。

这比暴力方法要快。

- mirod

Answer 4

一个“真正”的答案需要解析表达式并推理关系。除此之外，我建议使用系统遍历值空间，而不是随机尝试值。例如，

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

我会把具有最多个体约束的变量放在最外层，其次是下一个最受限制的变量，以此类推。

至少使用这种结构，您不会多次测试相同的组合（随机版本很可能会这样做），如果您观察它运行，您可能会看到出现模式，从而可以缩短执行时间。

- joel.neely

---

谢谢。我在问题中增加了一个澄清，解决了答案中的小缺陷，但总的来说，这将始终给出一个解决方案（如果存在）。然而，如果有许多变量或它们具有大范围，则不太可扩展。 - Nathan Fellman

嵌套循环几乎总是处理这种情况的错误答案，因为您必须更改代码结构以处理更多情况。您需要一个可以扩展而不改变逻辑的解决方案。 - brian d foy

Answer 5

看起来Simo::Constrain是你想要的

- bgbg

---

你的回答中的链接缺乏细节。你能添加一个例子吗？ - Nathan Fellman

Answer 6

我会创建一个算法来生成一堆有效的列表，无论是随机生成的还是不随机生成的（这应该很简单），将它们写入文件，然后使用该文件来提供测试程序，以便它可以随机选择任何想要的列表。

- Marc