مسئله کوله پشتی صفر و یک

مسئله کوله پشتی صفر و یک

اسلاید 1: مراحل پیش رو :1- الگوریتم عقبگرد برای مسئله کوله پشتی صفر و یک2- مقایسه الگوریتم پویا و عقبگرد برای مسئله کوله پشتی صفر و یک

اسلاید 2: مسئله کوله پشتی صفر و یکدر این مسئله مجموعه ای از قطعات را داریم که هر یک دارای وزن و ارزش معین است وزن ها و ارزش ها اعداد صحیح مثبت هستند. دزدی قصد دارد قطعاتی را که می دزدد درون یک کوله پشتی قرار دهد و اگر وزن کل قطعات قرار داده شده در کوله پشتی از یک عدد صحیح W فراتر رود کوله پشتی پاره می شود . هدف تعیین مجموعه ای از قطعات است که ارزش کل قطعات را بیشینه می کند به طوری که وزن کل آن ها از W بیشتر نشود.

اسلاید 3: مسئله کوله پشتی صفر و یک به روش عقبگرداین مسئله را به صورت زیر به صورت یک درخت در می اوریم:هنگامی که از ریشه به سمت چپ می رویم نخستین قطعه در مجموعه قرار می گیردو اگر از ریشه به سمت راست حرکت کنیم قطعه اول در مجموعه قرار نمی گیرد.در سطح دوم نیز اگر از یک گره به سمت چپ حرکت کنیم قطعه دوم در مجموعه قرارمی گیرد و اگر به سمت راست حرکت کنیم این قطعه در مجموعه قرار نمی گیرد.در سایر سطوح نیز به همین صورت می باشد.مثال : فرض کنیم

اسلاید 4: نکته حائز اهمیت در این مساله این است که تا زمانی که جستجو به پایان نرسد نمی توان دریافت گره ای حاوی یک حل می باشد یا خیر.در مثال بهتر متوجه میشوید .

اسلاید 5: مثال: فرض کنید W=16,n=4 و داشته باشیم : قطعات از قبل بر اساس مرتب شده اند.

اسلاید 6: ابتدا با چند تعریف آشنا می شویم یعنی بهترین مسیری که در درخت پیموده ایم)) :بهترین مجموعه ای که تا به حال انتخاب کرده ایمBEST SET : :Max profit ارزش کل BEST SET include :مجموعه ی انتخابی در هر مرحله (مسیری که الان در نود انتهای آن هستیم). Profit : ارزش کل Include weight : وزن کل مجموعه includebound : فرض می کنیم در گره ای واقع در سطح i قرار داریم و گره ی واقع در سطح k گره ای است کهحاصل جمع اوزان را از بیشتر میکند در این صورت : W

اسلاید 7: W K boundاین فرمول به ما می گوید بهترین سودی که در این مرحله در ذهن ما می گنجد داشته باشیم چقدر است به این صورت که ما نمی توانیم عنصر سطح را برداریم چون در صورت انتخاب ان مجموع وزنها از ما بیشتر میشود ولی فرض میکنیم که ما میتوانیم به اندازه ای که کوله ی ما جا دارد بخشی از ان را برداریم لذا بهترین سود فرضی ما در هر مرحله است . در هر مرحله بایستی انرا محاسبه نماییمدر ادامه بهتر متوجه میشوید

اسلاید 8: مثال: فرض کنید W=16,n=4 و داشته باشیم : قطعات از قبل بر اساس مرتب شده اند.

اسلاید 9: نود شروع، نودی تهی استاشنایی با درخت کوله پشتی به روش عقب گرددر هر دایره عدد بالایی است و عدد وسطی جمع اوزان انتخابی و عدد سوم استprofitbound

اسلاید 10: شرایط امید بخش بودن :امید بخش بودن یک گره یعنی با توجه به مجموعه ی include،بتوانیم شئ دیگری را انتخاب کنیم و ازاین گره عبور کنیم (یعنی امید ملاقات گره های دیگر وجود داشته باشد).weight < wMax profit < bound شرایط انتخاب یک گره به عنوان گره پایانی(یعنی مجموعه ای که انتخاب کرده ایم، بهتر از مجموعه ی bestset است):Weight <= wProfit > max profit

اسلاید 11: Best set :{}Max prcofit : 0Include : {}Profit : 0Weight :0

اسلاید 12: توضیحات برای اسلاید قبل - گره (0,0) را ملاقات می کنیم .- ارزش و وزن آن را محاسبه می کنیم(که برابر است با ارزش و وزن مجموعه ای که فعلا انتخاب کرده ایم (مجموعه include )) ( یعنی ارزش و وزن کل مسیری که منتهی به این گره میشود) :Profit=0 , weight=0مقدار bound (حد) را محاسبه می کنیم:در سطح k=3 داریم : مجموع وزن های انتخابی از سطح i=0 برابر است با: 2+5+10=17 که 17 > W=16

اسلاید 13: Best set{}به گره (1و1) میرسیم و داریم : با انتخاب شئ اول Maxprofit : 0 Include { item 1 } Profit : 40 Weight : 2 Bound :115 Profit > max profit , weight<W best set {item 1} ,Maxprofit=40

اسلاید 14: توضیحات برای اسلاید قبل 3- گره (1,1) را ملاقات می کنیم .ارزش و وزن آن را محاسبه می کنیم : profit=$0+$40=$40 weight=0+2=2مقدار bound (حد) را محاسبه می کنیم:2+5+10=17 17>16 k=3maxprofit= 0

اسلاید 15: Best set : {item1}Max profit: 40Include : {item1,item2}Profit : 70 Weight : 7Bound :115 Profit > max profit , weight<W best set}item1,item2}, Max profit=70

اسلاید 16: توضیحات برای اسلاید قبل4- گره (2,1) را ملاقات می کنیم .ارزش و وزن آن را محاسبه می کنیم : profit=$40+$30=$70 weight=2+5=7مقدار bound (حد) را محاسبه می کنیم:maxprofit= $40

اسلاید 17: Best set : {item1,item2}Max profit: 70Include : {item1,item2,item3}Profit : 120Weight : 17 Profit > max profit , weight<W=16

اسلاید 18: توضیحات برای اسلاید قبل5- گره (3,1) را ملاقات می کنیم .ارزش و وزن آن را محاسبه می کنیم : profit=$70+$50=$120 weight=7+10=17چون 17 از مقدار W یعنی 16 بزرگتر می باشد این گره اصلا نمی تواند اتخاب شود 6- عقبگرد به گره (2,1)maxprofit= $70

اسلاید 19: best set}item1,item2}Max profit : 70Include : {item1,item2}Profit : 70 Bound :80همانطور که ملاحظه می شود چون: لذا گره(2و3) انتخاب نمیشود و در مجموعه اتخابها قرار نمی گیرد ولی این گره شرایط امید بخش بودن را دارد لذا فرزندان این گره را بررسی میکنیمیاداوری شرط انتخاب گره profit > max profit و Weight <=WProfit = max profit

اسلاید 20: توضیحات برای اسلاید قبل7- گره (3,2) را ملاقات می کنیم .ارزش و وزن آن را محاسبه می کنیم : profit=$70 weight=7 نکته مهم :-چون وزن چهارم باعث نمی شود که حاصل جمع قطعات از W بیشتر شود و فقط 4 قطعه وجود دارد بنابراین :k=5 maxprofit= $70

اسلاید 21: best set}item1,item2} وMax profit : 70Include : {item1,item2,item4}Profit : 80 و Bound :80Profit > max profit , weight<W  best set}item1,item2,item4} , Max profit=80پس این گره انتخاب می شود ولی چون profit = bound ، پس امید بخش نیست . به طور شهودی هم این گره اصلا فرزندی ندارد که ما بخواهیم بررسی کنیم لذا این گره غیر امید بخش است.

اسلاید 22: توضیحات برای اسلاید قبل 8- گره (4,1) را ملاقات می کنیم .profit=$80, weight=12bound=$80Bound=maxprofit node is nonpromisingmaxprofit= $70profit > maxprofit maxprofit= $809- گره (4,2) نیز غیر امیدبخش می باشد..

اسلاید 23: best set توضیح مهم همانطور که در اسلایدهای اولیه گفتیم جواب نهایی را وقتی معین می کنیم که جستجو در در خت پایان بپذیرد. در صورتی که ما تا الآن تنها چند مسیر را پیمودیم. در این مسیرها ما به ماکزیمم ارزشی معادل 80$ دست یافته ایم پس به عقب بر میگردیم و مسیرهای دیگر را بررسی میکنیم اگر مسیرهای دیگر ارزشی بیشتر از 80$ به ما داد ، ما مجموعه را آپدیت میکنیم. یعنی مسیری که سود بیشتری به ما میدهد در قرار میگیردلذا به گره (1 و1 )عقب گرد می کنیم..best set

اسلاید 24: به گره (1و1) برمیگردیم و به گره (2و2) می رسیم و داریم :best set}item1,item2,item4}Max profit : 80Include : {item1,item3}Profit : 40 +50= 90Bound :98Profit > max profit , weight<W  best set}item1,item3} , Max profit=90

اسلاید 25: .در این گونه در خت ها تمام مسیرها را از نود شروع تا برگ میرویم به این صورت که ابتدا یک مسیر تا اخر میرویم و بررسی میکنیم سپس نتیجه را ثبت میکنیم سپس پله به پله بر میگردیم عقب و مسیر دیگری را بررسی میکنیم اگر به ارزش بیشتری رسیدیم مجموعه انتخاب بهتر را برمی گزینیم در این درخت جواب نهایی مسیر ابی است ولی ما باید به همین ترتیب گفته شده کل مسیرها را بررسی میکنیم.

اسلاید 26: الگوریتم عقبگرد برای مسئله کوله پشتی صفر و یک

اسلاید 27: الگوریتم عقبگرد برای مسئله کوله پشتی صفر و یک

اسلاید 28: الگوریتم عقبگرد برای مسئله کوله پشتی صفر و یک

اسلاید 29: مقایسه الگوریتم پویا و عقبگرد برای مسئله کوله پشتی صفر و یک زمان اجرای مسئله در بدترین حالت با الگوریتم پویا:O (minimum (2n, nW)). زمان اجرای مسئله در بدترین حالت با الگوریتم عقبگرد:Θ (2n)الگوریتم های عقبگرد در بدترین حالت ،دید خوبی نسبت به کارصرفه جویی شده نمی دهند.هورویتز و شانی در سال 1978با اجرای الگوریتم های عقبگرد و پویا بر روی چندین نمونه نشان دادند که الگوریتم عقبگرد در مقایسه با الگوریتم پویا کارایی بیشتری دارد