Printable View
یک شرکت حمل و نقل تعدادی کانتینر برای حمل با کشتی دارد که وزن آنها از ظرفیت کشتی بیشتر است. لذا شرکت مجبور است به میزان ظرفیت موجود در کشتی اقدام به ارسال محموله کند. از طرفی وزن کانتینرها با هم برابر نیست و سود حاصل از هر تن بار برای هر کانتینر متفاوت است.
الگوریتمی ارائه کنید که شرکت بتواند توسط آن کانتینرها را به گونه‌ای انتخاب کند که هم از ظرفیت کشتی نهایت استفاده را کرده باشد و هم از سود بیشتری بهره‌مند شود.
مسئله معروف TP
:lol:نقل قول:
نوشته شده توسط Inprise
حقیقتش مربوط به ادامه بحث تکنیکهای طراحی الگوریتم هست. :wink:
الف) خیلی باحالی :wink: بابا الگوریتم ! :roll: :roll:
ب) TP مسئله کلی و معروفی بود که با ارائه یک گراف وزنی باید فردی رو جهت خرید اجناسی خاص از مسیر های متفاوت و با قیمتهای متفاوت میفرستادیم و مجموع حرکت هم محدودیت خاصی داشت و نتیجه هم میبایست ماکزیمم میبود ! ( جزئیاتش یادم نیست سر صبحی حس سرچ فطیر موجود نیست :lol: )
ج) مهندس جان سری بعد خواستی برای این حقیر از اون چشمک ها بزاری قبلش یه PM بده ... یهو دیدی چشمکه راه نداشته باشه ! :wink:
اینپرایز کم حافظه :cry:
همین مسئله‌ای هست که گفتی و در کل از خانواده Knapsack Problem هستند. این حالت خاص از مسئله که اینجا عنوان شده اسمش Integer Knapsack هست.
Knapsack به معنی کوله‌پشتی هست و دلیل انتخاب این نام برای این مسئله اینه که وقتی ما یک کوله‌پشتی کوچیک داریم٬ باید چیزهایی رو که بیشتر بهشون نیاز داریم توش بگذاریم. از اون طرف هیچوقت هم به عنوان نمونه نمیایم کنسرو لوبیایی رو که قراره تو سفر استفاده کنیم باز کنیم و محتویاتش رو تو کوله پشتی بریزیم که جای کمتری بگیره.
با اینکه Integer Knapsack کاربردهای زیادی داره ولی تا حالا الگوریتمی که تضمین کنه مناسبترین جواب رو براش بدست میاره ارائه نشده و یافتن چنین الگوریتمی هم برای اون بسیار غیر محتمل هست.
با تمام این حرفها٬ این مسئله‌ی به ظاهر ساده برای بحثی که شروع شده یک مسئله مناسب هست.
من هم تمایل دارم ادامه بدیم اما قبلش یک نکته . فکر میکنم جمله بالات با ذهن من قدری ناسازگاره ! :skull: "مناسبترین روش" بقول حضرات امروزی دارای یک قرائت دولتی نیست که بتونیم با مقایسه نتایج یا روند انجام وظیفه یک الگوریتم یا پروسه ، اون رو پائین تر از "مناسبترین" یا دقیقا" خود "مناسبترین" بنامیم . نمیدونم منظورم رو رسوندم یا خیر .نقل قول:
تا حالا الگوریتمی که تضمین کنه مناسبترین جواب رو براش بدست میاره ارائه نشده و یافتن چنین الگوریتمی هم برای اون بسیار غیر محتمل هست.
موفق باشی
چیزی رو که تو جمله از قلم انداختم کارآیی هست.
ولی در هر حال من صحبت از مناسبترین روش نکردم، گفتم مناسبترین جواب.
همانطور که پیشتر گفتم این مسئله از خانواده مسائل کوله پشتی (Knapsack Problems) هست. مسائل کوله پشتی به سه گروه تقسیم می‌شوند:
در مسائل کوله پشتی اندازه مسئله <span dir=ltr>n * Log K</span> است.
- <span dir=ltr>0-1 Knapsack</span>
یک سارق در فروشگاهی تعداد n قلم شئ برای سرقت می‌یابد. هر شئ Iام از این اشیاء دارای وزن <span dir=ltr>C(i)</span> و ارزش <span dir=ltr>V(i)</span> می‌باشد (<span dir=ltr>C(i)</span> و <span dir=ltr>V(i)</span> هر دو عدد صحیح می‌باشند). همچنین سارق حداکثر می‌تواند وزن K (که یک عدد صحیح است) را در کوله پشتی خود حمل کند. این سارق چه اقلامی را انتخاب کند که سود بیشتری حاصل او شود؟ (این مسئله همانند صورت مسئله‌ای است که در اینجا مطرش شد و من آنرا به اشتباه از گروه دیگری از مسائل کوله پشتی به Inprise عزیز معرفی کردم).- Fractional Knapsack
همانند حالت قبل با این تفاوت که هر شی را بتوان به قسمتهای کوچکتر تقسیم کنیم. فرض کنید که سارق به یک جواهر سازی رفته و علاوه بر دیگر جواهرات مقداری گرد طلا و گرد نقره هم در آنجا هست.- Integer Knapsack
این حالت نیز همانند حالت اول است با این تفاوت که از هر قلم از اشیاء به تعداد نامحدود در دسترس است.
مسائل کوله پشتی را می‌توان با هر یک از الگوهای طراحی الگوریتم (Algorithm Paradims) زیر حل کرد:
از بین این روشها٬ روش سیری ناپذیر از زمان اجرای کمتری برخوردار است اما در آن تضمینی برای بدست آوردن بهترین جواب وجود ندارد. مشکل دو روش دیگر نیز زمان اجرای بالای آنها برای مقادیر بزرگ ورودی است.
سلام،
با تشکر فراوان از توضیحات مفید تان اگر امکان داشته باشد در باره ی knapsack و انواع آن اطلاعات ببیشتری در اختیار من قرار دهید.
با تشکر فراوان
با سلام
همون طور که دوستان گفتید شکل دیگری از الگوریتم کوله پشتی صفر و یک هستش چون مجازیم یک کانتینر رو بار کشتی کنیم یا که نکنیم. یعنی مثلا نمیتونیم نصفش رو بار کنیم!
مساله کوله پشتی صفر و یک توسط روش برنامه سازی پویا یا dynamic programming به گونه تقریبا رضایت بخشی حل میشه.
باید اضافه کنم که دو مساله کوله پشتی از نظر من بهترین گزینه برای توصیف تفاوتهای دو روش حریصانه و پویا هستش. کسی که این مسایل ساده رو بفهمه و این که چرا با دو روش حل میشن در حالی که خیلی شبیهند در واقع کل روش حریصانه و پویا و تفاوتهاشونو فهمیده.
در مورد جواب یکی از دوستان باید بگم که مساله کوله پشتی صفر ویک به روش پویا به طور قطع به جواب بهینه میرسه ولی با حریصانه نمیرسه. در حالی که در مورد مساله کوله پشتی کسری با روش حریصانه که روش تقلیل یافته ی پویاست و به زمان و حافظه ی کمتری نیاز داره به جواب بهینه خواهیم رسید و استفاده از روش پویا درست است ولی به صرفه نیست.
در ضمن روش بازگشتی روش حل مساله نیست بلکه دسته ای از روشهاست که با فراخونی مجدد خودشان کار میکنند.
سلام
اگه میشه دوستان در مورد مساله کوله پشتی کسری با روش پویا توضیح بدن. این تمرین درسی من هست.در ضمن اگه الگوریتم یا برنامه ی کامپیوتری اونو در اختیار من بذارید ممنون میشم
از دوستانی که این تاپیک رو میبینند و میتونند کمک کنند خواهشن بدون توجه رد نشید
اگه امکانش هست لطف کنید یک فایل بزارید چون من خیلی جستجو کردم به اندازه کافی توضیحات copy ، paste شده بود
با تشکر
دوستان عزیز
مسایل کوله پشتی (صفر و یک و عدد صحیح)و فروشنده دوره گرد و... در مجموغه مسایل NP_hard مسایل دشوار قرار دارند که الگوریتمی دقیق با زمان چند جمله ای برای آنها وجود ندارد.(مانند روش پویا و شاخه و کران که برای این مسایل جوابی دقیق می دهند ولی زمان آنا چند جمله ای نیست(نیاز به عمر نوح ویا حتی بیشتر برای حل این مسایل بااندازه بزرگ با روش های مذکور دارید) )
از این رو برای حل این مسایل از روش های ابتکاری heuristicو فرا ابتکاری metaheuristic استفاده می شود.مانند روش های حریصانهgreedy و ژنتیک GAو...که جواب شدنی و گاهی تقریبی ارایه می دهند.