در این پست به ارایه راه حل سوال 4288 میپردازم.
این سوال یکی از جالبترین و البته مشکلترین سوالات این ترم طراحی الگوریتم بود. آنچه از ظاهر ساده سوال برمیآید آن است که حل آن با استفاده از یک الگوریتم ساده نیز ممکن است. در این سوال، برخلاف سوال قبلی موارد آزمون داوری بسیار دقیق و حسابشده طرح شدهاند و حل آن جز به الگوریتمی معین میسر نیست. خوب برویم سر اصل مطلب...
1. فصل 26 کتاب طراحی الگوریتم:
2. فسفر: به مقدار لازم
در واقع در بیان این راه حل فرض بر این است که شما فصل 26 کتاب طراحی الگوریتم را تا پایان بخش سوم مطالعه کردهاید و با مسایلی از قبیل حداکثر جریان و بیشترین تعداد همخوان آشنا هستید.
در پایان این پست نیز اشارهای به بهینهسازیهای انجام شده و کاهش قابل توجه زمان اجرای کد راه حل این مسئله خواهم کرد.
در بخش ضمائم، کدهای این راه حل قابل دریافت است.
در این مسئله یک سری تماشاگر با یک سری تماشاگر دیگر سر بود و نبود یک سری سگ و گربه اختلاف دارند! پس، بودن یا نبودن، مسئله این است؟! نه این نیست، مسئله نوشتن برنامهای است که اگر سگها و گربهها به طور مناسبی از صحنه کنار روند، در نهایت، حداکثر تعداد بینندهای را که بدون اختلاف میتوانند مسابقه را تماشا کنند، تعیین کند.
ایده ساده حل آن چنین است:
باید حداقل تعداد افراد ممکن را حذف کنیم تا دیگر اختلافی وجود نداشته باشد.
در این صورت حداکثر تعداد افراد غیرمخالف میمانند که با هم میتوانند نمایش را ادامه دهند.
حال گراف G=(V,E) را گراف نمایشدهنده اختلافات، آرای تماشاگران را به عنوان رئوس آن و اختلاف بین دو رای را یالی بین رئوس متناظر با آن در نظر میگیریم که تعریف ریاضی آن به صورت زیر میشود:
که در اینجا اندیسهای صفر و یک نشاندهنده قسمت اول یا دوم هر رای است.
لم 1: گرافهایی که در این سوال شکل میگیرند همگی گرافهایی دوقسمتی (bipartite graph) هستند.
اثبات: اگر دسته گربهدوستان و سگدوستان را به ترتیب CD و DC بنامیم، بدیهی است که اختلافات تنها بین این دو دسته اتفاق میافتد. به بیان دیگر، آرای دسته CD نمیتوانند با هم اختلاف داشته باشند و آرای دسته DC هم همینطور. تنها آرایی میتوانند با هم اختلاف داشته باشند که یکی در دسته CD یا DC و دیگری در دسته DC یا CD قرار داشته باشد. از این رو گراف را میتوان به دو قسمت CD و DC تقسیم کرد در حالی همه یالها تنها بین این دو دسته قرار دارند.
تئوری 1: «کمترین پوشش رأسی» (MVC: Minimum Vertex Cover) عبارت است از کوچکترین زیر مجموعهای از روئوس گراف G که همه یالهای گراف، به حداقل یکی از روئوس این مجموعه متصل است.
بنابر تئوری 1، یالی وجود ندارد که یکی از رئوس دو سر آن در مجموعه MVC وجود نداشته باشد. خوب، ارتباط این تئوری با گراف مسئله ما تقریبا مشخص است. از آن جا که گراف ما نشاندهنده اختلافات بین تماشاگران است، پس کافیست MVC این گراف را یافته و حذف کنیم. در واقع MVC نشاندهنده حداقل تعداد شرکتکنندگانی است که اگر کنار روند، بیشترین تماشاگران غیرمخالف با هم باقی میمانند. با حذف رئوس مجموعه MVC دیگر یالی در گراف باقی نمیماند و در نتیجه اختلافی نیز وجود نخواهد داشت. از آنجا که در این مسئله تنها تعداد مهم است، ما صرفا به محاسبه اندازه یک مجموعه MVC از گراف G میپردازیم.
الگوریتم محاسبه MVC برای یک گراف عمومی در زمره مسایل NP-Complete است. به بیان دیگر حل آن در زمان چندجملهای بعید است. ولی محاسبه MVC برای گرافهای خاص مانند گراف دو قسمتی در زمان چندجملهای امکانپذیر است. تئوری کانیگ، نحوه محاسبه تعداد یک مجمومه MVCی یک گراف را شرح میدهد.
تئوری 2 (تئوری کانیگ): در هر گراف دو قسمتی، تعداد یالهای بیشترین تعداد همخوان (Maximum Matching) برابر است با تعداد رئوس در یک مجموعه MVC.
نهایتاً بنا بر لم 1 و تئوری 2 کافیست اندازه مجموعه کمترین پوشش راسی را محاسبه و از تعداد کل رایدهندگان کم کنیم. حاصل حداکثر تعداد تماشاگرانی است که با یکدیگر اختلاف ندارند.
و اما خلاصهای درباره کد راه حل...
در این کد از الگوریتم Ford-Fulkerson با رئوس منبع و مخرج مجازی استفاده شده است؛ یعنی در کد اثری از افزودن یا حذف دو راس اضافی وجود ندارد. به عکس از آرایهای به نام blocked برای تعیین مسدود بودن ورود-از-منبع یا خروج-به-مخرج استفاده شده است. در این کد از الگوریتم DFS برای یافتن مسیرهای تکمیلی (Augmenting Path) استفاده شده است.
یکی از بهینهسازی انجام شده که باعث کاهش 6700 میلیثانیهای زمان اجرای الگوریتم شده است، احتساب خطوط مستقیم از یک دسته به دسته دیگر به صورت درجا و حین رسم گراف است. در واقع، در گراف دوقسمتی مسئله اگر راه مستقیمی از یک گره غیر مسدود یک دسته به گره غیر مسدود دسته دیگر وجود داشته باشد، در جا، آن یال محاسبه و به تعداد مجموعه MVC افزوده میشود. در واقع وجود چنین یالی به معنی وجود مسیری تکمیلی از منبع به مخرج است. جهت مطالعه بیشتر، هر دو کد 6 ثانیهای و 60 میلیثانیهای را در ضمیمه قرار دادهام. تنها تفاوت عمده آنها در خط 63 کدها است.
بهینهسازیهای دیگری نیز، از جمله ساختمان داده مورد استفاده برای نمایش گراف وجود دارد که میتوانید با مطالعه کد، به آنها پیببرید.
موفق باشید.
علی ربیعی
---
ضمیمه 1:
کدهای راه حل به زبان سی++
پستها
