تشریح مسئله کوله پشتی Knapsak Problem — انواع روش های حل

مسائل بهینه سازی معروفی در حوزه علوم کامپیوتر وجود دارند که هر کدام از اهمیت منحصر به فردی برخوردار بوده و کاربردهای مختلفی نیز دارند. یکی از این مسائل، مسئله کوله پشتی یا Knapsak Problem است که یکی از مسائل معروف در حوزه بهینه سازی و علوم کامپیوتر می‌باشد. در این مقاله سعی بر این خواهیم داشت تا این مسئله را تشریح کنیم و روش های حل آن را بیان خواهیم کرد.

مقدمه

فرض کنید قرار است به دزدی بروید، در این دزدی شما یک کوله دارید که بایستی آن را با اشیاهای قیمتی و در عین حال کم وزن پر کنید؛ چرا که کوله تنها تا وزن خاصی قابلیت تحمل دارد، در این دزدی باید هوشمندانه برخورد کنید و اشیاهایی را بدزدید که سود بیشتری به جیب بزنید!

مسئله Knapsack Problem در انواع مختلفی وجود دارد. این مسئله در واقع به انتخاب بهینه اشیاء با محدودیت‌هایی مانند فضا یا وزن برای قرار دادن در یک کیسه یا کوله می‌پردازد.

مسئله کوله پشتی چیست؟

مسئله کوله پشتی یکی از مشهورترین مسائل بهینه‌سازی در علوم کامپیوتر است که در آن باید با استفاده از یک کوله محدود از ظرفیت و با توجه به وزن و ارزش اشیاء موجود، مقدار بیشینه‌ای از ارزش اشیاء را برای کوله برگزینیم. این مسئله به عنوان یک مسئله بهینه‌سازی ترکیبیاتی مطرح می‌شود و می‌تواند در بسیاری از زمینه‌ها مورد استفاده قرار گیرد.

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

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

تئوری حل مسئله کوله پشتی

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

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

همچنین، این مسئله به صورت یک مسئله بهینه‌سازی ترکیبیاتی دسته‌بندی می‌شود که در آن باید از بین تمام ترکیب‌های ممکن اشیاء، ترکیبی را انتخاب کنیم که ارزش آن بیشینه باشد و به موجب شرایط و محدودیت‌های داده شده، وزن آن در محدوده قرار داشته باشد.

انواع مسائل کوله پشتی کدامند؟

مسئله کوله پشتی در انواع مختلفی وجود دارند، که هر کدام ویژگی‌ها و محدودیت‌های خود را دارند. در زیر به برخی از انواع معروف مسئله Knapsack Problem اشاره خواهیم کرد:

مسئله کوله پشتی ۰-۱

در مسئله کوله پشتی ۰-۱، هر شیء موجود دو حالت دارد: انتخاب شدن یا نشدن. به عبارت دیگر، هر شیء فقط یک بار می‌تواند در کوله (یا knapsack) قرار گیرد، و یا نگیرد. این مسئله به دنبال انتخاب بهینه‌ای از اشیاء با در نظر گرفتن محدودیت‌های وزنی و ارزشی است که کیسه می‌تواند جای دهد. به عبارت دیگر، باید اشیاهایی انتخاب شوند که جمع وزن آن‌ها کمترین میزانی را داشته باشد و به‌طور همزمان ارزش بیشتری نیز داشته باشند.

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

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

مسئله کوله پشتی بدون محدودیت تعداد

در مسئله کوله پشتی بدون محدودیت تعداد، تعداد شیء‌های موجود برای قرار دادن در کیسه محدود نیست و همه‌ی اشیاء برای محاسبه بهینه‌سازی در نظر گرفته می‌شوند. این نوع از مسئله بر اساس محدودیت‌های دیگری مانند وزن یا ارزش، بهینه‌سازی را انجام می‌دهد تا بهترین مجموعه اشیاء برای قرار دادن در کیسه را انتخاب کند. این به ما اجازه می‌دهد تا از تمام اشیاء موجود استفاده کنیم و بهینه‌ترین راه‌حل را برای مسئله Knapsack Problem بدون محدودیت تعداد به دست آوریم.

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

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

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

حل مسئله کوله پشتی با الگوریتم SA در پایتون

کلیک کنید

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

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

• الگوریتم Greedy
• الگوریتم فراابتکاری (Metaheuristic Algorithms)
• الگوریتم برنامه‌ریزی پویا (Dynamic Programming)
• الگوریتم‌های تقریبی (Approximation Algorithms)

حل مسئله کوله پشتی با الگوریتم Greedy

الگوریتم Greedy یک روش ساده و موثر برای حل مسائل بهینه‌سازی است که در بسیاری از مسائل کاربرد دارد. برای حل مسئله کوله پشتی با الگوریتم Greedy، به این صورت عمل می‌کنیم که به ترتیب اشیاء را بر اساس نسبت ارزش به وزن مرتب می‌کنیم و سپس اشیاءی که نسبت ارزش به وزن بیشتری دارند را اولویت می‌دهیم.

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

حل مسئله کوله پشتی با الگوریتم های فراابتکاری

یکی از روش های پرکاربرد در حل مسئله کوله پشتی، استفاده از الگوریتم های فراابتکاری نظیر الگوریتم ژنتیک، الگوریتم PSO، الگوریتم مورچه و حتی الگوریتم های جدید مانند الگوریتم GPC یا ساخت اهرام جیزه می باشد. این روش‌ها مانند الگوریتم ژنتیک و الگوریتم‌های تابعی به دنبال جواب نزدیک به بهینه هستند و معمولاً برای مسائل بزرگ و پیچیده مورد استفاده قرار می‌گیرند.

برای حل مسئله کوله پشتی با استفاده از الگوریتم‌های فراابتکاری، می‌توان از روش‌هایی مانند الگوریتم ژنتیک استفاده کرد. در ادامه به کاربرد الگوریتم ژنتیک در حل مسئله کوله پشتی اشاره می‌کنیم:

• تعریف مجموعه ژن‌ها: ابتدا برای هر شیء موجود در مسئله، یک ژن تعریف می‌کنیم که نشان‌دهنده حضور یا عدم حضور آن شیء در کوله است.
• تولید جمعیت اولیه: یک جمعیت اولیه از رشته‌های ژن‌ها تولید می‌کنیم.
• ارزیابی هر فرد: هر فرد (یا رشته ژنی) در جمعیت بر اساس معیاری مانند ارزش کل شیء‌هایی که در کوله قرار گرفته است، ارزیابی می‌شود.
• انتخاب فردان: از جمعیت، فردانی که بهترین عملکرد را داشته‌اند (با توجه به معیار ارزیابی) انتخاب می‌شوند.
• تولید نسل جدید: از روی فردان انتخاب شده، با استفاده از عملیات مانند ترکیب و جهش، نسل جدیدی ایجاد می‌شود.
• ارزیابی و انتخاب مجدد: همین روند تا رسیدن به یک شرط توقف (مانند تعداد تکرارها یا بهبود نسبت به جواب قبلی) ادامه می‌یابد.

حل مسئله کوله پشتی با الگوریتم ژنتیک GA در متلب

کلیک کنید

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

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

برنامه‌نویسی پویا یکی از روش‌های قدرتمند برای حل مسائل کوله پشتی است. در این روش، از تکنیک‌های بهینه‌سازی استفاده می‌شود تا بهترین مجموعه از اشیاء برای قرار دادن در کوله را با در نظر گرفتن محدودیت‌های وزنی و ارزشی به دست آورد.

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

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

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

استفاده از برنامه‌نویسی پویا برای حل مسئله کوله پشتی به ما امکان می‌دهد تا به جواب بهینه برای مسئله با در نظر گرفتن تمام محدودیت‌ها و شرایط برسیم.

حل مسئله کوله پشتی با الگوریتم PSO در متلب

کلیک کنید

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

فرض کنید که شما یک دزد هستید و در حال دزدی از یک فروشگاه هستید. شما یک کوله با ظرفیت محدود دارید و می‌خواهید اقلامی که بیشترین ارزش را دارند را ببرید، اما کوله شما تنها ظرفیت محدودی دارد.

بیایید فرض کنیم که شما می‌توانید از فروشگاه اقلام زیر را ببرید:

• لپ‌تاپ با ارزش ۱۵۰ وزن ۲
• دوربین با ارزش ۳۰۰ وزن ۴
• کتاب با ارزش ۲۰۰ وزن ۱
• جوراب با ارزش ۵۰ وزن ۱
• کیف پول با ارزش ۷۰ وزن ۱

حالا سوال این است که چگونه می‌توانید اقلامی را که بیشترین ارزش را دارند در کوله خود قرار دهید، در حالی که وزن کوله نباید بیشتر از ۵ واحد باشد؟

حل مسئله با برنامه نویسی پویا در C++

برای حل این مسئله، می‌توان از روش برنامه‌نویسی پویا استفاده کرد. ابتدا جدولی به نام “جدول ارزش‌ها و وزن‌ها” ایجاد می‌کنیم که ارزش و وزن هریک از اقلام را نشان می‌دهد:

سپس یک جدول به نام “جدول بهینه‌سازی” ایجاد می‌کنیم که برای هر وزن ممکن (از ۰ تا وزن کله)، مقدار بهینه ارزش کوله را نگهداری می‌کند. با استفاده از روابط بازگشتی، این جدول را پر می‌کنیم.

حالا با استفاده از مقدار‌های به دست آمده در جدول بهینه‌سازی، می‌توانیم بهترین ارزشی که می‌توانیم با وزن کوله مجاز بدست آوریم را پیدا کنیم. در اینجا، بهترین ارزش برابر با ۳۵۰ است.

حل مسئله کوله پشتی با الگوریتم GPC ساخت اهرام جیزه در متلب

کلیک کنید

سپس با استفاده از مقادیر ذخیره شده در جدول بهینه‌سازی، می‌توانیم اقلامی که برای بهینه‌سازی ارزش کوله انتخاب کرده‌ایم را پیدا کنیم. در اینجا، اقلامی که برای بهینه‌سازی انتخاب شده‌اند عبارتند از: لپ‌تاپ، کتاب و جوراب.

بنابراین، بهترین راه حل برای این مسئله این است که لپ‌تاپ، کتاب و جوراب را در کوله خود قرار دهید که مجموع ارزش آنها بیشترین مقدار ممکن باشد و وزن کوله شما را بیشتر از حد مجاز نکند.

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

#include <iostream>
using namespace std;

int max(int a, int b) {
    return (a > b) ? a : b;
}

int knapsack(int W, int wt[], int val[], int n) {
    int i, w;
    int K[n + 1][W + 1];

    for (i = 0; i <= n; i++) {
        for (w = 0; w <= W; w++) {
            if (i == 0 || w == 0)
                K[i][w] = 0;
            else if (wt[i - 1] <= w)
                K[i][w] = max(val[i - 1] + K[i - 1][w - wt[i - 1]], K[i - 1][w]);
            else
                K[i][w] = K[i - 1][w];
        }
    }

    return K[n][W];
}

int main() {
    int val[] = {150, 300, 200, 50, 70};
    int wt[] = {2, 4, 1, 1, 1};
    int W = 5;
    int n = sizeof(val) / sizeof(val[0]);
    cout << "Maximum value that can be put in a knapsack of capacity " << W << ": " << knapsack(W, wt, val, n);
    return 0;
}

در این کد، تابع max برای مقایسه دو عدد و بازگرداندن بزرگترین آنها استفاده می‌شود.

تابع knapsack مرحله‌ای را انجام می‌دهد که با استفاده از جدولی دوبعدی به نام K، مقدار بهینه‌ی ارزش کوله پشتی با ظرفیت مختلف را محاسبه می‌کند. این تابع پارامترهای ورودی مانند ظرفیت کوله، وزن و ارزش هر اقلام و تعداد اقلام موجود را دریافت می‌کند.

در تابع main، مقادیر وزن و ارزش هر اقلام و ظرفیت مجاز کوله در نظر گرفته شده و تابع knapsack فراخوانی می‌شود. سپس مقدار بهینه‌ی ارزش کوله پشتی برای ظرفیت مشخص محاسبه و نمایش داده می‌شود.

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

حل مسئله کوله پشتی با الگوریتم های تقریبی

این روش‌ها به دنبال جوابی نزدیک به بهینه هستند اما به صورت سریع‌تر و با تضمین‌های کمتری ارائه می‌شوند. این الگوریتم‌ها برای مسائل NP-hard کاربرد دارند.

الگوریتم‌های تقریبی به دلیل سادگی و کارایی بالا، برای مسائل واقعی با حجم بزرگ مورد استفاده قرار می‌گیرند. با این حال، باید توجه داشت که این الگوریتم‌ها ممکن است به جواب‌های زیر‌بهینه منجر شوند و نمی‌توانند بهینه‌ترین راه حل را فراهم کنند. اما با وجود این محدودیت، الگوریتم‌های تقریبی می‌توانند جواب‌های بسیار نزدیک به بهینه را در زمان کوتاهی ارائه دهند.

سورس کد الگوریتم مورچه ACO برای حل مسئله کوله پشتی Knapsack در متلب

کلیک کنید

نتیجه گیری

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

در ادامه، به کاربردهای متعدد مسئله کوله پشتی در صنایع مختلف اشاره کردیم، از جمله مدیریت موجودی، بسته‌بندی، مدیریت منابع فضایی، برنامه‌ریزی مسیر و بسته‌بندی مسائل کاربردی.

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

سورس کدهای آماده حل مسئله کوله پشتی

سورس کدهای آماده حل مسئله کوله پشتی

کلیک کنید