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

برای دیگر کاربردها، کوله‌پشتی را ببینید.

Example of a one-dimensional (constraint) knapsack problem: which boxes should be chosen to maximize the amount of money while still keeping the overall weight under or equal to 15 kg? A multiple constrained problem could consider both the weight and volume of the boxes. Modeling the shapes and sizes would instead constitute a packing problem.
(Solution: if any number of each box is available, then three yellow boxes and three grey boxes; if only the shown boxes are available, then all but the green box.)

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

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

نسخه ی مسئله تصمیم برای مسئله ی کوله پشتی، این سوال است: "آیا ارزش V بدون فرارفتن از وزن W، قابل دستیابی است؟"

تعریف

فرض کنید $n$ جسم داریم که از $1$ تا $n$ شماره گذاری شده اند. جسم $i$ ام ارزشی معادل $v_{i}$و وزنی برابر با $w_{i}$ دارد. معمولا فرض می شود که وزن ها و ارزش ها نامنفی اند. برای ساده تر شدن نمایش، بدون کم شدن از کلیت مسئله می توان فرض کرد اشیا به ترتیب صعودی بر حسب وزنشان مرتب شده اند. بیشترین وزنی که می توان در کوله پشتی حمل کرد،$W$ است.

معروف ترین نوع از این مسئله، مسئله ی کوله پشتی 0 و 1 است. یعنی تعداد از هر شی، یا 0 است (آن شی را انتخاب نمی کنیم) یا 1 ( آن شی انتخاب می شود). مسئله ی کوله پشتی 0 و 1 را می توان به این صورت، به زبان ریاضی بیان کرد:

• مقدار $\qquad \sum _{i=1}^{n}v_{i}x_{i}$ را بیشینه کنید.
• به طوری که $\qquad \sum _{i=1}^{n}w_{i}x_{i}\leqslant W,\quad x_{i}\in \{0,1\}$

مسئله ی کوله پشتی کران دار، نسخه ی دیگری از این سوال است که در آن تعداد اشیا ($x_{i}$) عددی صحیح و نامنفی و حد اکثر برابر با$c_{i}$ است. به بیان ریاضی:

• مقدار $\qquad \sum _{i=1}^{n}v_{i}x_{i}$را بیشینه کنید.
• به طوری که$\qquad \sum _{i=1}^{n}w_{i}x_{i}\leqslant W,\quad x_{i}\in \{0,1,\ldots ,c_{i}\}$

مسئله ی کوله پشتی بیکران (UKP) ، هیچ محدودیتی روی تعداد اشیا قائل نمی شود. یعنی از هر شی، به هر تعداد دلخواهی می توان انتخاب کرد. نسخه ای ازین سوال که بیش از همه مورد توجه قرار میگیرد، دارای ویژگی های زیر است:

• یک مسئله تصمیم است.
• مسئله 0 و 1 است.
• برای هر شی، وزن و ارزش آن برابرند. یعنی$w_{i}=v_{i}$ .

دقت کنید که در این مورد خاص، این مسئله هم ارز است با: " مجموعه ای از اعداد صحیح نا منفی داده شده است. آیا زیر مجموعه ای از آن وجود دارد که جمع اعضایش دقیقا $W$ شود؟" و چنانچه وزن های منفی هم قابل قبول باشند، و $W$ برابر با $0$ در نظر گرفته شود، مسئله عبارت است از: " مجموعه ای از اعداد صحیح داده شده است. آیا زیر مجموعه ای غیر تهی از آن هست که جمع اعضایش $0$ شود؟" این مسئله خاص، مسئله جمع زیرمجموعه ها نامیده می شود. در رمزنگاری، هر گاه از مسئله کوله پشتی نام برده می شود، منظور مسئله جمع زیرمجموعه ها است.

چنانچه چند کوله پشتی داشته باشیم، مسئله تبدیل به سوال bin packing می شود.

پیچیدگی محاسباتی

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

• الگوریتمی با زمان اجرای شبه چند جمله ای با استفاده از برنامه نویسی پویا دارد.
• الگوریتمی تقریبی با زمان چند جمله ای دارد که از الگوریتم های با زمان شبه چند جمله ای به عنوان یک زیر-برنامه استفاده می کند.
• حل دقیق این سوال، مسئله ای از نوع NP-complete است. بنابراین پیش بینی شده که راه حلی که هم درست و هم سریع باشد( با زمان اجرای چند جمله ای) برای هر ورودی دلخواه، ندارد.

مسئله جمع زیر مجموعه ها که نسخه ای از مسئله ی کلی کوله پشتی است، به عنوان یکی از 21 مسئله ی NP-کامل ِ Karp مطرح است.

تلاش هایی برای استفاده از مسئله ی جمع زیر مجموعه ها به عنوان اصل در سیستم های رمزنگاری کلید عمومی، مانند رمزنگاری کولی پشتی ِ Merkle-Hellman انجام شد. در این روش ها، معمولا از گروه هایی به جز اعداد صحیح استفاده می شد. Merkle-Hellman و الگوریتم های مشابه دیگر بعدا با شکست روبرو شدند، زیرا مسائل خاصی که تولید می کردند در زمان چند جمله ای قابل حل بودند.

در خیلی از تحقیقات سعی می شود به این سوال پاسخ داده شود که نمونه های سخت مسئله ی کوله پشتی چه هستند؟ یا از دید دیگر، چه ویژگی هایی از مثال های مسئله ی کوله پشتی، باعث می شود در زمانی معقولتر نسبت به آن چه در صورت کلی NP-completeِ سوال مطرح است، حل شوند. . الگوریتم های زیادی بر پایه ی: برنامه نویسی پویا, روش تقسیم و حد، یا ترکیبی از هر دو روش برای این مسئله وجود دارند.

راه حل برنامه نویسی پویا

مسئله ی کوله پشتی بیکران

اگر تمام وزن ها ($w_{1},\ldots ,w_{n},W$ ) اعداد صحیح نامنفی باشند، مسئله ی کوله پشتی در در زمانی شبه چند جمله ای با استفاده از برنامه نویسی پویا قابل حل است.

برای سادگی فرض کنید تمام وزن ها اکیدا مثبت اند ($w_{i}>0$ ). می خواهیم جمع ارزش کالاهای انتخاب شده را بیشینه کنیم با این فرض که مجموع وزن آنها حداکثر$W$ شود. حال برای هر $w<W$ ،مقدار $m[w]$ را بیشترین ارزش قابل دستیابی تعریف کنید به طوری که جمع وزن اشیا انتخاب شده حد اکثر $w$ شود. بدیهی است که $m[W]$ پاسخ مورد نظر است.

دقت کنید که $m[w]$ ویژگی های زیر را دارد:

• $m[0]=0\,\!$ (جمع اعضای مجموعه ی تهی 0 است)
• $m[w]=\max _{w_{i}\leq w}(v_{i}+m[w-w_{i}])$ که $v_{i}$ ارزش شی ام iاست.

بیشترین ارزش قابل دستیابی از مجموعه ی تهی، 0 است. برای محاسبه ی هر کدام از $m[w]$ ها، باید $n$ شی را بررسی کرد. همچنین آرایه ی $W$، $m$ عنصر دارد. بنابر این زمان اجرای این الگوریتم $O(nW)$ است. بدیهی است با تقسیم کردن $w_{1},\,w_{2},\,\ldots ,\,w_{n},\,W$ بر بزرگترین مقسوم علیه مشترک شان، می توان زمان اجرای الگوریتم را بهینه کرد.

پیچیدگی زمانی $O(nW)$ تناقضی با NP-complete بودن مسئله ی کوله پشتی ندارد. زیرا $W$ برخلاف $n$، برحسب ورودی چند جمله ای نیست. طول $W$ ِ ورودی، متناسب با تعداد بیت های لازم برای نمایش $W$، یعنی $\log W$ است، نه خود $W$.

روابط Dominance در UKP

4 مورد

تاریخچه

مسئله ی کوله پشتی بیش از یک قرن مورد مطالعه قرار گرفته و اولین بررسی در سال 1897 انجام گرفته است. هر چند اولین داده های ثبت شده در این مورد، به کارهای ریاضیدانی به نام (1884–1956) Tobias Dantzig برمی گردد، چیزی با عنوان مسئله ی کوله پشتی قبلا در میان عامه ی مردم وجود داشته است. مسئله ی کوله پشتی درجه دوم، اولین بار توسط Hammer ، Gallo و Simeone در سال 1960 مطرح شد. در سال 1988، تحقیقی از دانشگاه استونی بروک بر روی مجموعه ای از الگوریتم ها، نشان داد که از میان 75 مسئله ی الگوریتمی، مسئله ی کوله پشتی، 18 امین مسئله ی معروف و 4 امین مسئله ی پرکاربرد بعد از درخت کی دی ، درخت پیشوندی و bin packing problem است.

برای مطالعه

• لیست مسائل کوله پشتی
• مسئله فشرده سازی
• مسئله برش کالا
• مسئله کوله پشتی پیوسته

منابع

• Garey, Michael R. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman. ISBN 0-7167-1045-5. {{cite book}}: Unknown parameter |coauthors= ignored (|author= suggested) (help) A6: MP9, pg.247.
• Kellerer, Hans; Pferschy, Ulrich; Pisinger, David (2004). Knapsack Problems. Springer. ISBN 3-540-40286-1. {{cite book}}: Unknown parameter |:en:mr= ignored (help)نگهداری یادکرد:نام‌های متعدد:فهرست نویسندگان (link)
• Martello, Silvano; Toth, Paolo (1990). Knapsack problems: Algorithms and computer interpretations. Wiley-Interscience. ISBN 0-471-92420-2. {{cite book}}: Unknown parameter |:en:mr= ignored (help)

پیوند های بیرونی

• Lecture slides on the knapsack problem
• PYAsUKP: Yet Another solver for the Unbounded Knapsack Problem, with code taking advantage of the dominance relations in an hybride algorithm, benchmarks and downloadable copies of some papers.
• Home page of David Pisinger with downloadable copies of some papers on the publication list (including "Where are the hard knapsack problems?")
• [ http://www.rosettacode.org/wiki/Knapsack_Problem Knapsack Problem solutions in many languages] at Rosetta Code
• Dynamic Programming algorithm to 0/1 Knapsack problem
• 0-1 Knapsack Problem in Python
• Interactive JavaScript branch-and-bound solver
• Solving 0-1-KNAPSACK with Genetic Algorithms in Ruby

توسط Asma.ghandeharioun (بحث) در حال به روز آوری است.