یکی از شگفتی های قرن ۲۱ام، فراهم شدن امکان تبلیغات برای همه برنامه های کاربردی وب است. همه برنامه های کاربردی میتوانند برای حمایت از خود با توجه به پرداخت یک هزینه از طریق تبلیغات اقدام کنند. همانطور که می دانیم، تلویزیون و رادیو از طریق استفاده از تبلیغات درآمد زیادی کسب می کنند. برای تبلیغات دوروش وجود دارد :
روش اول: تبلیغات آن لاین که بهترین تبلیغ را با توجه به جست و جوی صورت گرفته، ارایه می دهند.
روش دوم: انتخاب موضوعاتی برای تبلیغات در فروشگاه های آن لاین به این صورت که مشتری هایی با رفتار یکسان بیابیم و به آنها آنچه که به نظر می رسد نیاز دارند را پیشنهاد بدهیم.
همانطور که مشاهده می کنیم در روش اول که موضوع مورد بحث ما است تصمیم گیری جهت ارایه یک آگهی باید به صورت آن لاین صورت گیرد. همچنین اینکه درخواست ها به صورت آن لاین هستند و این بدان معنی است که داده های مورد نیاز الگوریتم از ابتدا معلوم نیستند، پس برای آن باید یک الگوریتم آن لاین ارایه شود. در الگوریتم آن لاین برای اختصاص تبلیغات از سری های جستجو استفاده می کنیم. یعنی وقتی یک جست و جو می آید باید سریع یک تبلیغ را انتخاب کنیم و ارایه دهیم. می توانیم از اطلاعات گذشته استفاده کنیم ولی هیچ دیدی نسبت به آینده نداریم. به عنوان مثال نمیدانیم جست و جوی بعدی چیست و آیا اختصاص های قبلی ما بهینه بوده یعنی بودجه آگهی دهنده با توجه به پاسخ گویی ما به جست و جوهای قبلی برای پاسخ به جست و جوهای بعدی لازم است باقی بماند یا خیر.
روش اول مساله تبلیغات به این صورت است که هر یک از آگهی دهندگان یک بودجه ای برای یک بازه زمانی مشخص تعیین می کنند، مثل ۲۰۰۰۰۰تومان برای مدت زمان یک ماه، همچنین یک قیمت پیشنهادی به ازای هر کلمه که جستجو می شود. به عنوان مثال به ازای هر کلمه “مبل” آگهی دهنده مبلغ ۲۱۱ تومن را پیشنهاد می دهد. پس در صورتی که کلمه “مبل” جستجو شود و رسانه تبلیغاتی، آگهی مربوط به آن آگهی دهنده را به جستجو کننده ارایه دهد مبلغ ۲۱۱ تومن از میزان بودجه آگهی دهنده به رسانه تبلیغاتی پرداخت می شود. در این مساله به دنبال حداکثر کردن میزان درآمد رسانه تبلیغاتی هستیم به این صورت که آگهی های داده شده را طوری به جستجو ها ارایه دهد که بیشترین میزان درآمد را دربازه زمانی مشخص شده، دارا باشد. الگوریتم آن لاینی که برای اختصاص دادن پرس و جو های جستجو در روش اول استفاده میشود، الگوریتم حریصانه آن لاین می باشد که به صورت زیر تعریف می شود:
تعریف الگوریتم: همانطور که از اسم این الگوریتم مشخص است برای بیشتر کردن میزان درآمد به صورت حریصانه عمل می کند. به این صورت که به ازای هر پرس و جوی جستجو روی یک کلمه از بین آگهی دهندگانی که روی آن کلمه قیمت پیشنهاد داده اند، آگهی شرکت یا فردی که بیشترین مبلغ را ارایه داده است و از میزان بودجه آن باقی مانده است، به جستجو اختصاص میدهد. برای بهتر مشخص شدن موضوع فرض کنید که دو آگهی دهنده داریم به نام های A و B. میزان بودجه هر دو برای بازه زمانی یک ماه مبلغ ۲۱۱۱۱۱ تومان است. آگهی دهنده A روی کلمه های “مبل” و “صندلی ” قیمت پیشنهادی ۱۱۱ تومان را داده است و آگهی دهنده B تنها روی کلمه “مبل” سرمایه گذاری کرده و مبلغ ۲۱۱ تومان را پیشنهاد داده است. اگر اولین پرس و جوی جستجو “مبل” باشد، الگوریتم حریصانه برای به دست آوردن درآمد بیشتر، آگهی مربوط به سازنده A را نمایش میدهد،زیرا قیمت بیشتری را پیشنهاد داده است. و به همین ترتیب الگوریتم حریصانه تا اتمام بودجه آگهی دهندگان و یا اتمام بازه زمانی به همین صورت عمل می کند.یعنی اگر برای حل این مساله از الگوریتم ارایه شده استفاده کنیم، حداقل نیمی از حداکثر درآمدی که در صورت حل مساله به صورت افلاین باید به دست آوریم را به دست می آوریم.