در تعیین حد سود حریص نباشید

معرفی

این هفته ما همچنان به روش حریص حل مشکلات خواهیم پرداخت.

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

مباحث اصلی این هفته:

همان نوع مشکلات (مشکلات بهینه سازی) اغلب با استفاده از روش حریص و برنامه نویسی پویا قابل حل است. غالباً ، روش حریص راه حل های کارآمدتری (اما نه همیشه) ایجاد می کند.

با این حال ، غالباً تشخیص اینکه آیا روش حریص واقعاً راه حل های بهینه تولید می کند ، بسیار دشوار است. مثال الگوریتم حریص را برای ایجاد تغییر به یاد بیاورید. به نظر می رسید که برای سکه های آمریکایی خوب کار می کند ، اما برای هیچ مجموعه دلخواه سکه کار نمی کند. برای برنامه نویسی پویا ، معمولاً بسیار ساده تر می توان دانست که راه حل بهینه است-اگر اصل بهینه نگه داشته شود و ما یک راه حل بازگشتی پیدا کنیم ، کل راه حل بهینه است.

مشکل Knapsack یک مشکل بهینه سازی مشهور است. این نگران است که بفهمید چقدر می توانید در یک کوله پشتی (یا کوله پشتی) قرار بگیرید تا سود آنچه را که در داخل کوله پشتی است به حداکثر برسانید. تصور کنید که شما یک فروشنده هستید و فقط می توانید آنچه را که در داخل کوله پشتی شماست بفروشید. شما نمی خواهید ارزان ترین موارد را بگیرید ، می خواهید مواردی را که بیشترین سود را برای شما کسب کرده است ، بگیرید.

دو مشکل در مورد مشکل کوله پشتی وجود دارد. در مشکل 0-1 Knapsack ، شما باید یک مورد کامل را بردارید یا نه. شما نمی توانید نیمی از یک مورد را بگیرید. در مشکل کسری کوله پشتی ، فقط می توانید بخشی از یک مورد را در نظر بگیرید.

در مشکل 0-1 Knapsack ، شما باید یک مورد را تهیه کنید یا یک مورد را نگیرید. شما ممکن است بخشی از یک مورد را نگیرید. از آنجا که هدف بهینه سازی سود موارد موجود در کوله پشتی است ، ممکن است استفاده از روش حریص برای حل مشکل را در نظر بگیریم. با استفاده از روش حریص ، باید یک روش انتخاب داشته باشیم. روشی برای انتخاب کدام مورد بیشترین سود را در سود دارد.

بیایید موارد زیر را در نظر بگیریم:

کدام یک از اینها بهترین انتخاب است؟ما می توانیم با توجه به حداکثر سود انتخاب کنیم. بیایید بگوییم که کوله پشتی ما می تواند 20 واحد وزن داشته باشد. اگر با توجه به حداکثر سود انتخاب کنیم ، مورد شماره 3 را برای کل سود 70 دلار انتخاب می کنیم. با این حال ، یک راه حل بهتر انتخاب موارد 1 و 2 برای سود کل 110 دلار است. بنابراین انتخاب با توجه به سود حداکثر راه حل خوبی نیست.

ما ممکن است با توجه به حداقل وزن انتخاب کنیم ، اما موارد زیر را در نظر بگیرید:

در این حالت ، انتخاب با توجه به حداقل وزن برای یک کوله پشتی که می تواند 20 واحد وزن را در خود جای دهد ، به جای راه حل بهتر مورد 3 با سود کل 70 دلار ، به سود کل 8 دلار منجر می شود.

گزینه دیگر انتخاب با توجه به سود در واحد نسبت وزن است. این موارد را در نظر بگیرید:

اگر با توجه به بهترین نسبت سود/وزن انتخاب کنیم ، با موارد 1 و 2 با سود کل 110 دلار به پایان می رسیم. راه حل بهتر مورد 3 برای سود کل 140 دلار است. این فرضیه ظرفیت 20 واحد وزن را بر عهده دارد.

بدیهی است که روش حریص همیشه یک راه حل بهینه برای روش 0-1 کوله پشتی ایجاد نمی کند. در مورد مشکل کسری کوله پشتی چیست؟

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

بالاترین نسبت سود/وزن مورد 1 است ، بنابراین ما آن را انتخاب می کنیم. وزن آن 5 است ، و کوله پشتی ما می تواند 30 را نگه دارد ، بنابراین ما کل مورد را می گیریم. بالاترین نسبت سود/وزن بعدی مورد 3 است. وزن آن 20 است و ما 25 فضای در کوله پشتی باقی مانده است ، بنابراین کل مورد را می گیریم. بالاترین نسبت سود/وزن بعدی مورد 2 است. ما 5 فضای در کوله پشتی خود باقی مانده است و این مورد وزن آن 10 است. بنابراین می توانیم 50 ٪ از کالاها را بگیریم. 50 ٪ از این کالا برای آن بخش از کالا 30 دلار سود می بخشد. سود کل سپس 50 دلار + 140 دلار + 30 دلار = 220 دلار است. این راه حل بهینه است.

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

روش حریص برای مشکل 0-1 Knapsack کار نکرد. از آنجا که این یک مشکل بهینه سازی است ، ممکن است انتظار داشته باشیم که برنامه نویسی پویا کار کند. در حقیقت ، می توان از برنامه نویسی پویا برای حل این نسخه از مشکل Knapsack استفاده کرد ، جایی که روش حریص شکست خورد.

مانند بسیاری از الگوریتم های برنامه نویسی پویا ، این یک آرایه دو بعدی استفاده می کند. اگر ما آرایه P را نامگذاری کنیم ، پس از آن سود [i] [w] سود حاصل از انتخاب از اولین موارد من است ، با محدودیت وزن w. ما محتویات این آرایه را پر خواهیم کرد ، با شروع مقادیر کم I و W ، حرکت می کنیم تا اینکه محلول نهایی را با I = N و W = W محاسبه کنیم (سرمایه W حد وزن Knapsack است). هرچه دورتر در امتداد آرایه حرکت می کنیم ، مقادیر را در آن قرار می دهیم که حداکثر سود را نشان می دهد.

1. انتخاب اول ما فرض می کند که ، برای مورد اول ، ما آن را انتخاب نمی کنیم. بنابراین ، حداکثر سود همان است که برای مورد قبلی یا P [i-1] [k] (جایی که من موردی است که ردیف را نشان می دهد ، و k ظرفیت نشانگر ستون است)
2. انتخاب دوم ما فرض می کند که ، برای مورد اول ، ما آن را انتخاب می کنیم. بنابراین ، حداکثر سود سود آن مورد به علاوه سود برای موارد قبلی در هر فضای باقیمانده یا p [ i-1] [k - وزن [i]] + سود [i] است.

ما به سادگی هر دو مقادیر را محاسبه می کنیم و حداکثر را انتخاب می کنیم.

می توانید الگوریتم برنامه نویسی پویا را در اینجا پیدا کنید. OH بزرگ این الگوریتم چیست؟

بیایید این الگوریتیم را با برخی از موارد نمونه امتحان کنیم. در اینجا مجموعه ای از مواردی که با رویکرد حریص امتحان کردیم وجود دارد.

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

اگر W بسیار زیاد باشد ، این الگوریتم خیلی کارآمد نیست. همانطور که متوجه شدید هنگام اجرای این الگوریتم ، بسیاری از ورودی های P یکسان هستند. صفحه 169 در کتاب شما اصلاحاتی را در الگوریتم توصیف می کند که در آن فقط ورودی های موجود در P را که مهم هستند محاسبه می کنید. این باعث می شود الگوریتم کارآمدتر شود.

رویکرد اساسی شروع از P [n] [w] است. شما می دانید که شما باید آن عنصر را محاسبه کنید ، زیرا این پاسخ به مشکل است. از آنجا ، شما می دانید که باید هر دو P [N-1] [W] و P [N-1] [W-وزن [N]] را محاسبه کنید. برای این دو عنصر می توانید بفهمید که چهار عنصر دیگر باید محاسبه شوند. برای این چهار عنصر ، می توانید بفهمید که هشت عنصر باید محاسبه شود ، و غیره. باید متوجه یک الگوی 2 N در حال تحول شوید. این یک O (2 N) برای این الگوریتم به شما می دهد.

بیایید ببینیم که چگونه این داده ها روی داده های زیر کار می کند:

ظرفیت 15 را به خود اختصاص دهید.

من سود و وزن را برای برخی از موارد موجود در صفحه می نویسم و ظرفیتی را برای کوله پشتی به شما می دهم. شما الگوریتم ها را برای هر دو مشکل کرکس کسری و مشکل 0-1 Knapsack اجرا خواهید کرد و به من بگویید که موارد بهینه برای هر دو مورد چیست. این تمرین 10 امتیاز دارد.

برای مشکل 0-1 کوله پشتی ، ممکن است کل آرایه را محاسبه کنید ، یا فقط عناصری را که مهم هستند ، محاسبه کنید.

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

برنامه ریزی با مهلت

در این مشکل برنامه ریزی ، هر شغلی که باید اجرا شود سود و مهلت دارد. اگر کار تا مهلت انجام شود ، ما سود آن کار را می گیریم. اگر کار پس از مهلت انجام شود ، ما از کار سود نمی گیریم. هر کار دقیقاً یک بار واحد طول می کشد. مثلا:

هدف این است که بفهمیم برای دستیابی به حداکثر سود می توانیم کدام شغل را انجام دهیم. از آنجا که برخی از مشاغل مهلت یکسانی دارند ، ما احتمالاً قادر به انجام همه کارها نخواهیم بود. ما می توانیم همه ترکیبات ممکن از مشاغل را بفهمیم. این رویکرد نیروی بی رحمانه O (n!) خواهد بود که بسیار ناکارآمد است.

ما می توانیم با توجه به چند مورد ، یک الگوریتم کارآمدتر بسازیم. اول ، همه ترکیبات مشاغل امکان پذیر نیست. به عنوان مثال ، از آنجا که موارد 2 و 4 هر دو مهلت 1 دارند ، ما نمی توانیم ترکیبی داشته باشیم که در آن شغل 4 و سپس شغل 2 را اجرا کنیم (زیرا بعد از اجرای کار 4 ، زمان به 2 رسیده است ، بنابراین مهلت Job 2گذشت)دوم ، با توجه به انتخاب بین مشاغل ، ما می خواهیم شخصی را انتخاب کنیم که حداکثر سود را به ما می دهد.

اولین قدم در الگوریتم مرتب سازی مشاغل به منظور بالاترین سود تا کمترین سود است.

الگوریتم ما:

در حالی که (مشکل حل نشده است) کار بعدی را انتخاب کنید

اگر (S با آن کار اضافه شده باشد) اضافه کنید) کار را به S اضافه کنید

if (there are no more jobs) problem is solved >

S مجموعه ای از مشاغل است. بیایید این کار را بر روی داده های بالا اجرا کنیم.

به نظر می رسد که ما یک بار در حال پردازش هر یک از موارد هستیم ، که می تواند OH بزرگ O (n) را به ما بدهد. اما ، این سؤال در مورد اینکه آیا S دارای ترکیبات معتبر است به این معنی است که برای بررسی چند ترکیب به نوعی حلقه نیاز داریم. در بدترین حالت ، ما با یک حلقه دیگر بر اساس N به پایان می رسیدیم و به ما (شماره 2) می دهیم.