مسئله منشی

‏فرض کنید که مدیر یک شرکت خیلی معروف هستید و باید از بین متقاضیان زیادی که برای مصاحبه شرکت کردند، یک نفر را انتخاب کنید!

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

این مسئله یک معمای بسیار مشهور در زمینه تصمیم‌گیری و بهینه‌سازی است که هدف آن یافتن بهترین استراتژی ممکن در میان یک دنباله از گزینه‌ها است. این مسئله در اواخر دهه ۱۹۵۰ و اوایل دهه ۱۹۶۰ ظاهر شد و به عنوان یک بازی فکری برای آمارشناسان و علاقه‌مندان به علم ریاضی و احتمال شناخته شد.

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

شرایط مسئله :

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

راه حل:

سیاست حل این مسئله، قانون توقف است بنابراین مصاحبه کننده، r-1 نفراول متقاضیان را رد می کند ( درحالی که متقاضی M ام بهترین بین r-1 نفری باشد که رد شده اند) و پس از آن هر متقاضی ای که بهتر از متقاضی M بود را انتخاب می کند .
احتمال انتخاب بهترین منشی به شکل زیر است:
A: متقاضی i ام انتخاب شود / B : متقاضی i ام بهترین باشد / C : بهترین متقاضی بین i-1 نفراول ، از میان r-1 نفراول باشد


در ادامه n را به بی نهایت میل می دهیم و x را حد r/n می گیریم و t را i/n و dt را n ‏/1 می گیریم و مجموع به انتگرال تبدیل می شود.

با صفرگداشتن مشتق p(x) ، مقدار بهینه x را برابر (e)/1 درمی آوریم. با افزایش n برش مطلوب به n/e میل می کند و احتمال انتخاب بهترین منشی تقریبا برابر با (e)/1 است.

کاربرد آن در موضوعات دیگر:

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