مسئله‌ی آسانسورها - الگوریتمستان
الگوریتمستان
315.005.00
  »  

       

بررسی مسئله‌ی آسانسورها (Elevators)، از سوالات مسابقات برنامه‌نویسی ACM

آنچه در این نوشته می‌خوانید:
   •  مسئله‌ی آسانسورها
       »  مسئله
       »  ورودی برنامه
       »  خروجی برنامه
       »  حل مسئله

مسئله

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

    ساختمان جدید دپارتمان مهندسی کامپیوتر تنها شامل آسانسور بوده و پله ندارد. برای دسترسی سریع و مناسب به اتاق‌ها و کلاس‌های طبقات مختلف، آسانسورها به گونه‌ای تنظیم شده‌اند که تنها در طبقات مشخصی توقف داشته باشند؛ مثلا تعدادی تنها در طبقات زوج و تعدادی دیگر تنها در طبقات فرد. دکمه‌های داخل آسانسور و کنار ورودی آسانسور نیز تنها برای همین طبقات از پیش مشخص شده فعال هستند. این ایده دسترسی سریع و مناسب به طبقات ساختمان را برای برخی افراد فراهم می‌کند. به عنوان نمونه اعضای هیئت علمی دسترسی مستقیم به طبقات اتاق‌های خود دارند. اما در حالت کلی باعث سردرگمی می‌شود. اگر شخصی بخواهد از طبقه‌ای به طبقه‌ی دیگری برود، ممکن است هیچ آسانسوری در هر دوی آنها توقف نداشته باشد و شخص مجبور به تعویض آسانسور گردد. در چنین شرایطی این سوال پیش می‌آید که کدام آسانسور (یا آسانسورها) باید انتخاب شوند و کدام انتخاب‌ها شخص را در زمان کمتری به مقصد می‌رساند. اگر مسیر حرکت شخص از طبقه‌ی i به طبقه‌ی j به صورت $ i = f_1 \rightarrow f_2 \rightarrow f_3 \rightarrow \cdots \rightarrow f_k = j $ نمایش داده شود، عبارت $ \sum_{r=1}^{k-1} \vert f_i - f_{i+1} \vert $ زمان لازم برای رسیدن به مقصد از طریق آن مسیر است. برنامه‌ای بنویسید که افراد را در استفاده‌ی بهتر (در زمان کمتر) از آسانسورها یاری کند.

      

ورودی برنامه

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

هر ورودی از یک سطر با سه عدد i، n و j شروع می‌شود که به ترتیب تعداد آسانسورها، طبقه‌ی مبدأ و طبقه‌ی مقصد را مشخص می‌کند. در ادامه، طبقات توقف هر آسانسور در یک سطر مجزا آمده است که هر کدام با عدد m برای مشخص شدن تعداد طبقات توقف شروع می‌شوند.

    n یک عدد طبیعی نابیشتر از 10 بوده و هر آسانسور حداکثر در 150 طبقه توقف می‌کند. انتهای ورودی‌ها نیز سه عدد صحیح صفر برای i، n و j است.

      

2 2 5

5 0 1 3 5 7

5 0 2 4 6 8

3 3 8

6 0 1 2 3 4 5

5 0 6 7 8 9

4 0 4 5 6

0 0 0

  

خروجی برنامه

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

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

      

7

5

  

    منبع: مسابقه‌ی ACM منطقه‌ای آسیا 2014 - سایت تهران - مسئله‌ی Elevators

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

  

حل مسئله

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

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

      

مسئله‌ی آسانسورها

      

    با توجه به این مدل‌سازی، حل مسئله تبدیل به یافتن کوتاهترین مسیر از گره طبقه‌ی مبدأ به گره طبقه‌ی مقصد می‌شود. پس می‌توان با استفاده الگوریتم دایکسترا با مرتبه‌ی زمانی $O(n^2)$ به نتیجه‌ی مطلوب رسید.

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


این نوشته آخرین بار در تاریخ پنجشنبه، ۱۰ فروردین ماه ۱۳۹۶ مورد بازنویسی نگارشی قرار گرفته است.
نوشته‌های مرتبط
        بررسی مسئله‌ی حداکثر مجموع، از سوالات آمادگی مسابقات برنامه‌نویسی
        متن فارسی مسئله‌ی The Trip از سوالات تمرینی کتاب‌های آمادگی مسابقات برنامه‌نویسی و وبسایت UVa Online Judge
        معرفی کتاب Competitive Programmer's Handbook (راهنمای برنامه‌نویسان رقابتی) برای علاقه‌مندان به مباحث الگوریتم‌ها و شرکت‌کنندگان در مسابقات برنامه‌نویسی با امکان دانلود
        متن فارسی مسئله‌ی 3n+1 Problem (حدس کولاتز یا حدس 3n+1) از سوالات تمرینی کتاب‌های آمادگی مسابقات برنامه‌نویسی و وبسایت UVa Online Judge
        متن فارسی و روش حل مسئله‌ی Turn the Lights Off از سوالات وبسایت UVa Online Judge
        متن فارسی مسئله‌ی Encrypted SMS از سوالات مسابقه‌ی برنامه‌نویسی ACM-ICPC 2007 منطقه‌ای سایت تهران
        متن فارسی مسئله‌ی Jolly Jumpers از سوالات تمرینی کتاب‌های آمادگی مسابقات برنامه‌نویسی و وبسایت UVa Online Judge
        متن فارسی مسئله‌ی Gholam's Simple Game از سوالات مسابقه‌ی برنامه‌نویسی ACM-ICPC 2010‌ منطقه‌ای سایت تهران
        مستندات دوره‌ی Introduction to Programming Contests دانشگاه استنفورد با موضوع ریاضیات، ساختمان داده‌ها و الگوریتم‌های مورد نیاز برای شرکت در مسابقات برنامه‌نویسی
        راه حل سوالات مسابقه‌ی جهانی ACM-ICPC 2016
پیوند کوتاه صفحه دسته‌بندی
امتیاز نوشته
  • 1
  • 2
  • 3
  • 4
  • 5
ارسال پیام

نام: *  

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

وبگاه:

متن پیام: *