Perl에서 일련의 제약을 어떻게 해결합니까?
https://stackoverflow.com/questions/575515
-
05-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian문제
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 등.)
가장 좋은 전략은 많은 것을 추출하는 것입니다 선의 전체 제약 세트의 제약 조건, 경계를 추론하려고 시도합니다 (사용 선형 프로그래밍 기술, 아래 참조), 정리 된 가변 공간에 대한 철저한 (또는 비 결정적) 시행 착오 테스트를 진행합니다.
전형적인 선형 프로그래밍 문제 형식입니다.
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에서 당신은 고용 할 수 있습니다 수학 :: 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) 평등이 사용됩니다 (변수의 개별 IE 정수 값을 가정) :
- '... <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) 튜플은 이미 테스트를 피하기 위해 이미 테스트되었습니다. 경우에만:
- 테스트중인 방법은 해시 조회보다 비싸다 (위에서 제공 한 샘플 코드의 경우는 아니지만 실제 코드의 문제가 있거나 아닐 수도 있음).
- 해시는 엄청난 비율로 성장하지 않습니다 (모든 변수는 유한 간격으로 결합되어 있으며, 제품은 합리적인 숫자입니다.이 경우 해시 크기를 확인하면 전체 공간을 완전히 탐색했는지 여부를 확인할 수 있습니다. 해시는 정기적으로 한 번에 한 번에 한 번의 간격으로 충돌 감지가 있습니다.)
- 궁극적으로 위의 내용이 귀하에게 적용될 수 있다고 생각되면 다양한 구현 옵션 (해시 유무에 관계없이)에 시간을내어 구현할 가치가 있는지 여부를 확인할 수 있습니다.
다른 팁
나는 사용한다 데이터 :: 제약. 개별 제약을 구현하는 작은 서브 루틴을 작성한 다음 원하는 모든 제약 조건을 연속적으로 적용합니다. 나는 이것에 대해 조금 이야기합니다 마스터 링 Perl "동적 서브 루틴"장에서.
use Data::Constraint;
Data::Constraint->add_constraint(
'a_less_than_b',
run => sub { $_[1] < $_[2] },
description => "a < b",
);
Data::Constraint->add_constraint(
'b_greater_than_c',
run => sub { $_[2] > $_[3] },
description => "b > c",
);
Data::Constraint->add_constraint(
'a_greater_than_0',
run => sub { $_[1] > 0 },
description => "a > 0",
);
Data::Constraint->add_constraint(
'c_less_than_30',
run => sub { $_[3] < 30 },
description => "c < 30",
);
Data::Constraint->add_constraint(
'a_is_odd_between_10_18',
run => sub {
return 1 if( $_[1] < 10 or $_[1] > 18);
return 0 unless $_[1] % 2,
},
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 $c;
my $a = int rand $b;
return ($a, $b, $c);
}
이렇게하면 전체 실패 대신 실패한 내용을 확인하기 위해 결과를 쉽게 검사 할 수 있습니다.
a = 2 | b = 4 | c = 5
Failed a_less_than_b
Failed b_greater_than_c
a = 0 | b = 0 | c = 2
Failed a_greater_than_0
Failed a_less_than_b
Failed b_greater_than_c
a = 0 | b = 0 | c = 2
Failed a_greater_than_0
Failed a_less_than_b
Failed b_greater_than_c
a = 7 | b = 14 | c = 25
Failed a_less_than_b
Failed b_greater_than_c
a = 0 | b = 0 | c = 29
Failed a_greater_than_0
Failed a_less_than_b
Failed b_greater_than_c
a = 0 | b = 0 | c = 20
Failed a_greater_than_0
Failed a_less_than_b
Failed b_greater_than_c
a = 0 | b = 4 | c = 22
Failed a_greater_than_0
Failed a_less_than_b
Failed b_greater_than_c
a = 4 | b = 16 | c = 28
Failed a_less_than_b
Failed b_greater_than_c
a = 0 | b = 22 | c = 26
Failed a_greater_than_0
Failed a_less_than_b
Failed b_greater_than_c
a = 0 | b = 3 | c = 6
Failed a_greater_than_0
Failed a_less_than_b
Failed b_greater_than_c
더 하드 코어를 원한다면 내 벽돌 모듈은 가지 치기 및 가지를 포함한 제약의 나무를 처리합니다. 이러한 것들은 대부분의 코드가 제약 조건 객체를 설정하기 때문에 다양한 상황에 대한 다양한 제약 조건을 혼합하고 일치시키는 더 큰 시스템에 적합합니다. 한 가지 상황 만 있다면 아마도 당신이 가진 것을 고수하고 싶을 것입니다.
행운을 빕니다, :)
"실제"대답은 관계에 대한 표현과 추론을 구문 분석해야합니다. 그 결과, 무작위로 값을 시도하는 대신 값 공간의 체계적인 횡선을 사용하는 것이 좋습니다. 예를 들어,
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;
}
}
}
나는 가장 개별적인 제약 조건으로 변수를 가장 바깥 쪽 레벨, 다음에 가장 제한된 다음으로 제한하는 등을 배치했습니다.
적어도이 구조에서는 동일한 조합을 여러 번 테스트하지 않으며 (임의 버전이 가능하기 때문에) 실행을 보면 실행을 짧게 줄일 수있는 패턴이 나타날 수 있습니다.
그것은 것 같습니다 사이모 :: 제약 당신이 원하는 것입니다
대신 무작위로 생성 여부를 무작위로 생성 여부 (사소한 일이어야 함)를 생성 한 알고리즘을 생성 한 다음 파일에 작성한 다음 해당 파일을 사용하여 테스트 프로그램을 공급하여 목록을 무작위로 선택할 수 있습니다. 원한다.
