دانلود پاورپوینت روش شاخه و حد

لینک دانلود و خرید پایین توضیحات

دسته بندی : پاورپوینت

نوع فایل :  .ppt ( قابل ویرایش و آماده پرینت )

تعداد اسلاید : 17 اسلاید

 قسمتی از متن .ppt : 

Branch and Bound

1

روش شاخه و حد branch and bound

Branch and Bound

2

مشابه روش backtracking از جستجو در درخت فضای حالت استفاده می کند.

روش خاصی برای پیمایش درخت استفاده نمی کند.

تنها برای مسائل بهینه سازی استفاده می شود.

انواع: جستجوی اول بهترین

جستجوی سطحی

Branch and Bound

3

مثال: مسأله کوله پشتی 1- 0 با روش اول سطح

M=16

Branch and Bound

4

کالاها را به صورت غیرنزولی بر اساس مقادیر pi / wi مرتب می کنیم.

گره سطح k : گرهی که موجب تجاوز مجموع وزن از مرز M می شود.

در سطح i پیش بینی از حداکثر ارزش قابل دستیابی, برابر با مجموع ارزش به دست آمده به علاوه ارزش کالاهای باقی مانده تا سطح k-1 به علاوه مقدار قابل انتخاب از کالای k ام (با فرض این که بتوان بخشی از آن را انتخاب کرد) می باشد.

در هر مرحله همه گره های آن سطح ایجاد می شوند و اگر bound ≤ maxprofit : گره غیر وعده گاه است.

totweight = weight+  wj

bound = (profit+  pj )+(M-totweight)(pk / wk)

j=i+1

k-1

j=i+1

k-1

ارزش اولین k-1

کالای انتخاب شده

ظرفیت باقی مانده

برای کالای k ام

ارزش واحد وزن

کالای k ام