الگوریتمستان

برنامه‌نویسی، طراحی الگوریتم و حل مسئله‌های الگوریتمی

 
در صورت ناخوانا بودن نوشته‌ها، از مرورگر دیگری استفاده کنید.
مسئله‌ی اعداد اردوش - الگوریتمستان
الگوریتمستان
  »  

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

        بررسی مسئله‌ی اعداد اردوش (Erdos Numbers) یا فاصله‌ی همکاری اردوش از سوالات آمادگی مسابقات برنامه‌نویسی موجود در کتاب Programming Challenges و وبسایت UVa Online Judge
آنچه در این نوشته می‌خوانید:
   •  مسئله‌ی اعداد اردوش
       »  مسئله
       »  ورودی مسئله
       »  خروجی مسئله
       »  حل مسئله

مسئله

  [بازگشت به فهرست]

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

به اشتراک‌گذاری نوشته
اشتراک‌گذاری در LinkedIn     Cloob     اشتراک‌گذاری در Twitter     اشتراک‌گذاری در Facebook     ارسال با Telegram     Google Plus
امتیاز نوشته
  • 1
  • 2
  • 3
  • 4
  • 5

نام: *  

پست الکترونیک:

وبگاه:

متن پیام: *

01 02 03 04 05 06 07 08 09 10 11 12 13 14

 


الگوریتمستان در تلگرام

   

   

پیوند کوتاه: عمر نوشته:  ۵۸۰ روز
تعداد بازدید:  ۳۱۵۴ بازدید
تعداد امتیاز:  ۳ امتیاز
میانگین امتیاز:  ۵.۰۰  از  ۵.۰۰
»  مسئله‌ی Column Addition
        بررسی مسئله‌ی Column Addition، از سوالات مسابقه‌ی برنامه‌نویسی ACM-ICPC 2017 سایت تهران
»  مسئله‌ی آتش‌سوزی در برره
        بررسی مسئله‌ی آتش در برره، از سوالات مسابقه‌ی برنامه‌نویسی ACM-ICPC 2017 سایت تهران
»  مسئله‌ی حداکثر مجموع
        بررسی مسئله‌ی حداکثر مجموع، از سوالات آمادگی مسابقات برنامه‌نویسی
»  کتاب راهنمای برنامه‌نویسان رقابتی
        معرفی کتاب Competitive Programmer's Handbook (راهنمای برنامه‌نویسان رقابتی) برای علاقه‌مندان به مباحث الگوریتم‌ها و شرکت‌کنندگان در مسابقات برنامه‌نویسی با امکان دانلود
»  مسئله‌ی Turn the Lights Off
        متن فارسی و روش حل مسئله‌ی Turn the Lights Off از سوالات وبسایت UVa Online Judge
»  مسئله‌ی Jolly Jumpers
        متن فارسی مسئله‌ی Jolly Jumpers از سوالات تمرینی کتاب‌های آمادگی مسابقات برنامه‌نویسی و وبسایت UVa Online Judge
»  مستندات دوره‌ی آمادگی مسابقات برنامه‌نویسی دانشگاه استنفورد
        مستندات دوره‌ی Introduction to Programming Contests دانشگاه استنفورد با موضوع ریاضیات، ساختمان داده‌ها و الگوریتم‌های مورد نیاز برای شرکت در مسابقات برنامه‌نویسی
»  مسئله‌ی The Trip
        متن فارسی مسئله‌ی The Trip از سوالات تمرینی کتاب‌های آمادگی مسابقات برنامه‌نویسی و وبسایت UVa Online Judge
»  مسئله‌ی 3n+1 Problem
        متن فارسی مسئله‌ی 3n+1 Problem (حدس کولاتز یا حدس 3n+1) از سوالات تمرینی کتاب‌های آمادگی مسابقات برنامه‌نویسی و وبسایت UVa Online Judge
»  مسئله‌ی Encrypted SMS
        متن فارسی مسئله‌ی Encrypted SMS از سوالات مسابقه‌ی برنامه‌نویسی ACM-ICPC 2007 منطقه‌ای سایت تهران
»  مسئله‌ی Gholam's Simple Game
        متن فارسی مسئله‌ی Gholam's Simple Game از سوالات مسابقه‌ی برنامه‌نویسی ACM-ICPC 2010‌ منطقه‌ای سایت تهران
»  راه حل سوالات مسابقه‌ی جهانی ACM-ICPC 2016
        راه حل سوالات مسابقه‌ی جهانی ACM-ICPC 2016
»  مسئله‌ی What Base Is This
        متن فارسی مسئله‌ی شماره‌ی 343 از UVa Online Judge، ار سوالات تمرینی کتاب‌های آمادگی مسابقات برنامه‌نویسی
»  ویدئوهای آموزشی کلاس Programming Challenges
        ویدئوهای آموزشی کلاس Programming Challenges شامل مباحث الگوریتم‌ها، ساختمان داده‌ها و ریاضیات محاسباتی برای آمادگی مسابقات برنامه‌نویسی