✤  مسئله‌ی اعداد اردوش

مسئله

  [برگرد بالا]

پل اردوش (اردیش - 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)$ است. اما پیاده‌سازی ساده‌تری نسبت به آن دارد.