IDS: Intrusion Detection System

مسائله کوله پشتی Knapsack Problem (KP)

مسائله کوله پشتی  Knapsack Problem (KP)

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

مسائله کوله پشتی یک نمونه از مسائل بهینه سازی ترکیبی است (combinatorial optimization problem) که در آن بهترین راه حل از میان راه حل‌های دیگر جستجو می شود. در این مسائله یک کوله پشتی که دارای اندازه صحیح مثبت(یا ظرفیت ) است وجود دارد که این ظرفیت با V نشان داده می شود.تعداد n آیتم متفاوت که بطور بالقوه ممکن است در کوله پشتی قرار داده شوند نیز وجود دارد.آیتم I دارای یک اندازه صحیح (ظرفیت) است که با VI  نشان داده می‌شود و  یک عدد صحیح BI که نشان دهنده منفعت ( ارزش) این آیتم است.علاوه بر این‌ها QI کپی از آیتم I در دسترس می باشد.که مقدار QI یک عدد صحیح است که شرط زیر را مهیا نماید
1 ≤ Q i ≤ ∞

اجازه بدهید که XI معین نماید که چه تعداد کپی های آیتم I قرار است در کوله پشتی قرار گیرند و هدف ما به صورت زیر تعریف می‌شود که حاصل عبارت زیر را پیشینه نماییم :(قرار دادن بیشترین آیتم با بیشترین ارزش در کوله پشتی)

با این شرط که آیتم های قرار گرفته از ظرفیت کوله پشتی بیشتر نباشند :

و همچنین شرط زیر نیز صادق باشد :
1 ≤ X i ≤ Q i
اگر یکی یا چند تا از Qi بی نهایت باشند ( نامتنهای) مسائله کوله پشتی را بدون کران می نامند در غیر این صورت مسائله کوله پشتی کراندار خواهد بود.مسائله کوله پشتی کراندار می‌تواند کوله پشتی 1-0 باشد ( 0-1 knapsack) و یا چند محدودیتی .اگر مقدار Qi برابر با ۱ باشد آنگاه با یک مسائله کوله پشتی از نوع 0-1 روبه رو هستیم. در این خاص از مسائله کوله پشتی (0-1) ما نمی‌توانیم بیشتر از یک کپی از یک آیم در کوله پشتی داشته باشیم.
یک مثال برای مسائله کوله پشتی 0-1
فرض کنیم که کوله پشتی در اختیار داریم که ظرفیت آن ۱۳ اینچ مکعبت است و چندین آیتم با سایزها و ارزش‌های مختلف در ختیار داریم.می می‌خواهیم در کوله پشتی تنها آیتم هایی را داشته باشیم که در مجموع دارای یبشترین ارزش باشند با این محدودیت که مجموع ظرفیت آن‌ها از ظرفیت کوله پشتی بیشتر نشود .برای مثال ما سه آیتم وجود دارد که با حروف A,B,C برچست خورده اند.که در جدول زیر ظرفیتها (حجم) و ارزش‌های آن‌ها را مشاهده می کنید :

آیتمABC
ارزش Benefit435
ظرفیت Volume678

ما به دنبال این هستیم که مقدار ارزش‌های آیتم ها را بیشینه نماییم:

البته با رعایت شرایط زیر :


برای مسائله ما 23 زیر مجموعه از آیتم ها وجود دارد که ترکیبی همگی در ذیل آورده شده است :

ارزش مجموعهظرفیت مجموعهCBA
00000
58100
37010
-15110
46001
-14101
713011
-21111

برای بدست آوردن بهترین راه حل مجبور هستیم که زیر مجموعه‌ای از آیتم ها که محدودیت‌های مورد نظر را دارا می‌باشند و جمع ارزش‌های آن‌ها بیشینه است را معین کنیم.در مثال ما تنها سطری که بصورت پر‌رنگ در آمده است شروط مورد نظر را فراهم می کند.بنا براین ارزش بهینه برای محدودیت مورد نظر ما ( V=13) تنها می‌تواند با یک مقدار از A ، یک مدقار از B و هیچ مقدار از C امکان‌پذیر خواهد بود که این مقدار نیز 7 بدست آمد.
نظرات (0)
نام :
ایمیل : [پنهان میماند]
وب/وبلاگ :
برای نمایش آواتار خود در این وبلاگ در سایت Gravatar.com ثبت نام کنید. (راهنما)