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

لینک دانلود و خرید پایین توضیحات
دسته بندی : پاورپوینت
نوع فایل :  powerpoint (..ppt) ( قابل ويرايش و آماده پرينت )
تعداد اسلاید : 17 اسلاید

 قسمتی از متن powerpoint (..ppt) : 
 

روش شاخه و حد  branch and bound
1
Branch and Bound
مشابه روش backtracking از جستجو در درخت فضای حالت استفاده می کند.
روش خاصی برای پیمایش درخت استفاده نمی کند.
تنها برای مسائل بهینه سازی استفاده می شود.
انواع: جستجوی اول بهترین
جستجوی سطحی
2
Branch and Bound
مثال: مسأله کوله پشتی 1- 0 با روش اول سطح
i
p i
w i
p i /w i
1
40
2
20
2
30
5
6
3
50
10
5
4
10
5
2
M=16
3
Branch and Bound
کالاها را به صورت غیرنزولی بر اساس مقادیر p i / w i مرتب می کنیم.
گره سطح k : گرهی که موجب تجاوز مجموع وزن از مرز M می شود.
در سطح i پیش بینی از حداکثر ارزش قابل دستیابی, برابر با مجموع ارزش به دست آمده به علاوه ارزش کالاهای باقی مانده تا سطح k-1 به علاوه مقدار قابل انتخاب از کالای k ام (با فرض این که بتوان بخشی از آن را انتخاب کرد) می باشد.
در هر مرحله همه گره های آن سطح ایجاد می شوند و اگر bound ≤ maxprofit : گره غیر وعده گاه است.
totweight = weight+  w j
bound = (profit+  p j )+(M-totweight)(p k / w k )
j=i+1
k-1
j=i+1
k-1
ارزش اولین k-1
کالای انتخاب شده
ظرفیت باقی مانده
برای کالای k ام
ارزش واحد وزن
کالای k ام
4
Branch and Bound