بستن پنجره
فرادرس - مجموعه آموزش‌های ویدئویی  مهندسی کامپیوتر - طراحی الگوریتم - ساختمان داده
بستن پنجره
وبگاه
این صفحه
اشتراک‌گذاری در LinkedIn     Cloob     اشتراک‌گذاری در Twitter
اشتراک‌گذاری در Facebook     ارسال با Telegram     Google Plus
مسأله‌ی آسانسورها - الگوریتمستان
الگوریتمستان
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)$ کوتاهترین مسیر بین تمامی گره‌های گراف را محاسبه می‌کند. در این مسأله هدف یافتن کوتاهترین مسیر بین دو گره مشخص (و نه تمامی گره‌ها) است. بنابراین نیازی به استفاده از الگوریتم فلوید-وارشال با مرتبه‌ی بدتر از الگوریتم دایکسترا احساس نمی‌شود. اما با توجه به اندازه‌ی حد آستانه‌ی مقادیر ورودی مسأله، این الگوریتم نیز در زمان مناسب به جواب می‌رسد. مزیت الگوریتم فلوید-وارشال نسبت به الگوریتم دایکسترا پیاده‌سازی آسان و سریع آن است.


نوشته‌های مرتبط
فرادرس - مجموعه آموزش‌های ویدئویی  مهندسی کامپیوتر - طراحی الگوریتم - ساختمان داده
        مسابقه‌ی برنامه‌نویسی آنلاین Codeforces Round 397
        نبرد هوش مصنوعی شریف ۹۵
        مسابقه‌ی برنامه‌نویسی آنلاین Codeforces Round 396
        مسابقه‌ی برنامه‌نویسی آنلاین Codeforces Round 395
        مسابقه برنامه‌نویسی دانشگاه شیخ بهایی
        برگزاری مجدد مسابقه‌ی برنامه‌نویسی ACM
        مسابقه‌ی برنامه‌نویسی آنلاین 15 Quera
        مسابقه‌ی برنامه‌نویسی آنلاین Codeforces Round 394
        مسابقه‌ی تمرینی المپیاد کامپیوتر هندوستان
        مسابقه‌ی برنامه‌نویسی آنلاین Educational Codeforces Round 17
پیوند کوتاه صفحه دسته‌بندی
امتیاز نوشته
  • 1
  • 2
  • 3
  • 4
  • 5
ارسال پیام

نام: *  

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

وبگاه:

متن پیام: *

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