پاورپوینت حل مساله استفاده درخت فضای حالت

فرمت فایل : پاورپوینت

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

Backtracking 1 مساله کوله پشتی 1-0 روش backtracking حل مساله استفاده درخت فضای حالت
تا پایان جستجو امکان فهمیدن ایا یک گره جواب خیر وجود ندارد.
باید بهینه سازی درنظر داشت. اگر مجموع ارزش گره بیشتر بهترین جوابی باشد کنون دست اورده ایم, مقدار بهترین جواب مقدار جدید تغییر دهیم.
فرض: weight: مجموع وزن کالاهایی تاکنون گره اضافه شده اند.
profit : مجموع ارزش کالاهایی گرعه جاری حساب امده اند.
bound: یک حد بالا ارزشی توانیم بسط گره برسیم.
totweight: حداکثر وزن کالاهای قابل انتخاب
maxprofit: مقدار ارزش بهترین جوابی کنون پیدا شده. Backtracking 2 کالاها صورت غیرنزولی اساس مقادیر 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 ام Backtracking 3 مثال profit
weight
bound هر گره M=16 Backtracking 4 0
0
115 0 40
2
115 1 40,2 Backtracking 5 0
0
115 0 40
2
115 1 70
7
115 2 120
17
0 3 70
7
80 4 40,2 30,5 50,10 تعداد گره= 2n+1-1 Backtracking 6 void knapsack(int i, int profit, int weight)
{ if weight <= M && profit > maxprofit)
{ maxprofit=profit;
numbest=i;
bestset=include;
}
if (promising (i))
{ include[i+1]=“yes”;
knapsack(i+1, profit+p[i+1],weight+w[i+1]);
include[i+1]=“no”;
knapsack(i+1, profit,weight);
}
}

الگوریتم مساله کوله پشتی روش backtracking Backtracking 7 int promising(int i)
{ int j,k,totweight; float bound;
if(weight>=M)
return 0;
else
{ j=i+1;
bound=profit;
totweight=weight;
while (j<=n && totweight+w[j] <=M)
{ totweight= totweight+w[j];
bound=bound+p[j];
j++;
}
k=j;
if (k<=n)
bound=bound+(M- totweight)*p[k]/w[k];
return bound>maxprofit;
}
}

 متن بالا فقط تکه محتوی متن پاورپوینت میباشد صورت نمونه در درج شدهاست.شما بعد پرداخت انلاین فایل فورا دانلود نمایید