الگوریتمستان - مسئله اعداد اردوش

پل اردوش (اردیش - Paul Erdős) ریاضیدان مشهور و برجسته قرن بیستم است که تا پایان عمر خود تلاش گسترده‌ای برای انتشار مقالات علمی داشت و همکاری با وی در انتشار مقاله یک افتخار بزرگ برای هر ریاضیدان محسوب می‌گردد.

با توجه به آنکه همکاری با ایشان برای هر کس ممکن نبود، تلاش می‌کردند با نفراتی در انتشار مقاله علمی همکاری کنند که با این دانشمند بزرگ مقاله داشتند. این رویکرد باعث پدید آمدن عدد اردوش (Erdős number) یا فاصله همکاری اردوش شد؛ یعنی برای نویسندگانی که به صورت مستقیم با ایشان همکاری داشتند عدد 1 و برای کسانی که با این نفرات مقاله داشتند عدد 2 نسبت داده شد و ارتباطات دورتر نیز به همین ترتیب با اعداد طبیعی بعدی مشخص شدند.

امروزه هر نویسنده مقالات علمی ریاضی دوست دارد عدد اردوش خود را بداند. ماموریت شما نوشتن برنامه‌ای است که عدد اردوش نویسندگان را بر اساس پایگاه‌داده مشخص شده اعلام کند.

  

ورودی مسئله

  [برگرد بالا]

در سطر اول ورودی تعداد سناریوها آمده است. سپس برای هر تست دو عدد P و N‌ در یک سطر آمده است که به ترتیب تعداد مقاله‌ها و تعداد نفرات مورد نظر برای محاسبه عدد اردوش هستند. در P سطر بعدی مقالات به صورت زیر لیست شده‌اند و در N سطر بعدی نیز اسامی نویسندگانی آمده است که باید عدد اردوش برای آنها محاسبه شود:

  

1

4 3

Smith, M.N., Martin, G., Erdos, P.: Newtonian forms of prime factor matrices

Erdos, P., Reisig, W.: Stuttering in petri nets

Smith, M.N., Chen, X.: First oder derivates in structured programming

Jablonski, T., Hsueh, Z.: Selfstabilizing data structures

Smith, M.N.

Hsueh, Z.

Chen, X.

  

خروجی مسئله

  [برگرد بالا]

به ازای هر سناریو ابتدا عبارتی به صورت Scenario i در یک سطر مستقل چاپ شود که i شماره سناریو است. در ادامه اسامی نویسندگان مد نظر و عدد اردوش آنها هر کدام در یک سطر چاپ شود. اسامی نویسندگان باید به همان ترتیبی باشد که در ورودی آمده است.

  

Scenario 1

Smith, M.N. 1

Hsueh, Z. infinity

Chen, X. 2

  

منبع: وب‌سایت UVa Online Judge - مسئله Erdos Numbers

  

حل مسئله

  [برگرد بالا]

همکار بودن افراد در انتشار یک مقاله را می‌توان به صورت گرافی در نظر گرفت که به هر نویسنده یک رأس تخصیص داده شده و اگر دو نفر همکاری علمی داشته باشند، یالی بین رأس‌های متناظر آنها رسم می‌شود. به عنوان مثال، گراف متناظر ورودی نمونه مسئله به این شکل است:

  

  

همانگونه که از شکل نیز مشخص است، ممکن است چندین مسیر ارتباطی از فرد به سمت رأس متناظر با اردوش وجود داشته باشد. در این مسئله هدف یافتن اندازه کوتاهترین مسیر (در صورت وجود) است. اگر چنین مسیری وجود نداشته باشد، عدد اردوش inifinity خواهد بود.
در ادامه سه راهکار مختلف برای محاسبه کوتاهترین مسیر بررسی می‌شوند.

الگوریتم فلوید-وارشال: اولین ایده برای حل هر مسئله مسیریابی استفاده از الگوریتم فلوید-وارشال است. چرا که با یک پیاده‌سازی چند خطی ساده، اندازه کوتاهترین مسیر بین هر دو رأس دلخواه و همینطور رأس‌های واسط در این مسیر را مشخص می‌کند. اما نکته اصلی آن مرتبه زمان اجرای $\theta(n^3)$ آن است که به ازای مقادیر بزرگ $n$ برای حل سوالات برنامه‌نویسی مناسب نیست. در مورد این مسئله نیز الگوریتم فلوید-وارشال کارآیی مطلوب را ندارد.

الگوریتم دایکسترا: در محاسبه عدد اردوش هدف یافتن کوتاهترین مسیر از رأس متناظر اردوش به هر یک از رأس‌های دیگر است. بنابراین می‌توان از الگوریتم دایکسترا برای حل مسئله استفاده کرد. این الگوریتم در بدترین حالت از مرتبه زمان اجرای $O(n^2)$ است که نسبت به الگوریتم فلوید-وارشال مناسب‌تر است. اما پیاده‌سازی پیچیده‌تری نیز دارد.

الگوریتم جستجوی اول سطح: همانطور که توضیح داده شد، یال‌های بین رأس‌ها همکاری نفرات متناظر دو رأس را نشان می‌دهند. بنابراین یال‌ها وزنی ندارند. در حل مسئله با الگوریتم‌های فلوید-وارشال یا دایکسترا نیز وزن یال‌ها 1 در نظر گرفته می‌شود. با توجه به این موضوع می‌توان کوتاهترین مسیر به هر رأس را با پیمایش اول سطح گراف با شروع از رأس متناظر اردوش محاسبه کرد. نتیجه چنین پیمایشی یک درخت است که نفرات متناظر رأس‌های آن با اردوش به صورت مستقیم یا غیرمستقیم همکاری داشته‌اند. اگر ریشه را سطح صفر در نظر بگیریم، عدد اردوش برای رأس‌های هر سطح، همان شماره سطح آنها است. همچین ممکن است برخی رأس‌های گراف در این درخت موجود نباشند که مقدار عدد اردوش برای آنها infinity است. مرتبه زمانی اجرای این الگوریتم نیز همانند الگوریتم دایکسترا در بدترین حالت $O(n^2)$ است. اما پیاده‌سازی ساده‌تری نسبت به آن دارد.