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

امروز عصر خونه برگشتنی می‌خواستم تخم مرغ بگیرم؛ سوپری اول به نظرم نداشت (!)، دومی شلوغ بود (کروناااا)، سومی خودِ خودِ کرونا بود و ... نزدیکای خونه دیگه دل به دریا زدم و گفتم اولین مغازه می‌خرم، هر چه بادا باد. چون اصلا حال نداشتم دوباره برگردم سراغ مغازه‌های قبلی. اینجا بود که یاد یکی از سخنرانی‌های افتتاحیه‌ی مسابقه‌ی اِی‌سی‌اِم⁺ امسال در مورد الگوریتم‌های آنلاین افتادم.

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


مسیر سفری رو در نظر بگیرید که طول مسیر مثلا ۱۰ سرویس به اصطلاح بهداشتی هست که البته خیلی‌ها چندان بهداشتی نیستن. سرویس اولی کمی کثیفه، دومی کثیف‌تر، سومی تمیز‌تر اما شاید بهتر از اون هم باشه ... و خب مسئله اینجاست که ما توی اتوبانیم و برگشت به عقب وجود نداره؛ یا باید سرویس رو انتخاب کرد و یا پیش رفت تا گزینه‌ی بعدی که معلوم نیست تمیزتر باشه. وجه تشابه تخم مرغ خریدن من و سرویس بهداشتی رفتن در سفر اینه که اطلاعات به صورت یکجا در اختیار ما قرار ندارن و در هر مرحله می‌تونیم گزینه‌ی فعلی رو انتخاب کنیم یا بریم سراغ بعدی، بدون امکان بازگشت به گزینه‌های قبلی. حالا سوال اینه چقدر احتمال داره بهترین و تمیزترین سوپری/سرویس رو از بین گزینه‌های ممکن انتخاب کنیم؟ و حداقل چطور می‌تونیم مطمئن شیم که با احتمال بالایی انتخاب خوبی داشتیم؟ پس چالش مهم این تیپ مسائل انتخاب بهتر از گزینه‌هایی هست که به صورت جریانی از اطلاعات یکی یکی در اختیار ما قرار می‌گیرن.

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


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


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

جزئیات بیشتر رو اینجا بخونید.

بعدن‌نوشت: راستی اگه تعداد هم از اول معلوم نباشه چی؟!

--------------------------------

⁺ الان اسمش عوض شده. اما هر وقت همه‌ی تبریزیا به چهارراه شهناز گفتن چهارراه شریعتی، منم به مسابقات اِی‌سی‌اِم (و در اصل اِی‌سی‌اِم-آی‌سی‌پی‌سی) آی‌سی‌پی‌سی خالی می‌گم.