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