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

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

روش حریصانه

روش حریصانه (Greedy) یکی از روش‌های مشهور و پرکاربرد طراحی الگوریتم‌ها است که با ساختاری ساده در حل بسیاری از مسائل استفاده می‌شود. این روش اغلب در حل مسائل بهینه‌سازی استفاده شده و در پاره‌ای مواقع جایگزین مناسبی برای روش‌هایی مانند برنامه‌ریزی پویا است. در حالت کلی این روش سرعت و مرتبه‌ی اجرایی بهتری نسبت به روش‌های مشابه خود دارد؛ اما متناسب با مسأله ممکن است به یک جواب بهینه‌ی سراسری ختم نشود.

در روش حریصانه رسیدن به هدف در هر گام مستقل از گام قبلی و بعدی است. یعنی در هر مرحله برای رسیدن به هدف نهایی، مستقل از این که در مراحل قبلی چه انتخاب‌هایی صورت گرفته و انتخاب فعلی ممکن است چه انتخاب‌هایی در پی داشته باشد، انتخابی که در ظاهر بهترین انتخاب ممکن است صورت می‌پذیرد. به همین دلیل است که به این روش، روش حریصانه گفته می‌شود. زمانی که یک دزد عجول و حریص وارد خانه‌ای می‌شود، در مسیر حرکت خود هر وسیله و کالای با ارزشی را داخل کیسه می‌اندازد. وی در این حالت چندان توجهی نمی‌کند که چه اشیائی را قبلا برداشته و ممکن است در آینده چه اشیاء گرانبهاتری به دست آورد. او در هر گام تنها از بین اشیاء دم دست خود با ارزش‌ترین آن را انتخاب کرده و به وسایل قبلی اضافه می‌کند.

این روش کاربردهای عمومی دیگری نیز دارد. زمانی که در مقابل خرید از یک فروشگاه یک اسکناس تحویل فروشنده داده می‌شود، وی با یک حساب سرانگشتی سعی می‌کند با حداقل اسکناس‌ها و سکه‌های ممکن باقیمانده‌ی پول را تولید کرده و به خریدار تحویل دهد. این حساب سرانگشتی ممکن است روش حریصانه باشد.

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

ساختار روش حریصانه

کلیت روش حریصانه در هر مرحله، انتخاب یک عنصر از عناصر موجود است. این عنصر قسمتی از جواب مسأله است که به مجموعه عناصر نهایی اضافه می‌شود. در طی این مسیر گام‌های زیر اتفاق می‌افتد:

1- روال انتخاب حریصانه: در این گام یک عنصر برای اضافه شدن به مجموعه جواب انتخاب می‌شود. معیار یا روال انتخاب عنصر برای اضافه شدن، ارزش آن عنصر است. بستگی به نوع مسأله هر عنصر ارزشی دارد که با ارزشترین آنها انتخاب می‌شود.

2- امکان‌سنجی و افزودن: پس از انتخاب یک عنصر به صورت حریصانه، باید بررسی شود که آیا امکان اضافه کردن آن به مجموعه جواب‌های قبلی وجود دارد یا نه. گاهی اضافه شدن عنصر یکی از شرایط اولیه‌ی مسأله را نقض می‌کند که باید به آن توجه نمود. اگر اضافه کردن این عنصر هیچ شرطی را نقض نکند، عنصر اضافه خواهد شد؛ وگرنه کنار گذاشته شده و بر اساس گام اول عنصر دیگری برای اضافه شدن انتخاب می‌شود. اگر گزینه‌ی دیگری برای انتخاب وجود نداشته باشد، اجرای الگوریتم به اتمام می‌رسد.

3- بررسی اتمام الگوریتم: در هر مرحله پس از اتمام گام 2 و اضافه شدن یک عنصر جدید به مجموعه جواب، باید بررسی کنیم که آیا به یک جواب مطلوب رسیده‌ایم یا نه؟ اگر نرسیده باشیم به گام اول رفته و چرخه را در مراحل بعدی ادامه می‌دهیم.

به زبان ساده، در روش حریصانه طی هر مرحله یک عنصر به روش حریصانه به مجموعه جواب اضافه شده، شرط محدودیت‌ها بررسی شده و در صورت نبود مشکل، عنصر و عناصر بعدی به همین ترتیب به مجموعه جواب اضافه می‌شوند. در طی این گام‌ها اگر به یک شرط نهایی خاص برسیم، یا امکان انتخاب عنصر دیگری برای اضافه کردن به مجموعه جواب وجود نداشته باشد، الگوریتم پایان یافته و مجموعه جواب به دست آمده به عنوان جواب بهینه ارائه می‌شود. توجه داشته باشید که ممکن است بر اساس نوع مسأله، ترتیب اضافه شدن عناصر به مجموعه جواب اهمیت داشته باشد.

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

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

تعاریف ما به صورت زیر می باشد:

یک بردار وزن به نام W خواهیم داشت که وزن اشیا را در ان وارد میکنیم

یک بردار ارزش به نام V خواهیم داشت که ارزش اشیا را در ان وارد میکنیم

و همچنین یک متغیر W_total داریم که حداکثر وزن قابل قبول را در ان وارد میکنیم

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

برای این کار ابتدا بردار V را بصورت نزولی مرتب میکنیم تا ارزش اشیا از بیشترین شی به کمترین شی مشخص شود. و متناظر با ان بردار W را نیز مرتب میکنیم

حال از ابتدا شی با بیشترین ارزش را در نظر میگیریم ، ان شی را  در کوله پشتی قرار میدهیم به شرطی که مجموع وزن ان و وزن اشیای قبلی داخل کوله پشتی از W_total کمتر باشد.

جهت خرید آنلاین کد متلب و توضیحات حل کوله پشتی با الگوریتم حریصانه از بخش زیر اقدام فرمایید