موضوع مقاله: مسئله کوله‌پشتی | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # مسئله کوله‌پشتی | مقدمه: مدل‌سازی اندازه و شکل جعبه‌ها، یک مسئله بسته‌بندی است.(راه حل: اگر هر تعداد دلخواهی از جعبه‌ها در دسترس باشد، ۳ جعبهٔ زرد و ۳ جعبهٔ خاکستری پاسخ‌اند. | ## بخش 1: مسئله کوله‌پشتی | اما اگر مانند شکل باشد یعنی از هر جعبه فقط یکی داشته باشیم، همه جعبه‌ها به جز جعبهٔ سبز را انتخاب می‌کنیم) مسئله کوله‌پشتی که با نام‌های Knapsack یا Rucksack مطرح می‌شود مسئله‌ای در بهینه‌سازی ترکیبیاتی است. فرض کنید مجموعه‌ای از اشیا که هر کدام داری وزن و ارزش خاصی هستند در اختیار دارید. به هر شی تعدادی را تخصیص دهید به‌طوری‌که وزن اشیا انتخاب شده کوچکتر یا مساوی حدی از پیش تعیین شده، و ارزش آن‌ها بیشینه شود. علت نامگذاری این مسئله، جهانگردی است که کوله‌پشتی‌ای با اندازهٔ محدود دارد و باید آن را با مفیدترین صورت ممکن از اشیا پر کند. همچنین مسائلی از این قبیل در ترکیبیات، نظریه پیچیدگی محاسباتی، رمزنگاری و ریاضیات کاربردی به چشم می‌خورد. نسخهٔ مسئله تصمیم برای مسئلهٔ کوله‌پشتی، این سؤال است: «آیا ارزش V با انتخاب اشیایی با مجموع وزن کمتر یا مساوی W قابل دستیابی است؟» تعریف فرض کنید که جهانگردی می‌خواهد کوله‌پشتی خود را با انتخاب حالت‌های ممکن از بین وسائل گوناگونی که بیشترین راحتی را برایش فراهم می‌سازند پر کند. این مسئله می‌تواند با شماره‌گذاری این وسائل از ۱ تا n و تعریف برداری از متغیرهای دودویی (Binary) (j = ۱٬۲٬۳…n) به صورت ریاضی فرمول بندی شود. به این معنی که: اگر شیء j ام انتخاب شود در غیر اینصورت وقتی میزان راحتی باشد که وسیله j ا م فراهم می‌آورد و وزن آن و c اندازه کوله‌پشتی باشد. بطوری‌که تابع هدف، بیشترین مقدار خود را بگیرد به عنوان نمونه‌ای از مسائلی که می‌توانند به صورت مسئله کوله‌پشتی فرمول بندی شوند، مسئله زیر را در نظر بگیرید: فرض کنید که شما مایل به سرمایه‌گذاری همه یا قسمتی از سرمایه‌تان باشید. اگر مبلغی که برای سرمایه‌گذاری در نظر گرفتید c دلار باشد و n مورد برای سرمایه‌گذاری ممکن باشد، اجازه دهید که سود حاصل از سرمایه‌گذاری j ام و مقدار دلارهایی باشد که آن سرمایه‌گذاری لازم دارد. بدین ترتیب جواب بهینه مسئله کوله‌پشتی که تعریف کردیم به ما این امکان را می‌دهد که بهترین حالت ممکن را از بین حالت‌های گوناگون سرمایه‌گذاری انتخاب کنیم. یک روش ابتدایی که در نگاه نخست، توجه ما را به خود جلب می‌کند عبارت از برنامه‌نویسی برای رایانه به منظور امتحان کردن همه بردارهای دودویی ممکن x است، تا از بین بردارهایی که محدودیت مسئله را ارضاء می‌کنند بهترین را انتخاب کند. بطوری‌که یک رایانه فرضی که می‌تواند یک بیلیون بردار را در یک ثانیه امتحان کند؛ برای n = ۶۰ بیش از ۳۰ سال وقت لازم دارد و بیش از ۶۰ سال برای n = ۶۱ و ده‌ها سده برای n = ۶۵ والی آخر. با این وجود با استفاده از الگوریتم‌هایی خاص می‌توان در بسیاری موارد مسئله‌ای با n = ۱۰۰ ۰۰۰ را در عرض چند ثانیه روی یک رایانه کوچک حل کرد. برای ساده‌تر شدن نمایش، بدون کم شدن از کلیت مسئله می‌توان فرض کرد اشیا به ترتیب صعودی بر حسب وزنشان مرتب شده‌اند. شناخته‌شده‌ترین نوع از این مسئله مسئلهٔ کوله‌پشتی ۰ و ۱ است؛ یعنی تعداد از هر شی، یا ۰ است (آن شی را انتخاب نمی‌کنیم) یا ۱ (آن شی انتخاب می‌شود). مسئلهٔ کوله‌پشتی ۰ و ۱ را می‌توان به این صورت، به زبان ریاضی بیان کرد: مقدار را بیشینه کنید. به‌طوری‌که مسئلهٔ کوله‌پشتی کران‌دار نسخهٔ دیگری از این سؤال است که در آن تعداد اشیا عددی صحیح و نامنفی و حداکثر برابر با است. به‌طوری که مسئلهٔ کوله‌پشتی بیکران هیچ محدودیتی برای تعداد اشیا ندارد؛ یعنی از هر شی، به هر تعداد دلخواهی می‌توان انتخاب کرد. نسخه‌ای از این سؤال که بیش از همه مورد توجه قرار می‌گیرد، دارای ویژگی‌های زیر است: یک مسئله تصمیم است. دقت کنید که در این مورد خاص، این مسئله هم ارز است با: " مجموعه‌ای از اعداد صحیح نا منفی داده شده است. آیا زیر مجموعه‌ای از آن وجود دارد که جمع اعضایش دقیقاً شود؟" و چنانچه وزن‌های منفی هم قابل قبول باشند، و برابر با در نظر گرفته شود، مسئله عبارت است از: " مجموعه‌ای از اعداد صحیح داده شده است. آیا زیر مجموعه‌ای غیر تهی از آن هست که جمع اعضایش شود؟" این مسئله خاص، مسئله جمع زیرمجموعه‌ها نامیده می‌شود. در رمزنگاری، هر گاه از مسئله کوله‌پشتی نام برده می‌شود، منظور مسئله جمع زیرمجموعه‌ها است. الگوریتمی تقریبی با زمان چندجمله‌ای دارد که از الگوریتم‌های با زمان شبه چندجمله‌ای به عنوان یک زیر-برنامه استفاده می‌کند. حل دقیق این سؤال، مسئله‌ای از نوع NP-complete است؛ بنابراین پیش‌بینی شده که راه حلی که هم درست و هم سریع باشد (با زمان اجرای چندجمله‌ای) برای هر ورودی دلخواه، ندارد. | ## بخش 2: مسئله کوله‌پشتی | مسئله جمع زیر مجموعه‌ها که نسخه‌ای از مسئلهٔ کلی کوله‌پشتی است، به عنوان یکی از ۲۱ مسئله ان‌پی-کامل کارپ مطرح است. تلاش‌هایی برای استفاده از مسئلهٔ جمع زیر مجموعه‌ها به عنوان اصل در سیستم‌های رمزنگاری کلید عمومی، مانند سیستم رمزنگاری کوله‌پشتی مرکل-هلمن انجام شد. راه حل برنامه‌نویسی پویا مسئلهٔ کوله‌پشتی بیکران اگر همه وزن‌ها اعداد صحیح نامنفی باشند مسئلهٔ کوله‌پشتی در زمانی شبه چندجمله‌ای با استفاده از برنامه‌نویسی پویا قابل حل است. می‌خواهیم جمع ارزش کالاهای انتخاب شده را بیشینه کنیم با این فرض که مجموع وزن آن‌ها حداکثر شود. حال برای هر ، مقدار را بیشترین ارزش قابل دستیابی تعریف کنید به‌طوری‌که جمع وزن اشیا انتخاب شده حداکثر شود. دقت کنید که ویژگی‌های زیر را دارد: (جمع اعضای مجموعهٔ تهی ۰ است) که ارزش شی i ام است. بدیهی است با تقسیم کردن بر بزرگ‌ترین مقسوم علیه مشترک می‌توان زمان اجرای الگوریتم را بهینه کرد. مسئلهٔ کوله‌پشتی ۰ و ۱ روش مشابهی با استفاده از برنامه‌سازی پویا برای حل مسئله کوله‌پشتی ۰ و ۱ با پیچیدگی زمانی شبه چندجمله‌ای وجود دارد. را بیشترین ارزش قابل دستیابی، با استفاده از اشیای ۱ تا با حداکثر وزن تعریف کنید. برای کارآمد شدن راه حل، می‌توان از جدولی برای نگهداری نتایج محاسبات قبلی استفاده کرد؛ بنابراین پیچیدگی زمانی آن و حافظه خواهد شد. سپس با حرکت بر روی ، مقدار را با افزودن یک شی جدید به انتخاب‌ها، به روز آوری می‌کنیم. الگوریتم دیگری برای مسئله کوله‌پشتی ۰ و ۱ در سال ۱۹۷۴ ارائه شد که گاهی «رویارویی در میانه» نیز نامیده می‌شود. هنگامی که نسبت به بسیار بزرگتر باشد (یعنی از هم بزرگتر باشد) این الگوریتم نسبت به روش پویا از نظر زمانی بهینه تر است. در اینجا نیز می‌توان از روش پویا استفاده کرد: اگر عددها رقم بعد از اعشار داشته باشند کافی است آن‌ها را در ضرب و سپس رند کرد (با استفاده از محاسبات ممیز ثابت). الگوریتم «رویارویی در میانه» به صورت زیر است: مجموعهٔ را به دو مجموعهٔ و با اندازهٔ نسبتاً برابر تقسیم کنید. برای هر زیرمجموعه از ، بهترین مکمل را از زیر مجموعه‌هایش انتخاب کنید: به عبارتی زیر مجموعه‌ای از با بیشترین جمع ارزش کالاها، به نحوی که جمع وزن‌های دو زیر مجموعه، از بیشتر نشود. این الگوریتم از مرتبهٔ حافظهٔ است و با پیاده‌سازی بهینه گام ۳، از مرتبهٔ زمانی می‌شود. (برای نمونه با مرتب کردن زیرمجموعه‌های بر حسب وزن، چشم پوشی از زیر مجموعه‌هایی از که وزنی بیشتر از سایر زیر مجموعه‌ها با ارزش بزرگتر/مساوی دارند و استفاده از جستجوی دودویی برای یافتن بهترین تطابق). مانند روش رویارویی در میانه در رمز نگاری، استفاده از این الگوریتم با هزینه کردن حافظه (مرتبهٔ نمایی به جای مقدار ثابت) باعث بهینه شدن زمان اجرا می‌شود. می‌دانیم چنانچه بخواهیم همه زیر مجموعه‌های {۱...n} را به روش brute force بررسی کنیم، مرتبهٔ زمانی خواهد شد اما با این الگوریتم آن را بهینه کردیم. الگوریتم تقریبی حریصانه جرج دانتزیگ الگوریتمی تقریبی از نوع حریصانه برای حل مسئله کوله‌پشتی بیکران ارائه داد.George B. 266–288, DOI: به این ترتیب که اشیا را به ترتیب نزولی بر حسب ارزش به واحد وزن مرتب می‌کند سپس از شی شماره ۱ شروع می‌کند. بیشترین تعداد ممکن از آن را در کوله‌پشتی قرار می‌دهد، تا زمانی که دیگر جای خالی‌ای برای آن نوع باقی نماند. (دقت کنید که در این نسخه از سؤال، محدودیتی برای تعداد اشیا نداریم) اگر بیشینه ارزش اشیایی باشد که در کوله‌پشتی جا می‌شوند، این الگوریتم حداقل به مقدار دست می‌یابد. اما اگر تعداد مجاز از هر شی محدود باشد، ممکن است خروجی این الگوریتم از پاسخ بهینه بسیار دور باشد. روابط پوشانندگی در مسئلهٔ کوله‌پشتی بیکران در حل مسئلهٔ کوله‌پشتی بیکران، با کنار گذاشتن اشیایی که هیچ‌وقت مورد استفاده قرار نمی‌گیرند، می‌توان مسئله را ساده‌تر کرد. | ## بخش 3: مسئله کوله‌پشتی | برای نمونه، فرض کنید برای شی‌ای مانند i، می‌توان زیر مجموعه از اشیا به نام J یافت طوری‌که ارزش مجموع آن‌ها بزرگتر از ارزش i و وزن مجموع آن‌ها کمتر از وزن i باشد؛ بنابراین، i نمی‌تواند در جواب بهینه بیاید. (توجه کنید این استدلال برای مسئلهٔ کوله‌پشتی کراندار نمی‌تواند مورد استفاده قرار گیرد؛ زیرا ممکن است قبلاً از اشیا سازندهٔ مجموعهٔ J استفاده کرده باشیم و تمام شده باشند) پیدا کردن روابط پوشانندگی به ما کمک می‌کند تا حجم فضای جستجو را به اندازه چشمگیری کاهش دهیم. (دقت کنید این jها، اعضای مجموعهٔ J هستند) پوشانندگی انتخابی شی ام به‌طور انتخابی توسط پوشانده شده، اگر جمع وزن شماری از اعضای مجموعهٔ ، کمتر از باشد و جمع ارزش آن‌ها بیشتر از . بررسی این نوع پوشانندگی، از لحاظ پیچیدگی محاسباتی چندان ساده نیست، بنابراین از بهترین روش‌ها، راه حل پویاست. در واقع این مسئله، یک مسئله کوله‌پشتی، اما با پارامترهای کوچکتر، مطابق زیر است: ، و اشیا محدود به مجموعهٔ هستند. پوشانندگی حدی اگر شماری از اشیا نوع توسط پوشانده شوند شی ام، تا اندازه‌ای توسط پوشانده می‌شود. این نوع پوشانندگی، نمایش کلی تری از پوشانندگی انتخابی نیست که برای نخستین‌بار در معرفی شد و در الگوریتم EDUK مورد استفاده قرار گرفت. پوشانندگی چندگانه شی ، به‌طور چندگانه توسط شی پوشانده شده، اگر توسط شماری از شی نوع پوشانده شود. (یعنی شی ، فقط توسط تعدادی شی از نوع پوشانده شود و نیازی به استفاده از اشیا دیگر نباشد). این پوشانندگی می‌تواند برای بهینه کردن پروسهٔ حل مورد استفاده قرار گیرد، زیرا تشخیص روابط پوشانندگی از این نوع، به محاسبات زیادی نیاز ندارد و نسبتاً ساده است. شی ام، به‌طور ماژولار توسط شی پوشانده شده، اگر توسط و تعدادی شی از نوع پوشانده شود. (یعنی شی ، فقط توسط و تعدادی شی از نوع پوشانده شود و نیازی به استفاده از اشیا دیگر نباشد) به بیان ریاضی: و که . این مسئله را برای یافتن نخستین جواب بهینه مطرح می‌کنیم مسئله:n کالا داریم که هر کدام از آن‌ها دارای ارزشی و وزنی دارند. 472 یکی از کاربردهای اولیهٔ مسئلهٔ کوله پشتی، طراحی و بارم بندی آزمون است به نحوی که آزمون‌دهنده در پاسخگویی به سؤالات حق انتخاب داشته باشد. برای نمونه، اگر آزمون دارای ۱۲ سؤال، هر سؤال به ارزش ۱۰ نمره باشد، آزمون دهنده باید فقط ۱۰ سؤال را پاسخ دهد تا به بیشینه نمره ممکنِ ۱۰۰ برسد. برای هر دانش آموز، پاسخ‌گویی به کدام زیر مجموعه از سؤالات، نمرهٔ بیشتری را به ارمغان می‌آورد؟ یک نمونه از مسئله کوله پشتی صورت مسئله: دزدی قصد سرقت از مغازه‌ای را دارد و حداکثر وزن w از اجناس را که می‌تواند بدزد در این مغازه n نوع جنس وجود دارد. این مسئله به دو صورت تعریف می‌شود: ۱- صفر و یک در حالت صفر و یک مسئله به این صورت تعریف می‌شود که دزد یا یک جنس را برمی‌دارد یا برنمی‌دارد و حق برداشتن تکه‌ای از یک جنس را ندارد. برای این مسئله راه حل حریصانه‌ای وجود ندارد و به ارائه یک راه حل پویا خواهیم پرداخت. ایده حل این مسئله در حالت پویا یه ابن صورت هست که دزد یا جنس iام را برمی‌دارد یا برنمی‌دارد و براساس این دو حالت سود زیرمسئله ایجاد شده محاسبه می‌شود و از مسیری که جواب بیشینه را داده پیش خواهیم رفت. برای این مسئله راه حال حریصانه وجود داره و به این شکل هست که دزد تا می‌تواند جنس پرارزش تر را برداشته و درصورتی که نتوانست بیشترین کسر ممکن آن را برمی‌دارد. تاریخچه مسئلهٔ کوله پشتی بیش از یک سده مورد مطالعه قرار گرفته و نخستین بررسی در سال ۱۸۹۷ انجام گرفته است. در سال ۱۹۸۸ پژوهشی از دانشگاه استونی بروک بر روی مجموعه‌ای از الگوریتم‌ها نشان داد که از میان ۷۵ مسئلهٔ الگوریتمی، مسئلهٔ کوله پشتی ۱۸امین مسئلهٔ سرشناس و ۴امین مسئلهٔ پرکاربرد پس از درخت کی‌دی، درخت پسوندی، و مسئله بین پکینگ است. برگردان: سید محمد مهدی شهیدی‌پور (۱۳۷۳) ص ۸۸۴–۸۵۶، انتشارات دانشگاه فردوسی مشهد. | ## جمع‌بندی | آشنایی با تحقیق در عملیات، برنامه‌ریزی خطی، پویا و با اعداد صحیح، برگردان: محمد باقر بازرگان (۱۳۷۷) ص.