如何在Perl中解决一组约束？

我在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: 这里的约束很容易用暴力解决.但是,如果有许多变量具有大范围的可能值,则不能选择强力.

该优化问题的主要挑战是数学性质.

你的目标,因为我可以从你的定义推断gen_abc方法,是寻找边界间隔为您的各种变量(修剪你的搜索空间$a,$b等等)

最好的策略是从您的全部约束中提取尽可能多的线性约束,尝试推断边界(使用线性编程技术,见下文),然后针对a进行详尽的(或非确定性的)试错法测试.修剪变量空间.

典型的线性规划问题的形式如下:

minimize (maximize) 
subject to 

例如,给定三个变量,a,b和c,以及下面的线性约束:

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

你可以找到的上限和下限$a,$b并且$c如下:

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

在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)元组已经过测试可能或者可能不是一个好主意,以避免再次测试它们,如果并且只有在:

正在测试的方法比哈希查找更昂贵(上面提供的示例代码不是这种情况,但实际代码可能存在问题,也可能不存在问题)

哈希不会增长到很大的比例(要么所有变量都是有限的间隔,其产品是一个合理的数字 - 在这种情况下,检查哈希大小可以表明你是否已经完全探索了整个空间 - 或者你可以清除这个散列是周期性的,所以至少在你有一些碰撞检测的时间间隔内.)

最终,如果您认为以上内容适用于您,您可以计算各种实现选项(使用和不使用哈希)并查看是否值得实现.