كيف يمكنني حل مجموعة من القيود في بيرل؟

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 إلخ.)

أفضل استراتيجية هي استخراج أكبر عدد ممكن خطي القيود من مجموعة كاملة من القيود، وحاول استنتاج الحدود (باستخدام البرمجة الخطية تقنيات، انظر أدناه)، ثم تابع اختبارات تجريبية (أو غير حتمية) شاملة (أو غير محددة) ضد مساحة متغيرة ذات تقللة.

نموذجي مشكلة البرمجة الخطية هو من النموذج:

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

في بيرل قد توظف الرياضيات :: 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 '
• '...> 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) تم اختبار tuples بالفعل، وتجنب اختبارها مرة أخرى، إذا وفقط إذا:

• تتمثل الطريقة التي يتم اختبارها أكثر تكلفة من بحث التجزئة (هذا ليس هو الحال مع نموذج التعليمات البرمجية الذي قدمته أعلاه، ولكن قد يكون أو لا يكون مشكلة مع الرمز الحقيقي الخاص بك)
• لن ينمو التجزئة على نسب هائلة (إما أن جميع المتغيرات ملزمة بفواصل فترات محدودة، التي يكون منتجها رقما معقولا - في هذه الحالة يمكن تحديد حجم حجم التجزئة أن يشير ما إذا كنت قد استكشفت تماما مساحة كاملة أم لا -، أو يمكنك مسحها التجزئة بشكل دوري حتى على الأقل لفترة زمنية واحدة في وقت قمت به بعض الكشف عن الاصطدام.)
  • في النهاية، إذا كنت تعتقد أن ما سبق يمكن أن ينطبق عليك، فيمكنك الوقت خيارات التنفيذ المختلفة (مع وبدون التجزئة) ومعرفة ما إذا كان يستحق التنفيذ أم لا.

Answer 2

أنا أستعمل البيانات :: القيد. وبعد تكتب التروتات الفرعية الصغيرة التي تنفذ القيود الفردية ثم تطبق جميع القيود التي تريدها. أنا أتحدث عن هذا قليلا في إتقان بيرل في الفصل "الروتين الديناميكي" الفصل.

استخدام البيانات :: القيد؛ البيانات :: contraint-> add_centraint ('a_less_than_b'، تشغيل => sub {$ _ [1] <$ _ [2]}، الوصف => "a <b"،)؛ البيانات :: القيد> add_centraint ('b_greater_than_c'، تشغيل => sub {$ _ [2]> $ _ [3]}، الوصف => "B> C"،)؛ البيانات :: القيد> add_constraint ('a_greater_than_0'، تشغيل => sub {$ _ [1]> 0}، الوصف => "a> 0"،)؛ البيانات :: القيد-> Add_Constraint ('c_less_than_30'، تشغيل => sub {$ _ [3] <30}، الوصف => "C <30"،)؛ البيانات :: القيد-> Add_Constraint ('A_IS_ODD_BETWEN_10_18'، تشغيل => SUB {EXTER 1 إذا ($ _ [1] <10 أو $ _ [1]> 18)؛ عودة 0 ما لم $ _ [1]٪ 2،} وصف => "أ هو غريب بين 10 و 18"،)؛ ل (1 .. 10) {My ($ A، $ B، $ c) = gen_abc ()؛ طباعة "A = $ A | B = $ B | C = $ c  n"؛ Foreach اسمي $ (البيانات :: Constition-> get_all_names) {print " tfailed $ اسم  n" } gen_abc الفرعية {بلدي $ c = int rand 30؛ بلدي $ B = int rand $ c؛ بلدي $ a = int rand $ b؛ العودة ($ A، $ B، $ c)؛ }

القيام بذلك بهذه الطريقة يعني أنه من السهل فحص النتيجة لمعرفة ما فشل بدلا من فشل عام:

A = 2 | ب = 4 | C = 5 فشل فشل a_less_than_b b_greater_than_c a = 0 | ب = 0 | C = 2 فشل a_greater_than_0 فشل فشل a_ger_than_b b_greater_than_c a = 0 | ب = 0 | C = 2 فشل a_greater_than_0 فشل فشل a_ger_than_b b_greater_than_c a = 7 | ب = 14 | C = 25 فشل فشل a_less_than_b b_greater_than_c a = 0 | ب = 0 | C = 29 فشل A_GREATER_THAN_0 فشل A_GRELS_THAN_B فشل B_Greater_than_c A = 0 | ب = 0 | C = 20 فشل A_GREATER_THAN_0 فشل A_GREAL_THAN_B فشل B_Greater_than_c A = 0 | ب = 4 | C = 22 فشل فشل a_greater_than_0 فشل a_ger_than_b فشل b_greater_than_c a = 4 | ب = 16 | C = 28 فشل a_less_than_b فشل b_greater_than_c a = 0 | ب = 22 | C = 26 فشل A_GREATER_THAN_0 فشل A_GREAL_THAN_B فشل B_Greater_than_c A = 0 | ب = 3 | C = 6 فشل A_Greater_Than_0 فشل فشل A_GRAN_THAN_B B_GREATER_THAN_C

إذا كنت تريد شيئا أكثر المتشددين، بلدي قالب طوب وحدة تعالج أشجار القيود، بما في ذلك التقليم والتفريع. هذه الأشياء منطقي أنظمة أكبر حيث يمكنك خلط وتتناسب مع العديد من القيود المختلفة للحالات المختلفة لأن معظم التعليمات البرمجية تقوم بإعداد كائنات القيد. إذا كان لديك موقفك الوحيد فقط، فربما تريد الالتزام بما لديك.

حظ سعيد، :)

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

لست متأكدا من أنك ستجد إجابة بسيطة على هذا (على الرغم من أنني أود أن أكون خاطئا!).

يبدو أن مشكلتك ستكون مناسبة تماما ل الخوارزمية الوراثية. وبعد يجب أن تكون وظيفة اللياقة البدنية سهلة الكتابة، فقط النتيجة 1 لكل قيد راض، 0 خلاف ذلك. منظمة العفو الدولية :: Genetic. يبدو أن الوحدة النمطية التي يمكن أن تساعدك، وكلاهما لكتابة الكود وفهم ما تحتاجه للكتابة.

يجب أن يكون هذا أسرع من طريقة القوة الغاشمة.

Answer 5

يبدو أن Simo :: Constrain. هو ما تريد

Answer 6

وأود بدلا من ذلك إنشاء خوارزمية تنشئ مجموعة من القوائم الصحيحة أو التي تم إنشاؤها بشكل عشوائي أو لا (يجب أن تكون تافهة)، ثم اكتبها إلى ملف، ثم استخدم هذا الملف لإطعام برنامج الاختبار، حتى يتمكن من اختيار أي قائمة بشكل عشوائي يريد.