Основная проблема в этой задаче оптимизации имеет математический характер.
Ваша цель, как я понимаю из вашего определения метода 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'
... то есть
$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) уже были протестированы. , чтобы избежать их повторного тестирования, тогда и только тогда, когда :
- тестируемый метод дороже, чем поиск по хешу (это не относится к примеру кода, который вы предоставили выше, но может быть или не быть проблемой с вашим реальным кодом)
- хеш не увеличится до огромных размеров (либо все переменные связаны конечными интервалами, произведение которых является разумным числом - в этом случае проверка размера хеша может указать, полностью ли вы исследовали все пространство или нет), или Вы можете периодически очищать хеш, чтобы, по крайней мере, в течение одного промежутка времени вы могли обнаруживать столкновения.)
- в конечном счете, если вы считаете, что вышесказанное может относиться к вам, вы можете рассчитать различные варианты реализации (с хешем и без него) и посмотреть, стоит ли его реализовывать.