متفرع ومحدود

📅 آخر تحديث: ٣١ يوليو ٢٠٢٦
✍️ نُشر في: ٣١ يوليو ٢٠٢٦
📷 يحتوي على 24 صور
الموسوعة الحرة

التفرع والتقييد ( BB أو B&B ​​أو BnB ) هي طريقة لحل مشاكل التحسين عن طريق تقسيمها إلى مشاكل فرعية أصغر واستخدام دالة تقييد لإزالة المشاكل الفرعية التي لا يمكن أن تحتوي على الحل الأمثل.

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

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

تعتمد الخوارزمية على التقدير الفعال للحدود الدنيا والعليا لمناطق/فروع فضاء البحث. إذا لم تتوفر أي حدود، فإن الخوارزمية تتحول إلى بحث شامل.

طُرحت هذه الطريقة لأول مرة من قِبل أيلسا لاند وأليسون دويغ أثناء إجراء بحث في كلية لندن للاقتصاد برعاية شركة بريتيش بتروليوم عام 1960 في مجال البرمجة المنفصلة ، ​​[ 1 ] [ 2 ] وأصبحت الأداة الأكثر شيوعًا لحل مسائل التحسين الصعبة من نوع NP . [ 3 ] ظهر مصطلح "التفرع والتقييد" لأول مرة في عمل ليتل وآخرون حول مسألة البائع المتجول . [ 4 ] [ 5 ]

ملخص

يهدف خوارزمية التفرع والتقييد إلى إيجاد قيمة x التي تُعظّم أو تُصغّر قيمة دالة حقيقية f ( x ) ، تُسمى دالة الهدف ، ضمن مجموعة S من الحلول المقبولة أو المرشحة . تُسمى المجموعة S فضاء البحث، أو المنطقة الممكنة . يفترض ما تبقى من هذا القسم أن المطلوب هو تصغير f ( x ) ؛ وهذا الافتراض لا يُخلّ بعمومية الحل ، إذ يُمكن إيجاد القيمة القصوى لـ f ( x ) بإيجاد القيمة الدنيا لـ g ( x ) = −f ( x ) . تعمل خوارزمية التفرع والتقييد وفقًا لمبدأين:

يتطلب تحويل هذه المبادئ إلى خوارزمية ملموسة لمسألة تحسين محددة نوعًا من بنية البيانات التي تمثل مجموعات الحلول المرشحة. يُطلق على هذا التمثيل اسم " حالة المسألة". لنرمز إلى مجموعة الحلول المرشحة لحالة I بالرمز S<sub> I</sub> . يجب أن يتضمن تمثيل الحالة ثلاث عمليات:

  • ينتج عن الدالة branch( I ) حالتان أو أكثر، تمثل كل منهما مجموعة جزئية من S I. (عادةً ما تكون المجموعات الجزئية منفصلة لمنع الخوارزمية من زيارة نفس الحل المرشح مرتين، ولكن هذا ليس شرطًا. ومع ذلك، يجب أن يكون الحل الأمثل ضمن S I موجودًا في مجموعة جزئية واحدة على الأقل. [ 6 ] )
  • يحسب bound( I ) حدًا أدنى لقيمة أي حل مرشح في الفضاء الذي يمثله I ، أي أن bound ( I ) ≤ f ( x ) لجميع x في S I.
  • تحدد الدالة solution( I ) ما إذا كان I يمثل حلاً مرشحاً وحيداً. (اختيارياً، إذا لم يكن كذلك، فقد تختار العملية إرجاع حل ممكن من بين S I. [ 6 ] ) إذا أرجعت solution( I ) حلاً، فإن f (solution( I )) توفر حداً أعلى لقيمة الهدف الأمثل على كامل فضاء الحلول الممكنة.

باستخدام هذه العمليات، تُجري خوارزمية التفرع والتقييد بحثًا تكراريًا من أعلى إلى أسفل عبر شجرة الحالات المُشكَّلة بواسطة عملية التفرع. عند زيارة حالة I ، تتحقق الخوارزمية مما إذا كان الحد (bound( I )) مساويًا أو أكبر من الحد الأعلى الحالي؛ إذا كان الأمر كذلك، يمكن استبعاد I بأمان من البحث ويتوقف التكرار. تُنفَّذ خطوة التقليم هذه عادةً عن طريق الاحتفاظ بمتغير عام يُسجِّل الحد الأعلى الأدنى الذي تم رصده بين جميع الحالات التي تم فحصها حتى الآن.

النسخة العامة

فيما يلي الهيكل الأساسي لخوارزمية عامة للتفرع والتقييد لتقليل دالة هدف اختيارية f . [ 3 ] للحصول على خوارزمية فعلية من هذا الهيكل، يلزم وجود دالة تقييد bound ، التي تحسب الحدود الدنيا لـ f على عقد شجرة البحث ، بالإضافة إلى قاعدة تفرع خاصة بالمسألة. وبذلك، فإن الخوارزمية العامة المعروضة هنا هي دالة من الرتبة العليا .

  1. باستخدام طريقة استدلالية ، أوجد حلاً x h لمسألة التحسين. خزّن قيمته، B = f ( x h ) . (إذا لم تتوفر طريقة استدلالية، فاجعل B تساوي اللانهاية). سيمثل B أفضل حل تم التوصل إليه حتى الآن، وسيُستخدم كحد أعلى للحلول المرشحة.
  2. قم بتهيئة قائمة انتظار لحفظ حل جزئي بدون تعيين أي من متغيرات المسألة.
  3. استمر في التكرار حتى تصبح قائمة الانتظار فارغة:
    1. قم بإزالة عقدة N من قائمة الانتظار.
    2. إذا كان N يمثل حلاً مرشحاً واحداً x وكان f ( x ) < B ، فإن x هو أفضل حل حتى الآن. سجله واجعل B ← f ( x ) .
    3. وإلا، قم بالتفرع على N لإنتاج عقد جديدة Ni . لكل من هذه:
      1. إذا كان الحد ( N i ) > B ، فلا تفعل شيئًا؛ نظرًا لأن الحد الأدنى على هذه العقدة أكبر من الحد الأعلى للمشكلة، فلن يؤدي ذلك أبدًا إلى الحل الأمثل، ويمكن تجاهله.
      2. وإلا، فقم بتخزين N i في قائمة الانتظار.

يمكن استخدام العديد من هياكل بيانات الطوابير المختلفة . يوفر هذا التطبيق القائم على طابور FIFO بحثًا بالعرض أولًا . بينما يوفر المكدس (طابور LIFO) خوارزمية بحث بالعمق أولًا . ويمكن الحصول على خوارزمية التفرع والتقييد الأفضل أولًا باستخدام طابور أولوية يرتب العقد وفقًا لحدودها الدنيا. [ 3 ]

من أمثلة خوارزميات البحث الأفضل أولاً التي تعتمد على هذه الفرضية خوارزمية ديكسترا وخوارزمية البحث A* المشتقة منها . يُنصح باستخدام خوارزمية البحث العميق أولاً عندما لا تتوفر طريقة استدلالية جيدة لإنتاج حل أولي، لأنها تُنتج حلولاً كاملة بسرعة، وبالتالي حدوداً عليا. [ 7 ]

الشفرة الزائفة

تطبيق الشفرة الزائفة لما سبق، على غرار لغة C ++، هو:

// تطبيق يشبه لغة C++ لخوارزمية التفرع والتقييد،// بافتراض أن دالة الهدف f هي التي يجب تصغيرهاحل التوافقية ( حل التفرع والتقييد (مشكلة اندماجية ,دالة الهدف objective_function /*f*/ ,BoundingFunction lower_bound_function /*bound*/ ){// الخطوة 1 أعلاه.double problem_upper_bound = std :: numeric_limits <double> :: infinity ; // = BCombinatorialSolution heuristic_solution = heuristic_solve ( problem ); // x_hproblem_upper_bound = objective_function ( heuristic_solution ); // B = f(x_h)الحل التوافقي الأمثل الحالي = الحل الاستدلالي ؛// الخطوة 2 أعلاهقائمة الانتظار < شجرة الحلول المرشحة > قائمة_المرشحين ؛// تهيئة قائمة الانتظار الخاصة بالمشكلةcandidate_queue = populate_candidates ( problem );بينما ( ! قائمة_المرشحين.فارغة ( ) ) { // الخطوة 3 أعلاه// الخطوة 3.1CandidateSolutionTree node = candidate_queue.pop ( ) ;// "node" يمثل N أعلاهإذا كان ( node.presents_single_candidate ( )) { // الخطوة 3.2إذا كانت دالة الهدف ( العقدة.المرشح ( )) أقل من الحد الأعلى للمشكلة ، {القيمة_الأمثل_الحالية = node.candidate ( ) ;problem_upper_bound = objective_function ( current_optimum );}// وإلا، فإن العقدة مرشحة واحدة وليست مثالية}وإلا { // الخطوة 3.3: تمثل العقدة فرعًا من الحلول المرشحة// يمثل "child_branch" N_i أعلاهfor ( auto && child_branch : node.candidate_nodes ) {​​إذا كانت دالة الحد الأدنى ( الفرع الفرعي ) أقل من أو تساوي الحد الأعلى للمشكلة ، {candidate_queue.enqueue ( child_branch ) ; // الخطوة 3.3.2}// وإلا، فإن bound(N_i) > B، لذا نقوم بحذف الفرع؛ الخطوة 3.3.1}}}أعد القيمة المثلى الحالية ؛}

في الشفرة الزائفة أعلاه، يجب تحديد الدوال heuristic_solveالتي populate_candidatesيتم استدعاؤها كإجراءات فرعية حسب ما ينطبق على المسألة. تُعامل الدالتان f ( objective_function) و bound ( ) ككائنات دالة كما هي مكتوبة، ويمكن أن تتوافق مع تعابير لامدا ، ومؤشرات الدوال ، وأنواع أخرى من الكائنات القابلة للاستدعاء في لغة البرمجة C++.lower_bound_function

التحسينات

متىx{\displaystyle \mathbf {x} }هو متجه منRن{\displaystyle \mathbb {R} ^{n}}يمكن دمج خوارزميات التفرع والتقييد مع تحليل الفترات [ 8 ] وتقنيات المقاول لتوفير أغلفة مضمونة للحد الأدنى العالمي. [ 9 ] [ 10 ]

التطبيقات

يُستخدم هذا النهج في عدد من المسائل الصعبة من نوع NP :

قد تُشكّل خوارزمية التفرع والتقييد أساسًا للعديد من الطرق الاستدلالية . على سبيل المثال، قد يرغب المرء في إيقاف التفرع عندما تصبح الفجوة بين الحدين الأعلى والأدنى أصغر من عتبة معينة. يُستخدم هذا الأسلوب عندما يكون الحل "جيدًا بما يكفي للأغراض العملية"، ويمكنه تقليل العمليات الحسابية المطلوبة بشكل كبير. يُعدّ هذا النوع من الحلول مناسبًا بشكل خاص عندما تكون دالة التكلفة المستخدمة غير دقيقة أو ناتجة عن تقديرات إحصائية ، وبالتالي لا تُعرف بدقة، وإنما تُعرف فقط بأنها تقع ضمن نطاق من القيم باحتمالية محددة .

العلاقة بالخوارزميات الأخرى

يقدم ناو وآخرون تعميمًا لخوارزمية التفرع والتقييد يشمل أيضًا خوارزميات البحث A* و B* و alpha-beta . [ 16 ]

مثال على التحسين

يمكن استخدام أسلوب التفرع والتقييد لتحقيق أقصى قدر من النتائجZ=5x1+6x2{\displaystyle Z=5x_{1}+6x_{2}}مع مراعاة القيود

x1+x2≤50{\displaystyle x_{1}+x_{2}\leq 50}

4x1+7x2≤280{\displaystyle 4x_{1}+7x_{2}\leq 280}

x1،x2≥0{\displaystyle x_{1},x_{2}\geq 0}

x1{\displaystyle x_{1}}وx2{\displaystyle x_{2}}هي أعداد صحيحة.

الخطوة الأولى هي تخفيف قيد العدد الصحيح. لدينا نقطتان متطرفتان للمعادلة الأولى تشكلان خطاً مستقيماً:[x1x2]=[500]{\displaystyle {\begin{bmatrix}x_{1}\\x_{2}\end{bmatrix}}={\begin{bmatrix}50\\0\end{bmatrix}}}و[050]{\displaystyle {\begin{bmatrix}0\\50\end{bmatrix}}}يمكننا تشكيل الخط الثاني باستخدام نقاط المتجهات[040]{\displaystyle {\begin{bmatrix}0\\40\end{bmatrix}}}و[700]{\displaystyle {\begin{bmatrix}70\\0\end{bmatrix}}}.

السطران.

النقطة الثالثة هي[00]{\displaystyle {\begin{bmatrix}0\\0\end{bmatrix}}}هذه منطقة ذات غلاف محدب ، لذا يقع الحل على أحد رؤوس المنطقة. يمكننا إيجاد نقطة التقاطع باستخدام اختزال الصفوف، وهو[70/380/3]{\displaystyle {\begin{bmatrix}70/3\\80/3\end{bmatrix}}}بقيمة 276 + 2/3. نختبر نقاط النهاية الأخرى عن طريق مسح الخط فوق المنطقة ونجد أن هذه هي القيمة القصوى على الأعداد الحقيقية.

نختار المتغير ذو الجزء الكسري الأكبر، في هذه الحالةx2{\displaystyle x_{2}}يصبح هذا هو المعامل الخاص بطريقة التفرع والتقييد. نتفرع إلىx2≤26{\displaystyle x_{2}\leq 26}واحصل على 276 في⟨24،26⟩{\displaystyle \langle 24,26\rangle }لقد توصلنا إلى حل صحيح، لذا ننتقل إلى الفرع الآخر.x2≥27{\displaystyle x_{2}\geq 27}نحصل على 275.75 عند⟨22.75،27⟩{\displaystyle \langle 22.75,27\rangle }لدينا عدد عشري، لذلك نقوم بالتفرعx1{\displaystyle x_{1}}لx1≤22{\displaystyle x_{1}\leq 22}ونجد أن 274.571 عند⟨22،27.4286⟩{\displaystyle \langle 22,27.4286\rangle }نجرب الفرع الآخرx1≥23{\displaystyle x_{1}\geq 23}ولا توجد حلول ممكنة. لذلك، فإن الحد الأقصى هو 276.x1=24{\displaystyle x_{1}=24}وx2=26{\displaystyle x_{2}=26}.

انظر أيضاً

مراجع

  1. ↑ هـ. لاند وأ. ج. دويغ (1960). "طريقة آلية لحل مسائل البرمجة المنفصلة". مجلة Econometrica . 28 (3): 497-520 . doi : 10.2307/1910129 . JSTOR 1910129 . 
  2. ↑ "أخبار الموظفين" . www.lse.ac.uk. مؤرشف من الأصل بتاريخ 24 فبراير 2021. تم الاطلاع عليه بتاريخ 8 أكتوبر 2018 .
  3. 1 2 3 كلاوسن، ينس (1999). خوارزميات التفرع والتقييد - المبادئ والأمثلة (ملف PDF) (تقرير فني). جامعة كوبنهاغن . مؤرشف من الأصل (ملف PDF) بتاريخ 23 سبتمبر 2015. تم الاطلاع عليه بتاريخ 13 أغسطس 2014 .
  4. 1 2 ليتل، جون دي سي؛ مورتي، كاتا جي؛ سويني، دورا دبليو؛ كاريل، كارولين (1963). "خوارزمية لمسألة البائع المتجول" (ملف PDF) . بحوث العمليات . 11 (6): 972-989 . Bibcode : 1963OpRes..11..972L . doi : 10.1287/opre.11.6.972 . hdl : 1721.1/46828 .
  5. ↑ بالاس، إيغون؛ توث، باولو (1983). طرق التفرع والتقييد لمسألة البائع المتجول (ملف PDF) (تقرير). كلية الدراسات العليا للإدارة الصناعية بجامعة كارنيجي ميلون . مؤرشف (ملف PDF) من الأصل في 20 أكتوبر 2012.
  6. 1 2 Bader, David A.; Hart, William E.; Phillips, Cynthia A. (2004). "تصميم الخوارزميات المتوازية لخوارزمية التفرع والتقييد" (ملف PDF) . في Greenberg, HJ (محرر). دروس تعليمية حول المنهجيات والتطبيقات الناشئة في بحوث العمليات . دار نشر كلوير الأكاديمية. مؤرشف من النسخة الأصلية (ملف PDF) بتاريخ 13 أغسطس 2017. تم الاطلاع عليه بتاريخ 16 سبتمبر 2015 .
  7. ↑ ميلهورن، كورت ؛ ساندرز، بيتر (2008). الخوارزميات وهياكل البيانات: مجموعة الأدوات الأساسية (ملف PDF) . سبرينغر. ص 249. 
  8. ↑ مور، ر. إي. (1966). تحليل الفترات . إنجلوود كليف، نيو جيرسي: برنتيس هول. ISBN 0-13-476853-1.
  9. ^ جولين، ل. كيفير، م. ديدريت، O.؛ والتر، إي. (2001). تحليل الفاصل الزمني التطبيقي . برلين: سبرينغر. رقم ISBN 1-85233-219-0.
  10. ^ هانسن، إي آر (1992). التحسين العالمي باستخدام تحليل الفاصل الزمني . نيويورك: مارسيل ديكر.
  11. ↑ كونواي، ريتشارد والتر ؛ ماكسويل، ويليام ل .؛ ميلر، لويس و. (2003). نظرية الجدولة . منشورات كوريير دوفر. الصفحات 56-61 . ISBN  978-0-486-42817-8.
  12. ↑ فوكوناغا، كينوسوكي؛ ناريندرا، باتريناهالي م. (1975). "خوارزمية التفرع والتقييد لحساب أقرب k جار". معاملات IEEE للحاسبات . 100 (7): 750-753 . Bibcode : 1975ITCmp.100..750F . doi : 10.1109/tc.1975.224297 . S2CID 5941649 . 
  13. ↑ ناريندرا، باتريناهالي م.؛ فوكوناغا، ك. (1977). "خوارزمية التفرع والتقييد لاختيار مجموعة فرعية من الميزات" (ملف PDF) . معاملات IEEE في الحوسبة . C-26 (9): 917-922 . Bibcode : 1977ITCmp.100..917N . doi : 10.1109/TC.1977.1674939 . S2CID 26204315 . 
  14. ↑ حازمه، حسين؛ مازومدر، راهول؛ صعب، علي (2020). "الانحدار المتفرق على نطاق واسع: التفرع والتقييد المتجذر في التحسين من الدرجة الأولى". arXiv : 2004.06152 [ stat.CO ].
  15. ↑ نوفوزين، سيباستيان؛ لامبرت، كريستوف هـ. (2011). "التعلم المنظم والتنبؤ في رؤية الحاسوب". أسس واتجاهات في رسومات الحاسوب والرؤية . 6 ( 3-4 ): 185-365 . CiteSeerX 10.1.1.636.2651 . doi : 10.1561/0600000033 . ISBN  978-1-60198-457-9.
  16. ↑ ناو، دانا س.؛ كومار، فيبين؛ كانال، لافين (1984). "التفرع والتقييد العام، وعلاقته بـ A* و AO*" (ملف PDF) . الذكاء الاصطناعي . 23 (1): 29-58 . doi : 10.1016/0004-3702(84)90004-3 .
  • LiPS – برنامج مجاني سهل الاستخدام بواجهة رسومية مصمم لحل مسائل البرمجة الخطية والبرمجة العددية والبرمجة الهدفية.
  • Cbc – (Coin-or branch and cut) هو برنامج مفتوح المصدر لحل مسائل البرمجة الخطية المختلطة مكتوب بلغة C++.