मैं पर्ल में बाधाओं का एक सेट कैसे हल करूं?

Question

मैं पर्ल में कमी (की कमी का सिर्फ एक नमूना सेट, नहीं लोगों को मैं वास्तव में जरूरत है) के निम्नलिखित सेट है:

$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(); 
} 

अब, इस समाधान को समाप्त करने की गारंटी नहीं है, और सामान्य रूप से बहुत अक्षम है। पर्ल में ऐसा करने का कोई बेहतर तरीका है?

संपादित करें: मैं एक यादृच्छिक परीक्षण जनरेटर के लिए इस की जरूरत है, तो समाधान इस तरह के rand() के रूप में यादृच्छिक कार्यों का उपयोग करने की जरूरत है। एक समाधान है कि पूरी तरह से नियतात्मक है, पर्याप्त नहीं है, तो यह है कि समाधान मुझे संभव संयोजनों की एक सूची दे सकते हैं मैं यादृच्छिक पर एक सूचकांक का चयन कर सकते हैं, हालांकि:

@solutions = &find_allowed_combinations(); # solutions is an array of array references 
$index = int rand($#solutions); 
($a, $b, $c) = @$solution[$index]; 

संपादित करें 2: यहाँ बाधाओं के साथ हल करने के लिए आसान है पाशविक बल। हालांकि, यदि संभावित मूल्यों की एक बड़ी श्रृंखला के साथ कई चर हैं, तो ब्रूट फोर्स एक विकल्प नहीं है।

Answer 1

इस अनुकूलन समस्या में मुख्य चुनौती प्रकृति में गणितीय है।

अपने लक्ष्य, जैसा कि मैंने gen_abc विधि की अपनी परिभाषा से अनुमान लगा सकते हैं, अपने विभिन्न चर ($a, $b आदि के लिए बाउंडिंग अंतराल का पता लगाकर अपनी खोज को अंतरिक्ष छँटाई करने के लिए है)

सबसे अच्छी रणनीति की कमी के लिए अपना पूरा सेट से के रूप में कई रैखिक बाधाओं को निकालने के लिए है, सीमा (linear programming तकनीक का उपयोग का अनुमान लगाने के प्रयास, नीचे देखें), तो संपूर्ण (या गैर नियतात्मक के साथ आगे बढ़ना) trial- और एक छिद्रित चर अंतरिक्ष के खिलाफ त्रुटि परीक्षण।

एक ठेठ linear programming problem फार्म की है:

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

पर्ल में आप इस उद्देश्य के लिए 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 

... और इसलिए है कि केवल =, <= और >= (में) समानताओं उपयोग किया जाता है (हमारे चर के लिए यह सोचते हैं असतत यानी पूर्णांक मान) की कमी को समायोजित:

• '... < सी' हो जाय। ' .. < = सी -1 '
• ' ...> सी 'बन जाता है' ...> = सी + 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, 2 9, आदि) बशर्ते आप बाधाओं को अभिव्यक्तियों में पार्स कर सकें संबंधित मैट्रिक्स प्रतिनिधित्व जैसे:

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) tuples पहले से ही परीक्षण किया गया है के रूप में उन्हें फिर से परीक्षण से बचने के लिए, तभी यदि:

• विधि परीक्षण किया जा रहा एक हैश देखने से ज्यादा महंगा है (यह स्थिति नहीं है आपके द्वारा प्रदान किए गए नमूना कोड के साथ, लेकिन आपके असली कोड के साथ कोई समस्या हो सकती है या नहीं)
• हैश भारी अनुपात में नहीं बढ़ेगा (या तो सभी चर सीमित अंतराल से बंधे हैं, जिनका उत्पाद उचित संख्या है - इन हैश आकार की जांच करने वाला कौन सा मामला इंगित कर सकता है कि आपने पूरी जगह पूरी तरह से खोज ली है या नहीं, या आप समय-समय पर हैश को साफ़ कर सकते हैं ताकि कम से कम एक बार अंतराल के लिए आपके पास कुछ टकराव हो ection।)
  • आखिरकार, अगर आपको लगता है कि उपरोक्त आप पर लागू हो सकता है, तो आप कई कार्यान्वयन विकल्पों (हैश के साथ और बिना) समय देख सकते हैं और देख सकते हैं कि यह लागू करने योग्य है या नहीं।

Answer 2

ऐसा लगता है Simo::Constrain क्या आप

Answer 3

एक 'असली' जवाब चाहिए भाव और संबंधों के बारे में तर्क पार्स करने की आवश्यकता होगी है। उस से कम, मैं यादृच्छिक रूप से मूल्यों की कोशिश करने के बजाय, मूल्य स्थान के व्यवस्थित ट्रैवर्सल का उपयोग करने का सुझाव दूंगा। उदाहरण के लिए,

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

मैं चर सबसे व्यक्ति बाधाओं के साथ सबसे बाहरी स्तर पर डाल दिया था, अगले अगले सबसे विवश, आदि

कम से कम इस संरचना के साथ आप एक ही संयोजन का परीक्षण नहीं होगा कई बार (जैसा यादृच्छिक संस्करण करने की संभावना है) और यदि आप इसे देखते हैं, तो आप पैटर्न उभर सकते हैं जो आपको निष्पादन को कम करने देता है।

Answer 4

मुझे यकीन नहीं है कि आपको इसका एक सरल जवाब मिल जाएगा (हालांकि मैं गलत साबित करना चाहता हूं!)।

ऐसा लगता है कि आपकी समस्या को अच्छी तरह से एक genetic algorithm के लिए अनुकूल किया जाएगा। फिटनेस फ़ंक्शन लिखना आसान होना चाहिए, प्रत्येक संतुष्ट बाधा के लिए केवल 1 स्कोर करें, 0 अन्यथा। AI::Genetic एक ऐसा मॉड्यूल प्रतीत होता है जो कोड लिखने और आपको जो लिखने की आवश्यकता है उसे समझने में आपकी मदद कर सकता है।

यह एक ब्रूट फोर्स विधि से तेज़ होना चाहिए।

Answer 5

मैं इसके बजाय एक एल्गोरिदम बनाउंगा जो वैध सूचियों का एक गुच्छा उत्पन्न करता है, यादृच्छिक रूप से जेनरेट किया गया है या नहीं (यह छोटा होना चाहिए), उन्हें फ़ाइल में लिखें, और उसके बाद परीक्षण फ़ाइल को फ़ीड करने के लिए उस फ़ाइल का उपयोग करें, इसलिए वह यादृच्छिक रूप से अपनी इच्छित सूची चुनें।

Answer 6

मैं Data::Constraint का उपयोग करें। आप छोटी subroutines लिखते हैं जो व्यक्तिगत बाधाओं को लागू करते हैं, फिर आप चाहते हैं कि सभी बाधाओं को क्रमशः लागू करें। मैं इस बारे में "डायनामिक सबराउटिन" अध्याय में Mastering 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 

आप कुछ अधिक कट्टर चाहते हैं, मेरी Brick मॉड्यूल बाधाओं के पेड़ संभालती है, छंटनी और शाखाओं सहित। ये चीजें बड़ी प्रणालियों के लिए समझ में आती हैं जहां आप अलग-अलग परिस्थितियों के लिए विभिन्न बाधाओं को मिलाकर मैच करेंगे क्योंकि अधिकांश कोड बाधा वस्तुओं को स्थापित कर रहे हैं। यदि आपके पास केवल एक ही स्थिति है, तो शायद आप बस अपने पास रहना चाहते हैं।

शुभकामनाएं, :)