الگوریتم های حریصانه¶
توضیحات¶
الگوریتم های حریصانه یا گریدی دسته ای از الگوریتم ها هستند که ما در هر مرحله سعی میکنیم همواره بهترین گزینه را انتخاب کنیم. کاربرد این الگوریتم ها بسیار زیاد و متنوع است. در ادامه چند مسئله که به کمک این الگوریتم ها حل میشوند آمده است.
مسئله کوله پشتی (مایع)¶
در این مسئله ما \(n\) مایع داریم که از مایع \(i\) ام \(L_i\) لیتر وجود دارد. قیمت هر لیتر از مایع \(i\) ام \(C_i\) تومان است و وزن هر لیتر از این مایع \(V_i\) گرم است. ما میخواهیم به بازار برویم و مقداری از این \(n\) مایع ها را بفروشیم ولی متاسفانه حداکثر \(W\) گرم میتوانیم حمل کنیم و میخواهیم بدانیم حداکثر فروشی که میتوانیم در یکبار رفتن به بازار داشته باشیم چقدر است.
راه حل
ابتدا مایع ها را بر حسب \(\frac {C_i} {V_i}\) از زیاد به کم مرتب میکنیم. برای سادگی در ابتدا فرض کنید برای هیچ دوتایی این مقدار برابر نیست. حال به ترتیب شروع میکنیم و از هر مایع هر چقدر که میتوانیم برمیداریم. یعنی اگر تا کنون \(w\) گرم برداشته ایم از مایع کنونی \(min(\frac {W-w} {V_i} , L_i)\) لیتر بر می داریم.
فرض کنید حالتی وجود داشته باشد که فروش بیشتری داشته باشیم. یکی از حالات بهینه را در نظر بگیرید. میدانیم مایع ای وجود دارد که نسبت به حالت اول از آن بیشتر فروخته ایم. این مایع را در نظر بگیرید و فرض کنید از آن \(l\) لیتر بیشتر فروخته ایم . اگر مایع ای نباشد که در ترتیب ما زودتر آمده باشد و الان کمتر فروخته شده باشد پس ما از این مایع بیشینه مقدار ممکن را انتخاب نکرده بودیم که تناقض است. اگر مایع ای وجود داشته باشد که کمتر فروخته باشیم و در ترتیب ما زود تر آمده باشد میتوانیم از آن بیشتر بفروشیم و از این مایع کمتر و سود بیشتری کسب کنیم پس حالتی که در نظر گرفتیم بهینه ترین حالت نبوده است که باز هم در تناقض است با فرض خلف ما.
حال اگر \(i\) و \(j\) وجود داشت که \(\frac {C_i} {V_i} = \frac {C_j} {V_j}\) و همچنین \(R = \frac {V_i} {V_j}\) آنگاه اگر \(l\) لیتر از مایع \(i\) ام بفروشیم مانند این است که \(l \times R\) لیتر از مایع \(j\) بفروشیم پس کافیست به مقدار مایع \(j\) که داریم \(L_i \times R\) واحد اضافه کنیم و خللی در اثبات به وجود نمی آید.
دقت کنید، برای سورت کردن مایع ها بر حسب \(\frac {C_i} {V_i}\) می‌توانید یک آرایه از اندیس ها را به کمک تابع سورت و این تابع
cmp سورت کنید.
- می‌توان به راحتی ثابت کرد چک کردن این شرط معادل چک کردن \(\frac {C_i} {V_i} < \frac {C_j} {V_j}\) است. با چک کردن این شرط از خطای اعشاری جلوگیری می‌شود.
Matching vs Independent Set¶
در این مسئله گرافی \(3 \times n\) راسی داریم و میخواهیم یا مجموعه مستقل حداقل \(n\) راسی پیدا کنیم یا تطابقی با حداقل \(n\) یال.
راه حل
همواره تا وقتی که گراف خالی از یال نشده یک یال را انتخاب میکنیم و رئوس دو سرش به همراه تمام یال های متصل به آن ها را حذف میکنیم حال در انتها اگر حداقل \(n\) راس بماند که میدانیم این رئوس یالی بینشان نیست و مجموعه مستقل هستند. در غیر این صورت میدانیم بیش از \(n\) یال انتخاب کرده ایم زیرا هر مرحله ۲ راس حذف میشوند. همچنین رئوس دوسر یال ها دو به دو متفاوت هستند و در نتیجه این یال ها تطابق ما هستند.
نکته
در اثبات الگوریتم های حریصانه معمولا در ابتدا فرض خلف میکنیم که جواب بهتری وجود داشته باشد و سپس از بین جواب های بهتر جوابی رو میگیریم که ویژگی خاصی داشته باشد و سپس سعی میکنیم به تناقض برسیم.