پاسخ سوال 3271

سلام،
در این پست به ارایه راه حل مسئله ۳۲۷۱ از سوی تیم iQueue می‌پردازم.

متاسفانه علی رغم تلاش‌های انجام شده ظاهرا اکثر دانشجویان تمایلی به حل مسایل مسابقات ندارند. در سوال اخیر کدهای 16 نفر از 20 نفر (دو نفر نیز کد را ارسال نکرده‌اند) به طور روشنی کپی‌برداری بود.

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

ادامه...

سوال ۳۲۷۱ علی رغم ظاهر پیچیده آن، چندان هم آسان نیست! :D ممکن است راه حلی که ارایه می شود کاملا هم صحیح نباشد (که البته اینطور است و خواهیم دید) چون طبق برخی مشاهدات، موارد آزمون داوری نیز چندان دقیق نیست و تعدادی از نقاط مستعد به خطا را تشخیص نمی‌دهد.

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

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

7
7 7
1 2 11
2 3 3
3 4 1
4 5 2
5 6 11
6 7 11
7 2 12
2
1
5

خوب این معادل گراف زیر است:

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

که مجموع اوازن یال‌ها برابر 39 می‌شود. ولی با یک محاسبه سرانگشتی در می‌یابیم که حاصل صحیح این مورد باید گراف زیر باشد:

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

الگوریتمی که ارایه می‌شود به این مشکل پاسخ می‌دهد. روشی که به قول آقای مهدیجو روش «حذف و ادامه» (EAC) (بر (بی)وزن تقسیم و حل (DAC)) نام دارد :P

این الگوریتم به شرح زیر است:

1. درخت پوشای کمینه‌ی گراف اصلی و وزن آن را محاسبه می‌کنیم.

2. سپس گره‌هایی که در آن‌ها داور وجود ندارد را یکی‌یکی حذف و درخت پوشای کمینه را مجددا محاسبه می‌کنیم. به عنوان مثال در نمونه فوق، اول گره 2 را حذف می‌کنیم و درخت را حساب می‌کنیم، سپس گره 2 را سرجای خود قرار می‌دهیم و گره 3 را حذف و درخت را محاسبه می‌کنیم و الی آخر. اوزان نتیجه این روند برای مثال فوق به صورت زیر است:
با حذف 2: بینهایت (چون گراف همبند نمی‌شود؛ درواقع درخت پوشایی نمی‌توان تشکیل داد)

با حذف 3: 47
با حذف 4: 48
با حذف 6: 29

3. اگر مینیمم اوزان بدست آمده از وزن درخت پوشای کمینه اصلی (39) کمتر نبود که جواب همان درخت اصلی است. اگر مینیمم آن‌ها از وزن درخت اصلی کمتر باشد درخت حاصل از حذف گرهی که مینیمم را دست داده است به عنوان درخت اصلی در نظر می‌گیریم و با برگشت به مرحله 2 محاسبات را تکرار می‌کنیم.

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

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

این الگوریتم گراف زیر را با وزن 9 به عنوان جواب معرفی می‌کند:

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

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

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


موفق باشد.
علی ربیعی از تیم iQueue

---
ضمیمه: کد این راه حل به زبان سی++

ضمیمه: با تشکر از آقای ساعی، شرح راه حل ایشان را از اینجا دریافت نمایید.