دسته : پاورپوینت روش شاخه و حد (branch and bound) در 16 اسلاید زیبا و قابل ویرایش با فرمت pptx
فهرست مطالب
روش شاخه و حدbranch and bound
روش اول سطح
الگوریتم روش اول سطح
روش اول بهترین
الگوریتم روش اول بهترین
مسأله فروشنده دوره گرد با روش شاخه و حد
مثال ها
الگوریتم فروشنده دوره گرد
قسمتی از متن
مشابه روش backtracking از جستجو در درخت فضای حالت استفاده می کند.
روش خاصی برای پیمایش درخت استفاده نمی کند.
تنها برای مسائل بهینه سازی استفاده می شود.
انواع:
جستجوی اول بهترین
جستجوی سطحی
کالاها را به صورت غیرنزولی بر اساس مقادیر pi / wi مرتب می کنیم.
گره سطح k : گرهی که موجب تجاوز مجموع وزن از مرز M می شود.
در سطح i پیش بینی از حداکثر ارزش قابل دستیابی, برابر با مجموع ارزش به دست آمده به علاوه ارزش کالاهای باقی مانده تا سطح k-1 به علاوه مقدار قابل انتخاب از کالای k ام (با فرض این که بتوان بخشی از آن را انتخاب کرد) می باشد.
در هر مرحله همه گره های آن سطح ایجاد می شوند و اگر bound ≤ maxprofit : گره غیر وعده گاه است.
مثال: مسأله کوله پشتی 1- 0 با روش اول بهترین
پس از ملاقات همه فرزندان یک گره, در بین همه گره هایی که بسط داده نشده اند گره با بهتدین حد انتخاب می شود...