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

تلاش برای تصمیم در عدم قطعیت
جستجو:  

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

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

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

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

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

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

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

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

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


تا کنون ۴ امتیاز ثبت شده
نوشته لایک نداشت؟
 
به اشتراک گذاری نوشته

algs.ir/spgi6y4

اشتراک‌گذاری در LinkedIn     اشتراک‌گذاری در Twitter     ارسال با Telegram


نام: *  

پست الکترونیک (محرمانه):

پیام: *  

01 02 06 07 08 09 10 11 12 13 14

• ثنا
۲۱ بهمن ۱۴۰۱، ساعت ۱۹:۳۰

070707070707070707070707070707070707070707070707070707070707070707070707070707070707