مستخدم:Abdeaitali/التفريغ والتحديد
التفريغ والتحديد (بالانجليزية Branch and bound) هو نموذج تصميم خوارزمية لحل مشاكل الاستمثال المنفصل والتوافقي ، وكذلك الاستمثال الرياضي. اتقوم الخوارزمية بتعداد منهجي للحلول عن طريق البحث في مجموعة الحلول. يمكن تشبيه عملية التعداد بشجرة متجذرة مع المجموعة الكاملة للحلول. تقوم الخوارزمية باستكشاف فروع هذه الشجرة ، والتي تمثل مجموعة فرعية من مجموع الحلول. قبل تعداد حل من الحلول، يتم مقارنة قيمة الحل بالقيمة العلوية والسفلية للحل الأمثل المقدرة سابقا. فإذا كان أحسن حل من الفرع أسوء من القيمة العلوية والسفلية للحل الأمثل يتم التخلص من هذا الفرع.
الخوارزمية تعتمد على جودة تقدير القيمة العلوية والسفلية للحل الأمثل.
اقترح كل من لاند و دويغ طريقة التفريغ والتحديد سنة 1960 لحل مسائل البرمجة المنفصلة.[1] اصبحت الطريقة من بين أكثر الأدوات استعمالا لحل مشاكل الاستمثال التي تدخل في صنف ن.ب.صعب.[2]
نظرة عامة[عدل]
الهدف من خوارزمية التفريغ والتحديد هو ايجاد قيمة x للحصول على اكبر أو أصغر قيمة لدالة الأعداد الحقيقية (f(x بحيث ان x يمكن ان ياخد اي قيمة في المجموعة S. تسمى المجموعة S بمجموعة الحلول الممكنة.
References[عدل]
- ^ A. H. Land and A. G. Doig. DOI:10.2307/1910129.
{{استشهاد بخبر}}: الوسيط|title=غير موجود أو فارغ (مساعدة)الوسيط|الأخير=تم تجاهله (مساعدة); الوسيط|دوي=تم تجاهله (مساعدة); مفقود أو فارغ|title=(مساعدة) - ^ اكتب عنوان المرجع بين علامتي الفتح
<ref>والإغلاق</ref>للمرجعclausen99
[[:تصنيف:استمثال توافقي]]