مسئله منشی: تفاوت میان نسخه‌ها

از ویکی‌پدیا، دانشنامهٔ آزاد
محتوای حذف‌شده محتوای افزوده‌شده
ویژگی پیوندهای پیشنهادی: ۱ پیوند افزوده شد.
ابرابزار
خط ۲: خط ۲:


== مقدمه ==
== مقدمه ==
در اواخر دهه 1950 و اوایل دهه 1960 مسئله ای ظاهر شد که تا حدی تفریحی بود که به مسئله منشی یا ازدواج مشهور است.
در اواخر دهه ۱۹۵۰ و اوایل دهه ۱۹۶۰ مسئله ای ظاهر شد که تا حدی تفریحی بود که به مسئله منشی یا ازدواج مشهور است.


این مسئله برای نخستین بار در ستون بازی های ریاضی در یک مجله آمریکایی مطرح شد.
این مسئله برای نخستین بار در ستون بازی‌های ریاضی در یک مجله آمریکایی مطرح شد.


بیان مسئله آسان و راه حل آن قابل توجه است.میان آمار دانان و احتمال دانان چندین نفر از جمله لیندلی ، داینکین<ref>{{Cite journal|date=2018-08-09|title=Eugene Dynkin|url=https://en.wikipedia.org/w/index.php?title=Eugene_Dynkin&oldid=854216234|journal=Wikipedia|language=en}}</ref> ، چو ، موگریتی ،روبینز،ساموئلز،گیلبرت و موستلر <ref>{{Cite journal|date=2018-09-19|title=Frederick Mosteller|url=https://en.wikipedia.org/w/index.php?title=Frederick_Mosteller&oldid=860204717|journal=Wikipedia|language=en}}</ref> این مسئله را اخذ کردند و توسعه دادند.بعد از آن مسئله منشی فراگیر و عمومی تر شد که اکنون می توان به آن عنوان یک گرایش درسی بین ریاضیات،[[احتمال]] و [[بهینه‌سازی|بهینه سازی]] داد.
بیان مسئله آسان و راه حل آن قابل توجه است. میان آمار دانان و احتمال دانان چندین نفر از جمله لیندلی، داینکین،<ref>{{Cite journal|date=2018-08-09|title=Eugene Dynkin|url=https://en.wikipedia.org/w/index.php?title=Eugene_Dynkin&oldid=854216234|journal=Wikipedia|language=en}}</ref> چو، موگریتی، روبینز، ساموئلز، گیلبرت و موستلر<ref>{{Cite journal|date=2018-09-19|title=Frederick Mosteller|url=https://en.wikipedia.org/w/index.php?title=Frederick_Mosteller&oldid=860204717|journal=Wikipedia|language=en}}</ref> این مسئله را اخذ کردند و توسعه دادند. بعد از آن مسئله منشی فراگیر و عمومی تر شد که اکنون می‌توان به آن عنوان یک گرایش درسی بین ریاضیات، [[احتمال]] و [[بهینه‌سازی]] داد.


شکل استاندارد مسئله منشی به اینگونه است که <math>N</math> نفر برای منشی گری تقاضا می دهند و به طور تصادفی مرتب و یکی پس از دیگری مصاحبه می شوند. مصاحبه کننده در هر لحظه اطلاعات متقاضی های قبلی و متقاضی فعلی را دارد و باید در همان لحظه تصمیم بر انتخاب یا رد مصاحبه شونده بگیرد.
شکل استاندارد مسئله منشی به اینگونه است که <math>N</math> نفر برای منشی گری تقاضا می‌دهند و به‌طور تصادفی مرتب و یکی پس از دیگری مصاحبه می‌شوند. مصاحبه‌کننده در هر لحظه اطلاعات متقاضی‌های قبلی و متقاضی فعلی را دارد و باید در همان لحظه تصمیم بر انتخاب یا رد مصاحبه‌شونده بگیرد.


مصاحبه کننده امکان انتخاب کاندیدی که رد کرده است را ندارد و مصاحبه تا آن جایی ادامه می یابد که بهترین منشی را انتخاب کند.هدف این مسئله بالا بردن احتمال انتخاب بهترین متقاضی است.
مصاحبه‌کننده امکان انتخاب کاندیدی که رد کرده‌است را ندارد و مصاحبه تا آن جایی ادامه می‌یابد که بهترین منشی را انتخاب کند. هدف این مسئله بالا بردن احتمال انتخاب بهترین متقاضی است.


== صورت دقیق مسئله ==
== صورت دقیق مسئله ==
بیان مسئله منشی بسیار متنوع است امّا ساده ترین شکل آن به شرح زیر است:
بیان مسئله منشی بسیار متنوع است امّا ساده‌ترین شکل آن به شرح زیر است:
# تنها یک نفر برای موقعیت منشی نیاز است.
# تنها یک نفر برای موقعیت منشی نیاز است.
# تعداد متقاضیان مشخص و برابر <math>N</math> است.
# تعداد متقاضیان مشخص و برابر <math>N</math> است.
# متقاضیان که به شکل تصادفی مرتب شده‌اند ، به ترتیب مصاحبه می شوند.
# متقاضیان که به شکل تصادفی مرتب شده‌اند، به ترتیب مصاحبه می‌شوند.
# وضعیت متقاضیان بدین گونه است که می توان آن ها را از بدترین به بهترین رده بندی کرد و [[تصمیم‌گیری|تصمیم گیری]] در هر مرحله بر مبنای رده بندی متقاضیان قبلی است که رد شده اند.
# وضعیت متقاضیان بدین گونه است که می‌توان آن‌ها را از بدترین به بهترین رده‌بندی کرد و [[تصمیم‌گیری]] در هر مرحله بر مبنای رده‌بندی متقاضیان قبلی است که رد شده‌اند.
# متقاضی که رد شده است دوباره فراخوانده نمی‌شود.
# متقاضی که رد شده‌است دوباره فراخوانده نمی‌شود.
# مصاحبه کننده تنها در حالتی که بهترین منشی را انتخاب کند راضی می شود.
# مصاحبه‌کننده تنها در حالتی که بهترین منشی را انتخاب کند راضی می‌شود.


== حل مسئله ==
== حل مسئله ==
سیاست بهینه برای این مسئله ، قانون توقف است. بنابراین مصاحبه کننده ، <math>r-1</math> نفر اولِ متقاضیان را رد می کند (در حالی که متقاضی <math>M</math> ام بهترین بین <math>r-1</math> نفری باشد که رد شده اند) و پس از آن هر متقاضی ای که بهتر از متقاضی <math>M</math> ام بود را انتخاب میکند . احتمال انتخاب بهترین منشی به شکل زیر است:
سیاست بهینه برای این مسئله، قانون توقف است؛ بنابراین مصاحبه‌کننده ، <math>r-1</math> نفر اولِ متقاضیان را رد می‌کند (در حالی که متقاضی <math>M</math> ام بهترین بین <math>r-1</math> نفری باشد که رد شده‌اند) و پس از آن هر متقاضی ای که بهتر از متقاضی <math>M</math> ام بود را انتخاب می‌کند. احتمال انتخاب بهترین منشی به شکل زیر است:


متقاضی i ام انتخاب شود <math>A : </math>
متقاضی i ام انتخاب شود <math>A : </math>
خط ۲۸: خط ۲۸:
متقاضی i ام بهترین باشد <math>B : </math>
متقاضی i ام بهترین باشد <math>B : </math>


بهترین متقاضی بین <math>i-1</math> نفر اول ، از میان <math>r-1</math> نفر اول باشد <math>C : </math>
بهترین متقاضی بین <math>i-1</math> نفر اول، از میان <math>r-1</math> نفر اول باشد <math>C : </math>

{{چپ}}
{{چپ}}


خط ۴۲: خط ۴۲:
{{راست}}
{{راست}}
<math> n
<math> n
</math> را به بی نهایت میل می دهیم و <math> x
</math> را به بی‌نهایت میل می‌دهیم و <math> x
</math> را حد<math> \tfrac {r}{n}
</math> را حد<math> \tfrac {r}{n}
</math> میگیریم و <math> t
</math> می‌گیریم و <math> t
</math> را <math> \tfrac {i}{n}
</math> را <math> \tfrac {i}{n}
</math> و <math> dt
</math> و <math> dt
</math> را <math> \tfrac {1}{n}
</math> را <math> \tfrac {1}{n}
</math>میگیریم و مجموع به انتگرال تبدیل می شود:
</math>می‌گیریم و مجموع به انتگرال تبدیل می‌شود:


<math> P(x)= x\int_{x}^{1}{ \tfrac{1}{t}dt} =-xln(x)
<math> P(x)= x\int_{x}^{1}{ \tfrac{1}{t}dt} =-xln(x)
خط ۵۶: خط ۵۶:
</math>، مقدار بهینه <math> x
</math>، مقدار بهینه <math> x
</math>را برابر <math> \tfrac {1}{e}
</math>را برابر <math> \tfrac {1}{e}
</math>در می آوریم.با افزایش <math> n
</math>درمی‌آوریم. با افزایش <math> n
</math> ، برش مطلوب به <math> \tfrac {n}{e}
</math> ، برش مطلوب به <math> \tfrac {n}{e}
</math>میل می کند و احتمال انتخاب بهترین منشی تقریباً برابر با <math> \tfrac {1}{e}
</math>میل می‌کند و احتمال انتخاب بهترین منشی تقریباً برابر با <math> \tfrac {1}{e}
</math>است.
</math>است.


== کاربرد و مثال ==
== کاربرد و مثال ==
* می توان در استخدام برای هر گونه شغلی نه تنها منشی گری از آن استفاده نمود.
* می‌توان در استخدام برای هر گونه شغلی نه تنها منشی گری از آن استفاده نمود.
* در زمینه خرید خانه توجه به این مسئله اهمیت زیادی دارد.<ref>{{یادکرد وب|کد زبان=en-US|وبگاه=davidwees.com|نشانی=http://davidwees.com/content/how-i-used-mathematics-choose-my-next-apartment/|عنوان=How I used mathematics to choose my next apartment – The Reflective Educator|بازبینی=2018-10-28}}</ref>
* در زمینه خرید خانه توجه به این مسئله اهمیت زیادی دارد.<ref>{{یادکرد وب|کد زبان=en-US|وبگاه=davidwees.com|نشانی=http://davidwees.com/content/how-i-used-mathematics-choose-my-next-apartment/|عنوان=How I used mathematics to choose my next apartment – The Reflective Educator|بازبینی=2018-10-28}}</ref>
* برعکس استخدام، می توان از این مسئله برای انتخاب شغل استفاده کرد.
* برعکس استخدام، می‌توان از این مسئله برای انتخاب شغل استفاده کرد.
* خریدن یک کالا یا منتظر تخفیف بودن
* خریدن یک کالا یا منتظر تخفیف بودن
*مزایده در بازار
* مزایده در بازار


مسئله منشی زیر چتر مسائل توقف بهینه برای تعداد زیادی از شرایط دنیای واقعی اعمال می شود، در صورتی که دو شرط اولیه زیر را داشته باشند:
مسئله منشی زیر چتر مسائل توقف بهینه برای تعداد زیادی از شرایط دنیای واقعی اعمال می‌شود، در صورتی که دو شرط اولیه زیر را داشته باشند:
# اقلام، داده‌ها یا متقاضیان به‌طور پیوسته و پشت سر هم وارد می‌شوند.
# هر مورد مستقل هست و یکسان توزیع شده‌اند (<math>i.i.d</math>).


مثال دیگر می‌تواند مسئله دزدی باشد، بدین گونه که دزد، برنامه سرقت‌های سریالی دارد و اگر دستگیر شود، بازنشسته خواهد شد. او می‌خواهد تا قبل از دستگیری بازنشسته شود. امّا می‌خواهد بداند بعد از چند سرقت باید بازنشسته شود.
# اقلام ، داده ها یا متقاضیان به طور پیوسته و پشت سر هم وارد می شوند.
# هر مورد مستقل هست و یکسان توزیع شده اند (<math>i.i.d</math>).

مثال دیگر می تواند مسئله دزدی باشد، بدین گونه که دزد، برنامه سرقت های سریالی دارد و اگر دستگیر شود، بازنشسته خواهد شد. او می خواهد تا قبل از دستگیری بازنشسته شود. امّا می خواهد بداند بعد از چند سرقت باید بازنشسته شود.


و مثال دیگر سفارش گرفتن از مشتریان توسط یک شرکت که منابع محدودی دارد است.<ref>{{یادکرد وب|کد زبان=en|وبگاه=ResearchGate|نشانی=https://www.researchgate.net/publication/242097841_A_Survey_of_Secretary_Problem_and_its_Extensions|عنوان=(PDF) A Survey of Secretary Problem and its Extensions|بازبینی=2018-12-03}}</ref>
و مثال دیگر سفارش گرفتن از مشتریان توسط یک شرکت که منابع محدودی دارد است.<ref>{{یادکرد وب|کد زبان=en|وبگاه=ResearchGate|نشانی=https://www.researchgate.net/publication/242097841_A_Survey_of_Secretary_Problem_and_its_Extensions|عنوان=(PDF) A Survey of Secretary Problem and its Extensions|بازبینی=2018-12-03}}</ref>


<br />
== جستارهای وابسته ==
== جستارهای وابسته ==
این مسئله برای N نامشخص نیز مطرح می شود.
این مسئله برای N نامشخص نیز مطرح می‌شود.


اگر تعداد نامحدودی از «متقاضیان» وجود داشته باشد، همیشه بهتر است منتظر بمانیم تا بتوانیم یک مورد بهتر را پیدا کنیم. در این موارد باید تعداد کاندیدا ها تخمین زده شود و سپس بر <math>e</math> تقسیم شود. با مطالعه متقاضیان به طور تقریبی می توان به توزیع آنان پی برد و سپس تصمیم بهتری گرفت.<ref>{{یادکرد وب|وبگاه=Mathematics Stack Exchange|نشانی=https://math.stackexchange.com/questions/168417/secretary-problem-for-unknown-n|عنوان=Secretary problem for unknown n?|بازبینی=2018-12-03}}</ref>
اگر تعداد نامحدودی از «متقاضیان» وجود داشته باشد، همیشه بهتر است منتظر بمانیم تا بتوانیم یک مورد بهتر را پیدا کنیم. در این موارد باید تعداد کاندیداها تخمین زده شود و سپس بر <math>e</math> تقسیم شود. با مطالعه متقاضیان به‌طور تقریبی می‌توان به توزیع آنان پی برد و سپس تصمیم بهتری گرفت.<ref>{{یادکرد وب|وبگاه=Mathematics Stack Exchange|نشانی=https://math.stackexchange.com/questions/168417/secretary-problem-for-unknown-n|عنوان=Secretary problem for unknown n?|بازبینی=2018-12-03}}</ref>


== منابع ==
== منابع ==
{{پانویس|۲|چپ‌چین=بله}}
{{پانویس|۲|چپ‌چین=بله}}

* https://projecteuclid.org/download/pdf_1/euclid.ss/1177012493
* https://projecteuclid.org/download/pdf_1/euclid.ss/1177012493
** <nowiki>http://rs.io/the-secretary-problem-explained-dating/</nowiki><span dir="LTR"><nowiki>http://rs.io/the-secretary-problem-explained-dating/</nowiki></span>
** <nowiki>http://rs.io/the-secretary-problem-explained-dating/</nowiki><span dir="LTR"><nowiki>http://rs.io/the-secretary-problem-explained-dating/</nowiki></span>

نسخهٔ ‏۲۲ سپتامبر ۲۰۲۱، ساعت ۲۰:۰۷

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

مقدمه

در اواخر دهه ۱۹۵۰ و اوایل دهه ۱۹۶۰ مسئله ای ظاهر شد که تا حدی تفریحی بود که به مسئله منشی یا ازدواج مشهور است.

این مسئله برای نخستین بار در ستون بازی‌های ریاضی در یک مجله آمریکایی مطرح شد.

بیان مسئله آسان و راه حل آن قابل توجه است. میان آمار دانان و احتمال دانان چندین نفر از جمله لیندلی، داینکین،[۱] چو، موگریتی، روبینز، ساموئلز، گیلبرت و موستلر[۲] این مسئله را اخذ کردند و توسعه دادند. بعد از آن مسئله منشی فراگیر و عمومی تر شد که اکنون می‌توان به آن عنوان یک گرایش درسی بین ریاضیات، احتمال و بهینه‌سازی داد.

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

مصاحبه‌کننده امکان انتخاب کاندیدی که رد کرده‌است را ندارد و مصاحبه تا آن جایی ادامه می‌یابد که بهترین منشی را انتخاب کند. هدف این مسئله بالا بردن احتمال انتخاب بهترین متقاضی است.

صورت دقیق مسئله

بیان مسئله منشی بسیار متنوع است امّا ساده‌ترین شکل آن به شرح زیر است:

  1. تنها یک نفر برای موقعیت منشی نیاز است.
  2. تعداد متقاضیان مشخص و برابر است.
  3. متقاضیان که به شکل تصادفی مرتب شده‌اند، به ترتیب مصاحبه می‌شوند.
  4. وضعیت متقاضیان بدین گونه است که می‌توان آن‌ها را از بدترین به بهترین رده‌بندی کرد و تصمیم‌گیری در هر مرحله بر مبنای رده‌بندی متقاضیان قبلی است که رد شده‌اند.
  5. متقاضی که رد شده‌است دوباره فراخوانده نمی‌شود.
  6. مصاحبه‌کننده تنها در حالتی که بهترین منشی را انتخاب کند راضی می‌شود.

حل مسئله

سیاست بهینه برای این مسئله، قانون توقف است؛ بنابراین مصاحبه‌کننده ، نفر اولِ متقاضیان را رد می‌کند (در حالی که متقاضی ام بهترین بین نفری باشد که رد شده‌اند) و پس از آن هر متقاضی ای که بهتر از متقاضی ام بود را انتخاب می‌کند. احتمال انتخاب بهترین منشی به شکل زیر است:

متقاضی i ام انتخاب شود

متقاضی i ام بهترین باشد

بهترین متقاضی بین نفر اول، از میان نفر اول باشد

=

=

=[

=

را به بی‌نهایت میل می‌دهیم و را حد می‌گیریم و را و را می‌گیریم و مجموع به انتگرال تبدیل می‌شود:

با صفر گذاشتن مشتق ، مقدار بهینه را برابر درمی‌آوریم. با افزایش ، برش مطلوب به میل می‌کند و احتمال انتخاب بهترین منشی تقریباً برابر با است.

کاربرد و مثال

  • می‌توان در استخدام برای هر گونه شغلی نه تنها منشی گری از آن استفاده نمود.
  • در زمینه خرید خانه توجه به این مسئله اهمیت زیادی دارد.[۳]
  • برعکس استخدام، می‌توان از این مسئله برای انتخاب شغل استفاده کرد.
  • خریدن یک کالا یا منتظر تخفیف بودن
  • مزایده در بازار

مسئله منشی زیر چتر مسائل توقف بهینه برای تعداد زیادی از شرایط دنیای واقعی اعمال می‌شود، در صورتی که دو شرط اولیه زیر را داشته باشند:

  1. اقلام، داده‌ها یا متقاضیان به‌طور پیوسته و پشت سر هم وارد می‌شوند.
  2. هر مورد مستقل هست و یکسان توزیع شده‌اند ().

مثال دیگر می‌تواند مسئله دزدی باشد، بدین گونه که دزد، برنامه سرقت‌های سریالی دارد و اگر دستگیر شود، بازنشسته خواهد شد. او می‌خواهد تا قبل از دستگیری بازنشسته شود. امّا می‌خواهد بداند بعد از چند سرقت باید بازنشسته شود.

و مثال دیگر سفارش گرفتن از مشتریان توسط یک شرکت که منابع محدودی دارد است.[۴]

جستارهای وابسته

این مسئله برای N نامشخص نیز مطرح می‌شود.

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

منابع

  1. "Eugene Dynkin". Wikipedia (به انگلیسی). 2018-08-09.
  2. "Frederick Mosteller". Wikipedia (به انگلیسی). 2018-09-19.
  3. «How I used mathematics to choose my next apartment – The Reflective Educator». davidwees.com (به انگلیسی). دریافت‌شده در ۲۰۱۸-۱۰-۲۸.
  4. "(PDF) A Survey of Secretary Problem and its Extensions". ResearchGate (به انگلیسی). Retrieved 2018-12-03.
  5. «Secretary problem for unknown n?». Mathematics Stack Exchange. دریافت‌شده در ۲۰۱۸-۱۲-۰۳.