حل مساله کوله پشتی با رویکرد حریصانه

حل مساله کوله پشتی با رویکرد حریصانه

اسلاید 1: اهداف درس این جلسهحل مساله کوله پشتی با رویکرد حریصانهمقایسه رویکرد حریصانه با برنامه‌نویسی پویا در حل مساله

اسلاید 2: که wi و pi و W همگی اعداد مثبتی هستند. می‌خواهیم زیر مجموعه A از S را به گونه‌ای مشخص کنیم که ...3یادآوری مسئله کوله‌پشتی صفر و یک

اسلاید 3: ه) الگوریتم حریصانه در مسئله کوله پشتی صفر و یکاگر بخواهیم رویکرد brute-force را درنظر بگیریم ...باید تمامی زیرمجموعه‌های S را درنظر بگیریم و ...از اونهایی که مجموع وزنشون از W بیشتر است صرفنظر کنیم و ...از زیرمجموعه‌های باقیمانده اونی که بیشترین مجموع منفعت دارد را به عنوان پاسخ انتخاب کنیم.پیچیدگی محاسباتی این روش بادرنظر گرفتن n آیتم ....2n می‌باشد4

اسلاید 4: ه) الگوریتم حریصانه در مسئله کوله پشتی صفر و یکاولین راه حل حریصانه که شاید برای این مساله به ذهن برسد آن است که ...تمامی آیتم‌ها را بر اساس منفعتشان به صورت نزولی مرتب کنیم و ...به ترتیب آیتم‌ها را از مجموعه مرتب‌شده برداریم مادامیکه ...مجموع وزنشان از W بیشتر نشود.این استراتژی زمانیکه آیتم‌های با منفعت بالا وزن بیشتری در مقایسه با منفعتشون دارند مناسب نمی‌باشد.5

اسلاید 5: ه) الگوریتم حریصانه در مسئله کوله پشتی صفر و یکاحتمالا استراتژی بعدی این می‌تواند باشد که آیتم‌های سبک‌تر را ابتدا برداریم ...این استراتژی هم زمانی که آیتم‌های سبک منفعت کمی داشته باشند به شکست می‌انجامد.6

اسلاید 6: ه) الگوریتم حریصانه در مسئله کوله پشتی صفر و یکراه حل حریصانه مناسب این است که ...آیتم‌ها را بر اساس منفعت واحد وزنشان به صورت نزولی مرتب کنیم و ...آیتم‌ها را تا زمانیکه مجموع وزنشان از W بیشتر نشود برداریم.7

اسلاید 7: ه) الگوریتم حریصانه در مسئله کوله پشتی صفر و یک8

اسلاید 8: ه) الگوریتم حریصانه در مسئله کوله پشتی کسری (Fractional) در مساله کوله‌پشتی کسری چنانچه برداشتن کل آیتم میسر نیست، می‌توان بخشی از آن را نیز برداشت.مثلا در مثال قبل ...بنابراین هیچ فضایی هدر نمی‌رود. پس همواره حل بهینه را خواهیم داشت.9

اسلاید 9: ه) برنامه‌نویسی پویا در مسئله کوله پشتی صفر و یکچنانچه بتوانیم ...اصل بهینگی را در مساله کوله‌پشتی صفر و یک نشان دهیم ...بنابراین می‌توانیم آن را با برنامه‌نویسی پویا حل کنیم.10

اسلاید 10: یادآوری اصل بهینگی (Principle of Optimality)تعریف: مساله‌ای شرایط اصل بهینگی را داردچنانچه در آن مساله ...زیر راه‌حل‌های یک راه‌‌حل بهینه برای هر نمونه مساله‌ ...خودشان راه‌حل‌های بهینه برای زیرمسائلی متناظر باشند.11ه) برنامه‌نویسی پویا در مسئله کوله پشتی صفر و یک

اسلاید 11: ه) برنامه‌نویسی پویا در مسئله کوله پشتی صفر و یکفرض کنیم که A، زیرمجموعه بهینه شامل n آیتم باشد ...باید نشان دهیم زیر راه‌حل‌های بهینه این راه حل بهینه خود حل‌های بهینه برای زیر مسائل متناظرشان هستند. در اینجا دو امکان وجود دارد ...یا A شامل itemn است یا نیست.12

اسلاید 12: ه) برنامه‌نویسی پویا در مسئله کوله پشتی صفر و یکاگر A شامل itemn نباشد، بنابراین ...A دربرگیرنده پاسخ بهینه (زیر راه حل) برای n-1 آیتم (زیر مساله) می‌باشد.اگر A شامل itemn باشد ...بنابراین مجموع منفعت‌های بدست آمده در A برابر است با pn به اضافه ...منفعت بهینه بدست آمده از انتخاب n-1 آیتم اول ...البته با این محدودیت که ...مجموع وزن n-1 آیتم اول از ...W-wn بیشتر نشود.پس اصل بهینگی برقرار است13

اسلاید 13: ه) برنامه‌نویسی پویا در مسئله کوله پشتی صفر و یکبرای حل مساله با رویکرد برنامه ‌نویسی پویا همانند گذشته باید ...ویژگی بازگشتی تعریف کنیم که حل مساله از پایین به بالا ایجاد شود. یعنی ...ابتدا راه حل بهینه برای زمانیکه که A دارای 1 آیتم، سپس A دارای ...2 آیتم، سپس دارای 3 آیتم و ... در نهایت A دارای n آیتم باشد.14

اسلاید 14: ه) برنامه‌نویسی پویا در مسئله کوله پشتی صفر و یکماتریس P را درنظر می‌گیریم که P[i][w] برابر است با ...منفعت بهینه زمانی باشد که ...i آیتم ابتدایی با این شرط که مجموع وزنشان از w تجاوز نکند.توجه: آیتم‌های لیست بر اساس نسبت منفعت به وزن مرتب شده‌اند.پاسخ نهایی ...P[n][W] می‌باشد.15

اسلاید 15: ه) برنامه‌نویسی پویا در مسئله کوله پشتی صفر و یکبنابراین ماتریس P باید دارای سطرهایی با اندیس 0 تا n باشد. همچنین ...باید دارای ستون‌هایی با اندیس 0 تا W باشد تا ...بر اساس رابطه بازگشتی تعریف شده، المان‌های ماتریس را محاسبه کنیم تا در نهایت ...P[n][W] محاسبه شود.مقادیر P[0][w] و P[i][0] پیش‌فرض برابر 0 قرارداده می‌شود.16

اسلاید 16: ه) روش بهبود‌یافته برنامه‌نویسی پویا در مسئله کوله پشتی صفر و یکبا این روش حل، پیچیدگی محاسباتی هم به n و هم به ...W بستگی دارد. اگر مجبور باشیم تمامی المان‌های ماتریس را محاسه کنیم در این صورت باید …nW محاسبه انجام دهیم که روش ما داری مرتبه پیچیدگی محاسباتی Θ(nW) خواهد بود که ...به W وابسته است که اگر W مقادیر بزرگ مثلا n! داشته باشد در این صورت ...مثلا برای n=20، اجرای الگوریتم سال‌ها به طول خواهد کشید. در این حالت ...این الگوریتم از الگوریتم brute force که دارای پیچیدگی ...2n بود بدتر می‌باشد.17

اسلاید 17: ه) روش بهبود‌یافته برنامه‌نویسی پویا در مسئله کوله پشتی صفر و یکالگوریتم را می‌توانیم به گونه‌ای تغییر دهیم که پیچیدگی محاسبات کاهش یابد.چگونه؟این واقعیت وجود دارد که نیازی نیست که مثلا در سطر i، مقادیر تمامی ستون‌ها از 1 تا W محاسبه شود.مثلا تنها المان‌هایی که نیاز است در سطر n-1 ام محاسبه شود ...18

اسلاید 18: ه) روش بهبود‌یافته برنامه‌نویسی پویا در مسئله کوله پشتی صفر و یکبنابراین تعداد المان‌هایی از ماتریس که نیاز است محاسبه شود برابر می‌شود با ...19