这个优化问题的主要挑战本质上是数学。
正如我从您对方法的定义中推断的那样,您的目标是通过查找各种变量(等)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)
- 正在测试的方法比哈希查找更昂贵(您上面提供的示例代码不是这种情况,但您的真实代码可能有问题,也可能没有问题)
- 散列不会增长到很大的比例(所有变量都受有限区间的约束,其乘积是一个合理的数字 - 在这种情况下,检查散列大小可以表明您是否已经完全探索了整个空间 - 或者您可以清除定期散列,因此一次至少有一个时间间隔,您确实有一些碰撞检测。)
- 最终,如果您认为上述内容适用于您,您可以对各种实施选项(有和没有散列)计时,看看是否值得实施。