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

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو


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

چیزی که در تمام نسخه های این مسئله مشترک است، وجود مجموعه‌ای با n عضو است، که هر عضو با اندیس j که 1 \leq j \leq n، یک ارزش p_j و وزن w_j دارد. متغیر دودویی تصمیم x_j برای انتخاب کردن اشیا به کار میرود. هدف برداشتن تعدادی از اعضا است، به طوری که ارزش کلشان بیشینه شود و در عین حال بیشینه مجموع وزن اشیا انتخاب‌شده از W تجاوز نکند. در حالت کلی، این ضرایب در عددی ضرب میشوند (مقیاس میشوند) تا به اعداد صحیح تبدیل شوند و همیشه فرض می شود که این ضرایب مثبت هستند.

مسئله کوله‌پشتی در ساده ترین شکل به صورت زیر است:

\sum_{j=1}^n p_j x_j را بیشینه کنید، به طوری‌که \sum_{j=1}^n w_j x_j \leq W، x_j \in \{0,1\}،\forall j \in \{1,\ldots, n\}.

کلی‌سازی مستقیم[ویرایش]

یک شکل رایج این مسئله این است که هر عضو بتواند چندین بار انتخاب شود. مسئله کوله‌پشتی محدود برای هر عضو j ، یک کران بالای u_j (که میتواند یک عدد صحیح مثبت یا بی‌نهایت باشد) که تعداد دفعاتی است که عضو jام انتخاب شده است را مشخص میکند:

\sum_{j=1}^n p_j x_j را بیشینه کنید، به طوری‌که \sum_{j=1}^n w_j x_j \leq W ،  u_j \geq x_j \geq 0 و x_j برای هر j عددی صحیح است.

مسئله کوله‌پشتی نامحدود (که گاهی اوقات مسئله کوله‌پشتی صحیح نیز خوانده میشود) برای تعداد تکرارهای یک عضو کران بالایی قرار نمی‌دهد:

\sum_{j=1}^n p_j x_j را بیشینه کنید، به طوری‌که \sum_{j=1}^n w_j x_j \leq W و  x_j \geq 0 ،  x_j برای هر j عددی صحیح است.

در سال 1975 لوکر ثابت کرد که نوع نامحدود مسئله ان‌پی کامل است.[۱] هر دو نوع محدود و نامحدود این مسئله یک FPTAS دارند (در اصل شبیه به همان است که در مسئله کوله‌پشتی 0-1 استفاده شد).

اگر اعضا در k دسته که با N_i نشان داده میشوند طبقه بندی شوند، و دقیقاً از هر کلاس یک عضو انتخاب شود آنگاه با مسئله کوله‌پشتی چند گزینه ای روبرو هستیم:

\sum_{i=1}^k\sum_{j\in N_i} p_{ij} x_{ij} را بیشینه کنید، به طوری‌که \sum_{i=1}^k\sum_{j\in N_i} w_{ij} x_{ij} \leq W ؛ \sum_{j \in N_i}x_{ij} = 1 ، برای هر 1 \leq i \leq k و  x_{ij} \in \{0,1\}، برای هر1 \leq i \leq k و هر j \in N_i.

اگر برای هر عضو ارزش و وزنش یکسان باشند، با مسئله جمع زیرمجموعه ها روبرو هستیم (اغلب مسئله تصمیم که متناظر با آن است به جای آن داده میشود):

\sum_{j=1}^n p_j x_j را بیشینه کنید، به طوری‌که \sum_{j=1}^n p_j x_j \leq W،  x_j \in \{0,1\}.

اگر n عضو و m کوله‌پشتی با ظرفیت  W_i داشته باشیم،با مسئله کوله‌پشتی چندگانه روبرو هستیم:

\sum_{i=1}^m\sum_{j=1}^n p_j x_{ij} را بیشینه کنید، به طوریکه \sum_{j=1}^n w_j x_{ij} \leq W_i، برای هر 1 \leq i \leq m

و \sum_{i=1}^m x_{ij} \leq 1 ، برای هر 1 \leq j \leq n

و  x_{ij} \in \{0,1\} ، برای هر 1 \leq j \leq n و هر 1 \leq i \leq m.

به عنوان یک حالت خاصِ مسئله کوله‌پشتی چندگانه، هنگامی که ارزش ها با وزن ها برابر و همه صندوق ها حجم برابر داشته باشند، با مسئله حاصل جمع زیرمجموعه‌های چندگانه روبرو هستیم:

مسئله کوله‌پشتی درجه دوم:

\sum_{j=1}^n p_j x_j+\sum_{i=1}^{n-1}\sum_{j=i+1}^n p_{ij} x_i x_j را بیشینه کنید، به طوری‌که \sum_{j=1}^n w_j x_j \leq W،  x_j \in \{0,1\} برای هر 1 \leq j \leq n.

مسئله کوله‌پشتی مجموعه-اجتماع(SUKP):

SUKP توسط Kellerer و همکارانش [۲]( در صفحه 423) همانطور که در ادامه آمده تعریف شده است:

مجموعه N = \{1, \ldots, n\} شامل n عضو و P = \{1, \ldots, m\} شامل m عضو داده شده است، هر عضو j به یک زیرمجموعه P_j از مجموعه P مربوط میشود. برای هرj = 1, \ldots, n ، عضو jام ارزش نامنفی p_j دارد، و برای هر i = 1, \ldots, m ، عضو i ام وزن نامنفی w_i دارد. وزن کلی یک مجموعه از اعضا برابر با مجموع وزن اعضای متناظر آن در مجموعه است. هدف پیدا کردن زیرمجموعه ای از عضوها است که وزن کلی آن از حجم کوله‌پشتی بیشتر نشود و ارزش بیشینه را داشته باشد.

محدودیت چندگانه[ویرایش]

اگر بیشتر از یک محدودیت وجود داشته‌باشد (برای مثال هم محدودیت حجمی و هم محدودیت وزنی داشته‌باشیم، در حالی‌که حجم و وزن هر شی هیچ رابطه‌ای با یکدیگر ندارند)، به مسئله‌ی کوله‌پشتی با شرایط چندگانه، مسئله کوله‌پشتی چند بعدی، یا مسئله کوله‌پشتی m- بعدی می‌رسیم (توجه کنید که "بُعد" در این‌جا هیچ ارتباطی به شکل اشیا ندارد). این مسئله انواع 0-1، محدود و نامحدود دارد که نوع نامحدود آن در زیر نشان داده شده است:

\sum_{j=1}^n p_j x_j را بیشینه کنید، به طوریکه \sum_{j=1}^n w_{ij} x_j \leq W_i ، برای هر 1 \leq i \leq m

x_j \geq 0 ، x_j برای هر  1\leq j \leq n عددی صحیح باشد.

در حدود سال 1980 نشان داده شد که نوع 0-1 مسئله (برای هر m \ge 2 ثابت) ان‌پی کامل است و به طور قویتر FPTAS ندارد مگر اینکه P = NP.[۳][۴]

انواع محدود و نامحدود مسئله نیز (برای هرm \ge 2 ثابت) درجه سختی مشابه دارند.[۵]

برای هر m \ge 2 ثابت، این مسائل یک زمان اجرای شبه چند جمله ای (مشابه مسئله کوله‌پشتی اصلی) و یک PTAS دارند.[۲]

مسئله‌های مشابه کوله‌پشتی[ویرایش]

اگر ارزش همه‌ی اشیا یک باشد می‌توانیم تلاش کنیم تا تعداد اشیایی که کوله‌پشتی را کاملاً پر می‌کنند، کمینه کنیم:

\sum_{j=1}^n x_j را کمینه کنید، به طوریکه \sum_{j=1}^n w_j x_j = W و  x_j \in \{0,1\}،  \forall j \in \{1,\ldots,n\}.

اگر تعدادی جعبه (با سایز یکسان) داشته باشیم و هدف قرار دادن همه‌ی n شی در حداقل تعداد جعبه ممکن باشد به مسلله‌ی bin packing (بسته بندی جعبه ها) می‌رسیم که با متغیرهای شاخص مدل می‌شود و  y_i = 1 است اگر و تنها اگر جعبه‌ی iم استفاده شود:

\sum_{i=1}^n y_i را کمینه کنید، به طوریکه \sum_{j=1}^n w_j x_{ij} \leq Wy_i، \forall i \in \{1,\ldots,n\}

و \sum_{i=1}^n x_{ij} = 1 ، \forall j \in \{1,\ldots,n\}

و  y_i \in \{0,1\} ، \forall i \in \{1,\ldots,n\}

و  x_{ij} \in \{0,1\} ، \forall i \in \{1,\ldots,n\} \wedge \forall j \in \{1,\ldots,n\}.

مسئله‌ی cutting stock مشابه مسئله‌ی bin packing است، اما از آن‌جا که نمونه های عملی انواع کمتری از اعضا دارند، اغلب از فرمول دیگری استفاده می‌شود. عضو jم B_j مرتبه نیاز است، هر الگویی از اعضا که برای یک کوله‌پشتی مناسب باشد یک متغیر x_i دارد(m الگو وجود دارد) و الگوی i عضو j را b_{ij} بار استفاده میکند:

\sum_{i=1}^m x_i را کمینه کنید، به طوریکه \sum_{i=1}^m b_{ij} x_i \leq B_j برای هر 1 \leq j \leq n و x_i \in \{0,1,\ldots ,n\} برای هر 1\leq i \leq m.

اگر برای مسئله کوله‌پشتی چندگزینه‌ای که در آن‌ها چند انتخاب وجود دارد، این محدودیت که در آن سایز هر زیرمجموعه n باشد را اضافه کنیم و محدودیت بر روی وزن کلی را حذف کنیم، به مسئله‌ی assignment می‌رسیم که مسئله‌ی پیدا کردن یک جور سازی دوبخشی بیشینه نیز است:

\sum_{i=1}^k\sum_{j=1}^n p_{ij} x_{ij} را بیشینه کنید، به طوریکه \sum_{i=1}^n x_{ij} = 1 برای هر 1 \leq j \leq n

و \sum_{j=1}^n x_{ij} = 1 برای هر 1 \leq i \leq n

و  x_{ij} \in \{0,1\} برای هر 1 \leq i \leq k و برای هر j \in N_i.

در مسئله کوله‌پشتی با چگالی بیشینه وزن اولیه  W_0 است و ما تراکم اشیای انتخابی را تا زمانی‌که با محدودیت‌های ظرفیت مغایرت نداشته باشد، زیاد می‌کنیم:[۶]

\frac{\sum_{j=1}^n x_j p_j}{w_0 +\sum_{j=1}^n x_j w_j} را بیشینه کنید، به طوریکه \sum_{j=1}^n w_j x_j \leq W و  x_j \in \{0,1\} ،  \forall j \in \{1,\ldots,n\}.

تعداد دیگری مسئله‌های مشابه کوله‌پشتی نیز وجود دارند که البته نسبت به مسئله‌های ذکرشده کمتر متداول هستند، شامل:

  • مسئله کوله‌پشتی تو در تو
  • مسئله کوله‌پشتی سقوط‌کننده
  • مسئله کوله‌پشتی غیرخطی
  • مسئله کوله‌پشتی معکوس پارامتری

سه مسئله‌ی آخر در مرجع کار Kellerer و همکارانش، Knapsack Problems ، مورد بحث و بررسی قرار گرفته‌اند.[۲]

منابع و ماخذ[ویرایش]

  1. Lueker, G.S. (1975). "Two NP-complete problems in nonnegative integer programming". Report No. 178, Computer Science Laboratory, Princeton. 
  2. ۲٫۰ ۲٫۱ ۲٫۲ Kellerer, Hans and Pferschy, Ulrich and Pisinger, David (2004). Knapsack Problems. اشپرینگر ساینس+بیزینس مدیا. ISBN 3-540-40286-1. 
  3. 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. 
  4. "On the Existence of Fast Approximation Schemes". Nonlinear Programming (Academic Press) 4: 415–437. 1980. 
  5. 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. 
  6. Cohen, R. and Katzir, L. 2008. The Generalized Maximum Coverage Problem. Inf. Process. Lett. 108, 1 (Sep. 2008), 15-22.