فهرست مسائل کولهپشتی
مسئله کولهپشتی، یکی از مسائل مورد مطالعه در بهینه سازی ترکیبیاتی است که در بعضی موارد در زندگی واقعی نیز کاربرد دارد. به همین دلیل تعدادی از حالات خاص یا حالات کلی آن مورد آزمایش قرار گرفتهاست.
چیزی که در تمام نسخههای این مسئله مشترک است، وجود مجموعهای با n عضو است، که هر عضو با اندیس j که
مسئله کولهپشتی در سادهترین شکل به صورت زیر است:
کلیسازی مستقیم
یک شکل رایج این مسئله این است که هر عضو بتواند چندین بار انتخاب شود. مسئله کولهپشتی محدود برای هر عضو
مسئله کولهپشتی نامحدود (که گاهی اوقات مسئله کولهپشتی صحیح نیز خوانده میشود) برای تعداد تکرارهای یک عضو کران بالایی قرار نمیدهد:
در سال 1975 لوکر ثابت کرد که نوع نامحدود مسئله انپی کامل است. هر دو نوع محدود و نامحدود این مسئله یک FPTAS دارند (در اصل شبیه به همان است که در مسئله کولهپشتی 0-1 استفاده شد).
اگر اعضا در k دسته که با
اگر برای هر عضو ارزش و وزنش یکسان باشند، با مسئله جمع زیرمجموعه ها روبرو هستیم (اغلب مسئله تصمیم که متناظر با آن است به جای آن داده میشود):
اگر n عضو و m کولهپشتی با ظرفیت
و
و
به عنوان یک حالت خاصِ مسئله کولهپشتی چندگانه، هنگامی که ارزشها با وزنها برابر و همه صندوقها حجم برابر داشته باشند، با مسئله حاصل جمع زیرمجموعههای چندگانه روبرو هستیم:
مسئله کولهپشتی درجه دوم:
مسئله کولهپشتی مجموعه-اجتماع(SUKP):
SUKP توسط Kellerer و همکارانش ( در صفحه 423) همانطور که در ادامه آمده تعریف شدهاست:
مجموعه
شاملعضو وشاملعضو داده شده است، هر عضوبه یک زیرمجموعهاز مجموعهمربوط میشود. برای هر، عضوام ارزش نامنفیدارد، و برای هر، عضوام وزن نامنفیدارد. وزن کلی یک مجموعه از اعضا برابر با مجموع وزن اعضای متناظر آن در مجموعه است. هدف پیدا کردن زیرمجموعه ای از عضوها است که وزن کلی آن از حجم کولهپشتی بیشتر نشود و ارزش بیشینه را داشته باشد.
محدودیت چندگانه
اگر بیشتر از یک محدودیت وجود داشتهباشد (برای مثال هم محدودیت حجمی و هم محدودیت وزنی داشتهباشیم، در حالیکه حجم و وزن هر شی هیچ رابطهای با یکدیگر ندارند)، به مسئلهٔ کولهپشتی با شرایط چندگانه، مسئله کولهپشتی چند بعدی، یا مسئله کولهپشتی m- بعدی میرسیم (توجه کنید که "بُعد" در اینجا هیچ ارتباطی به شکل اشیا ندارد). این مسئله انواع 0-1، محدود و نامحدود دارد که نوع نامحدود آن در زیر نشان داده شدهاست:
در حدود سال 1980 نشان داده شد که نوع 0-1 مسئله (برای هر
انواع محدود و نامحدود مسئله نیز (برای هر
برای هر
مسئلههای مشابه کولهپشتی
اگر ارزش همهٔ اشیا یک باشد میتوانیم تلاش کنیم تا تعداد اشیایی که کولهپشتی را کاملاً پر میکنند، کمینه کنیم:
اگر تعدادی جعبه (با سایز یکسان) داشته باشیم و هدف قرار دادن همهٔ n شی در حداقل تعداد جعبه ممکن باشد به مسللهٔ bin packing (بسته بندی جعبه ها) میرسیم که با متغیرهای شاخص مدل میشود و
و
و
و
مسئلهٔ cutting stock مشابه مسئلهٔ bin packing است، اما از آنجا که نمونههای عملی انواع کمتری از اعضا دارند، اغلب از فرمول دیگری استفاده میشود. عضو jم
اگر برای مسئله کولهپشتی چندگزینهای که در آنها چند انتخاب وجود دارد، این محدودیت که در آن سایز هر زیرمجموعه n باشد را اضافه کنیم و محدودیت بر روی وزن کلی را حذف کنیم، به مسئلهٔ assignment میرسیم که مسئلهٔ پیدا کردن یک جور سازی دوبخشی بیشینه نیز است:
و
و
در مسئله کولهپشتی با چگالی بیشینه وزن اولیه
تعداد دیگری مسئلههای مشابه کولهپشتی نیز وجود دارند که البته نسبت به مسئلههای ذکرشده کمتر متداول هستند، شامل:
- مسئله کولهپشتی تو در تو
- مسئله کولهپشتی سقوطکننده
- مسئله کولهپشتی غیرخطی
- مسئله کولهپشتی معکوس پارامتری
سه مسئلهٔ آخر در مرجع کار Kellerer و همکارانش، Knapsack Problems، مورد بحث و بررسی قرار گرفتهاند.
منابع و ماخذ
- ↑ Lueker, G.S. (1975). "Report No. 178, Computer Science Laboratory, Princeton". ;
- ↑ Kellerer, Hans and Pferschy, Ulrich and Pisinger, David (2004). Knapsack Problems. اشپرینگر ساینس+بیزینس مدیا. ISBN 3-540-40286-1.
- ↑ Gens, G. V. and Levner, E. V. (1979). "Complexity and Approximation Algorithms for Combinatorial Problems: A Survey". Central Economic and Mathematical Institute, Academy of Sciences of the USSR, Moscow.
- ↑ "On the Existence of Fast Approximation Schemes". Nonlinear Programming. Academic Press. 4: 415–437. 1980.
- ↑ Magazine, M. J.; Chern, M.-S. (1984). "A Note on Approximation Schemes for Multidimensional Knapsack Problems". Mathematics of Operations Research. 9 (2): 244–247. doi:10.1287/moor.9.2.244.
- ↑ Cohen, R. and Katzir, L. 2008. The Generalized Maximum Coverage Problem. Inf. Process. Lett. 108, 1 (Sep. 2008), 15-22.
- "Algorithms for Knapsack Problems", D. Pisinger. Ph.D. thesis, DIKU, University of Copenhagen, Report 95/1 (1995).