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

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

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

فرض کنید در مثال فوق فقط دو حق انتخاب داشته باشیم. در این حالت چه اولی را انتخاب کنیم و چه دومی را، با احتمال یک دوم انتخاب درستی داشته‌ایم و نیاز به استراتژی خاصی برای انتخاب نیست. اگر امکان انتخاب از بین سه گزینه باشد، شش ترتیب مختلف زیر از نظر نظافت وجود دارد که منظور از ۱ تمیزترین و منظور از ۳ کثیف‌ترین سرویس بهداشتی است.

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

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

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

همانطور که می‌بینید از شش حالت در سه حالت عدد ۱ (تمیزترین مکان) پررنگ شده است. پس اجرای این استراتژی با احتمال یک دوم انتخاب درستی برای ما دارد که از انتخاب تصادفی (یک سوم) بهتر است. در حالت کلی ثابت می‌شود اگر $n$ گزینه وجود داشته باشد و $ n / e$ گزینه‌ی اول را (منظور از $e$ عدد نپر است) را بدون انتخاب رد شده و اولین گزینه‌ای که از همه‌ی بازدیدشده‌های قبلی بهتر بود انتخاب کنیم، بیشترین احتمال موفقیت وجود دارد. با اضافه شدن به تعداد گزینه‌ها احتمال موفقیت کوجکتر می‌شود، اما حتی اگر یک میلیارد انتخاب مختلف هم وجود داشته باشد، این احتمال از ۰٫۳۶۷۹ (و به صورت دقیق‌تر وارون عدد نپر) پایین‌تر نمی‌رود. یعنی با این استراتژی در بدترین شرایط با احتمال نزدیک به ۳۷ درصد بهترین سرویس بهداشتی انتخاب می‌شود.

الگوریتم مرتب‌سازی درجی نیز نمونه‌ی دیگری از الگوریتم‌های آنلاین است و در حالت کلی هر الگوریتم حریصانه یک الگوریتم آنلاین است.

◄  پیوندها برای مطالعه‌ی بیشتر
مسعود اقدسی‌فام

مسعود اقدسی‌فام هستم.

یک معلم علاقه‌مند به تحقیق، تدریس و نوشتن در حوزه‌های برنامه‌نویسی، الگوریتم و حل مسئله :)

algs.ir/spgi6y4     اشتراک‌گذاری در LinkedIn     اشتراک‌گذاری در Twitter     ارسال با Telegram
آخرین نوشته‌ها
       ✦   الگوریتم آنلاین
       ✦   ابزار CodinGame
بازدید نوشته
          ۲۴ ساعت گذشته:  ۱۱ بازدید
          ۳۰ روز گذشته:  ۱۲۵ بازدید
          کل: ۱۲۵ بازدید
  • 1
  • 2
  • 3
  • 4
  • 5

نام: *  

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

متن پیام: *  

01 02 06 07 08 09 10 11 12 13 14