پاورپوینت روش شاخه و حد (pptx) 17 اسلاید

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

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

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

قسمتی از متن PowerPoint (.pptx) :

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 ام Branch and Bound 5 روش اول سطح 0 0 115 0 تعداد گره= 2n+1-1 Branch and Bound 6 الگوریتم روش اول سطح void knapsack_bf(int n, in p[], int w[], int M, int &maxprofit) { queue_of_node Q; node u,v; initialize (Q); // تهی v.level=0; v.profit=0; v.weight=0; maxprofit=0; enqueue(Q,v); while (!empty(Q)) { dequeue (Q,v); u.level=v.level+1; u.weight= v.weight+w[u.level]; u.profit=v.profit+p[u.level]; if (u.weight <= M && u.profit > maxprofit) maxprofit=u.profit; if (bound(u) > maxprofit) enqueue(Q,u); u.weight=v.weight; u.profit=v.profit; if (bound(u) > maxprofit) enqueue(Q,u); } } Branch and Bound 7 float bound (node u) { int j,k,totweight; float result; if (u.weight >= M) return 0; else { result=u.profit; j=u.level+1; totweight=u.weight; while (j<=n && totweight+w[j] <= M) { totweight=totweight+w[j]; result+=p[j]; j++; } k=j; if (k<=n) result+=(M-totweight)*p[k]/w[k]; return result; } } Branch and Bound 8 پس از ملاقات همه فرزندان یک گره, در بین همه گره هایی که بسط داده نشده اند گره با بهتدین حد انتخاب می شود. مثال: مسأله کوله پشتی 1- 0 با روش اول بهترین Branch and Bound 9 روش اول بهترین 0 0 115 0 تعداد گره= 2n+1-1