در زندگی همه ما بارها و بارها موقعیتهایی پیش میآید که باید در مورد آنها تصمیمگیری کنیم. انتخاب کلاس زبان از بین انبوه کلاسهای زبان، انتخاب رشته دانشگاه از بین رشتههای مختلف، انتخاب لپتاپ از بین انواع مدلهای مختلف، انتخاب نامزدهای شورای شهر از بین تعداد زیاد نامزدها، انتخاب آپارتمان از بین گزینههای موجود و… تنها، بخشی از این موقعیتها هستند که باید بهترین و باکیفیتترین گزینه ممکن را از میان تعداد زیاد گزینهها انتخاب کنیم.
در یکی از نوشتههای قبلی «پانویس»، با چند کاربرد ریاضی آشنا شدیم. در این نوشته میخواهیم ببینیم چطور میتوان از ریاضی برای انتخاب بهترین آپارتمان برای سکونت استفاده کرد. برای این کار باید ابتدا با «مساله منشی» یا همان Secretary problem آشنا شویم. این مساله صورت بسیار سادهای دارد و احتیاج به دانستن پیشنیاز خاصی از ریاضی ندارد:
فرض کنید مدیر شرکتی میخواهد بین n متقاضی برای پست منشیگری، بهترین منشی را انتخاب کند. متقاضیان با ترتیبی تصادفی، یک به یک مصاحبه میشوند. تصمیم درباره هر متقاضی، بلافاصله باید بعد از مصاحبه گرفته شود. هر متقاضیای که رد بشود، دوباره نمیتواند مصاحبه بدهد. در طول مصاحبه، مدیر میتواند متقاضی را با توجه به خصوصیات متقاضیان قبلی، درجهبندی کند؛ اما از کیفیت و توانایی متقاضیان باقیمانده بیاطلاع است. مساله این است که چطور میتوان احتمال انتخاب بهترین متقاضی را افزایش داد؟
قانونی در ریاضیات به نام «قانون توقف بهینه» یا Optimal stopping rule وجود دارد که پیشنهاد میکند تعداد n/e (که در آن، e پایه لگاریتم طبیعی بوده و مقدار آن تقریباً برابر 2.71828 است) از متقاضیان را بعد از مصاحبه رد کنیم و سپس اولین متقاضیای که بهتر از تمام متقاضیان مصاحبهشده تا آن لحظه است را برای پست منشیگری انتخاب کنیم. گاهی اوقات این راهکار، قانون توقف
1/e
نامیده میشود؛ چون احتمال توقف در بهترین انتخاب با این راهکار، برای مقادیر متوسط n، تقریباً برابر
1/e
است.
یکی از دلایل مشهور شدن مساله منشی این است که قانون توقف این مساله، ساده است و صرف نظر از اینکه تعداد متقاضیان، ۱۰۰ نفر یا ۱۰۰ میلیون نفر باشد، در حداقل ۳۷ درصد حالات، بهترین نامزد را انتخاب میکند که درصد کمی نیست. به بیانی دقیقتر، برای هر مقدار n، احتمال انتخاب بهترین نامزد با این قانون بهینهسازی، حداقل
1/e
است. منظور از نامزد در اینجا، متقاضیای است که از تمام متقاضیان مصاحبهشده قبلی بهتر باشد.
حال برمیگردیم به بحث اصلی؛ یعنی انتخاب بهترین آپارتمان برای زندگی. فرض میکنیم مدت قرارداد آپارتمانی که در حال حاضر در آن زندگی میکنیم تا چند ماه دیگر تمام میشود. پس باید دنبال آپارتمانی جدید برای اجاره کردن باشیم. از طریق پرسوجو از دوستان و یا آگهیهای سایتها و روزنامهها، ۲۶ آپارتمان را پیدا میکنیم که از بین آنها باید یکی را انتخاب کنیم. طبق مساله منشی، ۲۶ در اینجا همان n است. پس
26/e ≈ 9.6 ≈ 10
بنابراین به صورت تصادفی، به دیدن ۱۰ آپارتمان مختلف میرویم. بعد از دیدن آنها، طبق معیارهایی مثل مقدار فضای آپارتمان، ظاهر آپارتمان، هزینه اجاره، مکان قرارگیری آپارتمان، کیفیت مدرسههای اطراف آن که از قبل برای خودمان تعریف کردهایم و برایمان مهم هستند، آنها را درجهبندی میکنیم. حال چون دیدن ۱۶ آپارتمان باقیمانده، هم وقت، هم هزینه و هم حوصله زیادی میخواهد، از راهکار مساله منشی کمک میگیریم؛ بنابراین به دیدن یازدهمین آپارتمان میرویم. اگر این آپارتمان از تمام ۱۰ تای قبلی بهتر باشد، مساله منشی تضمین میکند که احتمال اینکه یازدهمین آپارتمان، از تمام ۲۶ آپارتمان بهتر باشد، حداقل ۳۷ درصد است که احتمال کمی نیست. دقت داشته باشید که اگر آپارتمان یازدهم از ۱۰ تای قبلی بهتر نباشد، سراغ آپارتمان دوازدهم میرویم و باز اگر این آپارتمان هم از ۱۱ تای قبلی بهتر نبود، سراغ آپارتمان سیزدهم میرویم.
نظر شما درباره این روش چیست؟ آیا حاضرید از این روش استفاده کنید؟
در نوشتههای بعدی این وبلاگ، باز هم درباره کاربردهای ریاضی خواهم نوشت. اگر میخواهید از انتشار این نوشتهها باخبر شوید، میتوانید به طور رایگان، مشترک خوراک «پانویس» و یا مشترک ایمیلی «پانویس» شوید. دقت داشته باشید که برای فعالسازی اشتراک ایمیلی، باید ایمیلی که از طرف وبلاگ برایتان فرستاده میشود را تأیید کنید.
منبع: + و +
لینک ثابت: https://panevis.ir/?p=1240
نوشتههای پیشنهادی
- معرفی کتاب: جن اعداد
- معرفی کتاب: برنامهنویسی شیگرا به زبان ++C
- جلسه اول کلاس؛ شانسی برای اثرگذاری مفید
- معرفی کتاب خود استاد به عنوان منبع درس: کاری اخلاقی یا غیراخلاقی؟
- پاسخ به چند سوال درباره دزدی علمی (۱)
- درخواست مقاله یا بخشی از یک کتاب از نویسنده آن
- چرا به دانشجو، نمره پاسی نمیدهم؟
- نظرسنجی: علت درس نخواندن دانشجویانم
شما در بالا گفتین که برای حالت منفی هم جواب میدهد.پس باید در کنترل کیفیت با همین فرمول معیوبترین رابتوان بدست آورد.
سلام مطلبتون خیلی جالب بود مرسی
مسأله زمان هم هست. احتمال اینکه خونه ای رو که الان دیدیم و پسند هم کردیم ولی میگیم حالا ببینیم شاید بهتر از اونم باشه مشتری دیگه ای نیاد قولنامه اش کنه. بنابراین از اون 26 خونه ای بسا 4 تاش معامله بشه. خب بیعانه هم بزاریم هر کدوم 20 تومن که نمیشه داد.
پیشفرض مسأله منشی اینه که در یک بازه زمانی خاص معامله ای صورت نگیره.
با سلام
ممنون بابت اين مطلب مفيد
37 درصد، شاید احتمال کمی نباشه ولی به دل نمیشینه. از 2/5 هم کمتره.
ضمن این که میتونیم به مسئله با دید متقارن نگاه کنیم یعنی به جای دادهی n/e دادهی n-n/e رو بررسی کنیم.
روش منطقی به نظر میرسه اما من از این راه خونمو انتخاب نمیکنم
یعنی میشه در نظر گرفت که از بین محصولات، بدترین رو انتخاب کنیم. یعنی بدترین حالت در مساله منشی! اگه شرایط مدنظر خودمون رو همه آیتم های بد در نظر بگیریم بازم میشه از این روش استفاده کرد؟ ( بعنی به نوعی برعکس مساله)
بله میشه برای انتخاب بدترین چیز هم از این مساله منشی استفاده کرد. برای اطمینان، این سوال رو در اینجــا هم پرسیدم و جواب، مثبت بود.
از دقت نظر شما بسیار متشکرم:-)
مطلب جالبی بود. ممنونم
خوب مسئله اینجاست شاید بازدید دلخواه از 10 تا آپارتمان در اختیار ما نباشه و به دلایلی مجبور بشیم 10 تا آپارتمان نزدیک به بنگاه رو بازدیدکنیم(مثلا از روی تنبلی شاگرد بنگاهی!). در این صورت اگه مثلا 5 تا آپارتمان در دورترین نقاط باشند که ما بازدید نکردیم چطور؟ ( این یعنی تو بازه احتمال 100-37 قرار میگیره؟)
یعنی باید به صورت رندوم و تصادفی بازدید کنیم؟
قبول کنید که احتمال اینکه معرف هر ۲۶ آپارتمان، یه بنگاه باشه، خیلی کمه. اگر هم باشه، بیشتر اوقات با گذاشتن یه ۱۰ تومنی کف دست شاگرد، میشه راضیش کرد:-)
بله دقیقاً. شرط اصلی این مساله اینه که اون n/e مورد اول رو کاملاً تصادفی انتخاب کنیم. اگر این کار صورت نگیره، مساله، هیچگونه شانسی برای بهترین انتخاب رو تضمین نمیکنه.
پس با این حساب به نظرتون میشه از این مسئله مثلا در مورد بازرسی و کنترل کیفی n تا محصول که باید مشابه باشند ولی احتمال خرابی در بین آنها میره، استفاده کرد؟
فرض کنید یه انبار رو تحویل دادن که یا علی مدد باید به صورت تصادفی کنترل بشه 🙂
تا اونجایی که من میدونم، هدف از کنترل کیفیت، تست کردن محصولات تولیدشده برای پیدا کردن محصولات معیوب هستش؛ نه پیدا کردن باکیفیتترین محصول؛ پس با توجه به اینکه هدف «مساله منشی»، پیدا کردن باکیفیتترین محصول هستش، به نظر میرسه که نمیشه از این محصول برای کنترل کیفیت استفاده کرد.
لطفاً اگر برداشت من از کنترل کیفیت، اشتباهه، اصلاحش کنید.