सचिव समस्या: Difference between revisions

* पद के लिए n आवेदक हैं और n का मान ज्ञात है।

* आवेदकों को यदि सभी को एक साथ देखा जाए तो उन्हें स्पष्ट रूप से सर्वश्रेष्ठ या सबसे खराब क्रम में रखा जा सकता है।

* आवेदकों का यादृच्छिक क्रम में क्रमिक रूप से साक्षात्कार किया जाता है जिसमें प्रत्येक आदेश समान रूप से होने की संभावना होती है।

* एक साक्षात्कार के तुरंत बाद साक्षात्कार के आवेदक को स्वीकार या अस्वीकार कर दिया जाता है और निर्णय अपरिवर्तनीय है।

* किसी आवेदक को स्वीकार या अस्वीकार करने का निर्णय अब तक साक्षात्कार किए गए आवेदकों के सापेक्ष पद पर ही आधारित हो सकता है।

* सामान्य समाधान का उद्देश्य पूरे समूह के सर्वश्रेष्ठ आवेदक के चयन की उच्चतम संभावना है यह अपेक्षित अदायगी को अधिकतम करने के समान है जिसमें अदायगी को सर्वश्रेष्ठ आवेदक के लिए एक और अन्यथा शून्य के रूप में परिभाषित किया गया है।

एक उम्मीदवार को एक आवेदक के रूप में परिभाषित किया जाता है जिसका साक्षात्कार होने पर पहले साक्षात्कार किए गए सभी आवेदकों से बेहतर होता है इसका मतलब साक्षात्कार के तुरंत बाद हटाना होता है जिससे समस्या का उद्देश्य एकल सर्वश्रेष्ठ आवेदक का चयन करना है इसलिए स्वीकृति के लिए केवल उम्मीदवारों पर विचार किया जाएगा इस संदर्भ में उम्मीदवार क्रम परिवर्तन में रिकॉर्ड की अवधारणा से मेल खाता है।

समस्या के लिए इष्टतम नीति एक रोक नियम है इसके तहत साक्षात्कारकर्ता पहले r − 1 आवेदकों अस्वीकार करता है और आवेदक M को इन r − 1 आवेदकों में से सबसे अच्छा आवेदक होने दें और फिर बाद में पहले आवेदक का चयन करसे जो आवेदक M से बेहतर होता है इसमें यह दिखाया जाता है कि इष्टतम रणनीतियों के इस वर्ग में निहित है आवेदक का चयन नहीं करना चाहिए जो अब तक हमने देखा है कि सबसे अच्छा आवेदक नहीं है क्योंकि वे समग्र रूप से सर्वश्रेष्ठ आवेदक नहीं हो सकते हैं एक मनमाना कटऑफ आर के लिए सबसे अच्छा आवेदक चुने जाने की संभावना है

राशि r = 1 के लिए परिभाषित नहीं है लेकिन ऐसे स्थानों में एकमात्र व्यवहार्य नीति पहले आवेदक का चयन करना है और P(1) = 1/n यह राशि इस बात को ध्यान में रखते हुए प्राप्त की जाती है कि यदि आवेदक i सबसे अच्छा आवेदक है तो इसे चुना जाता है और यदि अगर पहले i − 1 आवेदकों में से सबसे अच्छा आवेदक उन पहले r − 1 आवेदकों में से है जिन्हें अस्वीकार कर दिया गया था तो एन को अनंत की ओर ले जाने या लिखने के लिए <math>x</math> (r−1)/n की सीमा के रूप में (i−1)/n के लिए t और 1/n के लिए dt का उपयोग करके योग को समाकल द्वारा अनुमानित किया जा सकता है।

के संबंध में P(x) का अवकलन लेना <math>x</math> इसे 0 पर एकत्र करके और x के लिए हल करके हम पाते हैं कि इष्टतम x 1/e के बराबर है या नहीं इस प्रकार इष्टतम कटऑफ एन / ई के रूप में बढ़ता है और सबसे अच्छा आवेदक 1 / ई संभावना के साथ चुना जाता है।

n के छोटे मानों के लिए मानक [[गतिशील प्रोग्रामिंग|गतिशील]] कार्यक्रमिक विधियों द्वारा इष्टतम r भी प्राप्त किया जा सकता है इष्टतम आर और एन के कई मूल्यों के लिए सबसे अच्छा विकल्प पी चुनने की संभावना निम्न तालिका में दिखायी गयी है।

शास्त्रीय सचिव समस्या में सर्वश्रेष्ठ आवेदक के चयन की संभावना की ओर अभिसरण होता है। <math>1/e\approx 0.368</math>.

इस समस्या और कई संशोधनों को कठिनाई प्रारूप द्वारा सीधे तरीके से इष्टतमता के प्रमाण सहित हल किया जा सकता है जिसमें अन्य अनुप्रयोग भी हैं इस प्रारूप द्वारा हल की जा सकने वाली सचिव समस्या के लिए संशोधनों में आवेदकों की यादृच्छिक उपलब्धता आवेदकों के लिए अधिक सामाशा परिकल्पनाएं सम्मिलित हैं जो निर्णयकर्ता के लिए रुचिकर हों आवेदकों के लिए समूह साक्षात्कार साथ ही आवेदकों की यादृच्छिक संख्या के लिए कुछ प्रयुक्त आवेदक हैं।{{Citation needed|date=May 2022}}

सचिव समस्या का समाधान केवल तभी सार्थक है जब आवेदकों को नियोजित निर्णय रणनीति का कोई ज्ञान न हो क्योंकि शुरुआती आवेदकों के पास कोई मौका नहीं है और यह दिखाई भी नहीं दे सकता है।

शास्त्रीय सचिव समस्या के समाधान के अनुप्रयोगों के लिए एक महत्वपूर्ण दोष आवेदकों की संख्या <math> n </math> है जो इस समस्या को दूर करने का तरीका यह मान लेता है कि आवेदकों की संख्या एक यादृच्छिक चर है <math>N </math> के ज्ञात वितरण के साथ  <math>P(N=k)_{k=1,2,\cdots} </math> प्रेसमैन और सोनिन 1972 में इस प्रारूप के लिए इष्टतम समाधान सामान्य रूप से अधिक कठिन है इसके सफलता की संभावना अब 1/e के आसपास नहीं है लेकिन आमतौर पर कम है इसे आवेदकों की संख्या न जानने की कीमत चुकाने के संदर्भ में समझा जा सकता है जबकि इस प्रारूप में कीमत ज्यादा है यह इसके वितरण की पसंद पर निर्भर करता है <math>N</math>इष्टतम जीत संभावना शून्य तक पहुंच सकती है इस नई समस्या से निपटने के तरीकों की तलाश में एक नए प्रारूप का नेतृत्व किया गया जो तथाकथित 1/ई-कानून को सर्वोत्तम विकल्प प्रदान करता है।

प्रारूप का सार इस विचार पर आधारित है कि जीवन अनुक्रमिक है और वास्तविक दुनिया की समस्याएं वास्तविक समय में उत्पन्न होती हैं इसके अलावा ऐसे समय का अनुमान लगाना आसान होता है जिसमें विशिष्ट घटनाओं आवेदकों के आगमन को अधिक बार होना चाहिए यदि वे ऐसा करते हैं तो होने वाली विशिष्ट घटनाओं की संख्या के वितरण का अनुमान लगाने के जगह इस विचार ने निम्नलिखित दृष्टिकोण को जन्म दिया तथाकथित एकीकृत दृष्टिकोण 1984 में लागू हुआ।

प्रारूप को इस प्रकार परिभाषित किया गया है कि एक आवेदक को कुछ समय अंतराल पर चुना जाना चाहिए <math>[0,T]</math> किसी अनजान नंबर से <math> N</math> पद करने योग्य आवेदकों का लक्ष्य इस परिकल्पना के तहत केवल सर्वश्रेष्ठ का चयन करने की संभावना को अधिकतम करना है किसी विभिन्न पदों के सभी आगमन आदेशित समान रूप से होने की संभावना है मान लीजिए कि सभी आवेदकों का आगमन समय घनत्व समान है लेकिन एक-दूसरे से स्वतंत्र है <math>f</math> पर <math>[0,T]</math> और जाने  <math>F</math> इसी आगमन समय वितरण कार्यक्रम को निरूपित करें अर्थात्

<math>\tau</math> ऐसा हो कि <math> F(\tau)=1/e.</math> सभी आवेदक समय-समय पर प्रतीक्षा करने और निरीक्षण करने की रणनीति पर विचार करें <math>\tau </math> यदि संभव हो तो समय के बाद पहले उम्मीदवार का चयन करना <math>\tau </math> जो पिछले सभी से बेहतर है फिर इस रणनीति को जिसे 1/ई-रणनीति कहा जाता है इसमें निम्नलिखित गुण हैं

:(i) सभी के लिए पैदावार <math>N</math> कम से कम 1/e की सफलता की संभावना।

: (ii) चयनकर्ता के लिए एक न्यूनतम-इष्टतम रणनीति है जो <math>N</math>को नहीं जानता है।

:(iii) चयन करता है यदि कम से कम एक आवेदक हो जो 1/e संभावना के साथ कोई न हो।

एफ. थॉमस ब्रस द्वारा 1984 में सिद्ध किया गया पहला/ई-कानून एक आश्चर्य के रूप में सामने आया कारण यह था कि अज्ञात के लिए एक प्रारूप में पहुंच से बाहर होने से पहले लगभग 1/e के मान पर विचार किया गया था <math> N </math> जबकि यह मान 1/e अब सफलता की संभावना के लिए एक निचली सीमा के रूप में प्राप्त किया गया था और यह यकीनन बहुत कमजोर परिकल्पनाओं वाले प्रारूप में है उदाहरण के लिए समीक्षाएं 85: मिनट

जबकि कई अन्य रणनीतियाँ हैं जो (i) और (ii) प्राप्त करती हैं और इसके अलावा 1/ई-रणनीति की तुलना में सख्ती से बेहतर प्रदर्शन करती हैं एक साथ सभी के लिए <math>N</math>> 2। एक सरल उदाहरण वह रणनीति है जो समय के बाद या पहले अपेक्षाकृत सर्वश्रेष्ठ उम्मीद का चयन करती है यदि संभव हो जबकि <math>\tau </math> कम से कम एक आवेदक इस समय से पहले पहुंचे और समय के बाद दूसरे अपेक्षाकृत सर्वश्रेष्ठ उम्मीदवार का चयन करें {{sfn|Gnedin|2021}}

संख्या 1/ई की समान भूमिका के कारण 1/ई-कानून कभी-कभी ऊपर वर्णित शास्त्रीय सचिव समस्या के समाधान के साथ भ्रमित हो जाता है जबकि 1/ई-कानून में यह भूमिका अधिक सामान्य है परिणाम भी मजबूत है क्योंकि यह अज्ञात संख्या में आवेदकों के लिए है और चूंकि आगमन समय वितरण एफ पर आधारित प्रारूप अनुप्रयोगों के लिए अधिक हैं।

थॉमस एस. फर्ग्यूसन के अनुसार सचिव समस्या पहली बार छपाई में दिखाई दी जब इसे [[मार्टिन गार्डनर]] ने अपने फरवरी 1960 में [[ अमेरिकी वैज्ञानिक ]]में [[गणितीय खेल स्तंभ]] में चित्रित किया {{r|TomFer89}} यहां बताया गया है कि गार्डनर ने इसे कैसे तैयार किया किसी को कागज की जितनी चाहें उतनी पर्चियां लेने के लिए कहें और प्रत्येक पर्ची पर एक अलग सकारात्मक संख्या लिखें संख्याएँ 1 के छोटे अंशों से लेकर एक गोगोल के आकार की संख्या 1 के बाद सौ शून्य या इससे भी बड़ी हो सकती हैं इन पर्चियों को उल्टा कर दिया जाता है और एक मेज के ऊपर से फेर दिया जाता है एक समय में आप फिसलकर उल्टा कर देते हैं लक्ष्य यह है कि जब आप उस संख्या तक पहुंचें जिसे आप श्रृंखला में सबसे बड़ा मानते हैं तो मुड़ना बंद कर दें आप वापस नहीं जा सकते हैं और पहले से मुड़ी हुई पर्ची नहीं उठा सकते हैं यदि आप सभी पर्चियों को पलट देते हैं तो निश्चित रूप से आपको अंतिम मुड़ी हुई पर्चियों को चुनना चाहिए।{{sfn|Gardner|1966}}

लेख में सचिव समस्या का समाधान किसने किया फर्ग्यूसन ने बताया कि सचिव की समस्या अनसुलझी रही जैसा कि एम. गार्डनर ने कहा था जो दो विरोधी खिलाड़ियों के साथ दो-व्यक्ति शून्य-राशि के खेल के रूप में है {{r|TomFer89}} इस खेल में ऐलिस, सूचित खिलाड़ी, गुप्त रूप से अलग-अलग नंबर लिखता है <math>n</math> पत्ते बॉब, रोकने वाला खिलाड़ी, वास्तविक मूल्यों को देखता है और जब भी वह चाहता है तो कार्ड को बदलना बंद कर सकता है अगर आखिरी कार्ड बदल गया तो जीतना कुल अधिकतम संख्या है बुनियादी सचिव की समस्या से अंतर यह है कि बॉब कार्डों पर लिखे वास्तविक मूल्यों का अवलोकन करता है जिसका उपयोग वह अपनी निर्णय प्रक्रियाओं में कर सकता है सचिव समस्या के कुछ संस्करणों में कार्ड पर संख्या आवेदकों के संख्यात्मक गुणों के अनुरूप होती है संख्याओं का [[संयुक्त संभाव्यता वितरण]] ऐलिस के नियंत्रण में है।

बॉब उच्चतम संभव संभावना के साथ अधिकतम संख्या का अनुमान लगाना चाहता है जबकि ऐलिस का लक्ष्य इस संभावना को यथासंभव कम रखना है ऐलिस के लिए कुछ निश्चित वितरण से स्वतंत्र रूप से संख्याओं का नमूना लेना इष्टतम नहीं है और वह कुछ आश्रित तरीके से यादृच्छिक संख्याओं को चुनकर बेहतर खेल सकती है के लिए <math>n=2</math> ऐलिस की कोई न्यूनतम रणनीति नहीं है जो थॉमस एम. कवर टी के विरोधाभास से निकटता से संबंधित है  <math>n>2</math> खेल में एक समाधान है ऐलिस यादृच्छिक संख्या जो आश्रित यादृच्छिक चर हैं यह इस तरह से चुन सकता है कि बॉब सापेक्ष पदों के आधार पर शास्त्रीय रोक रणनीति का उपयोग करने से बेहतर नहीं खेल सकता।{{sfn|Gnedin|1994}}

{{harvnb|Stein|Seale|Rapoport|2003}} ने कई मनोवैज्ञानिक रूप से प्रशंसनीय अनुमानों के लिए अपेक्षित सफलता की संभावनाएँ प्राप्त कीं जिन्हें सचिव समस्या में नियोजित किया जा सकता है उन्होंने ह्यूरिस्टिक्स की जांच की थी

* कटऑफ नियम पहले y आवेदकों में से किसी को भी स्वीकार न करें इसके बाद पहले सामना करने वाले उम्मीदवार यानी सापेक्ष पद 1 वाला आवेदक का चयन करें इस नियम में एक विशेष स्थान के रूप में शास्त्रीय सचिव समस्या के लिए इष्टतम नीति है जिसके लिए y = r

*उम्मीदवार गणना नियम सीसीआर वाई-वें सामना करने वाले उम्मीदवार का चयन करें ध्यान दें कि यह नियम आवश्यक रूप से किसी भी आवेदक को छोड़ नहीं देता है यह केवल इस बात पर विचार करता है कि कितने उम्मीदवारों का अवलोकन किया गया है यह नहीं कि आवेदक अनुक्रम में निर्णय निर्माता कितना गहरा है।

* लगातार गैर-उम्मीदवार नियम एसएनसीआर वाई गैर-उम्मीदवारों यानी संबंधित पद वाले आवेदक > 1 का अवलोकन करने के बाद सबसे पहले सामना करने वाले उम्मीदवार का चयन करें ।

अनुमानी का एक एकल पैरामीटर y होता है आंकड़ा दाईं ओर दिखाया गया है n = 80 के साथ समस्याओं के लिए y के एक समारोह के रूप में प्रत्येक अनुमानी के लिए अपेक्षित सफलता की संभावनाएं प्रदर्शित करता है।

एकल सर्वश्रेष्ठ आवेदक ढूँढना एक सख्त उद्देश्य की तरह लग सकता है कोई कल्पना कर सकता है कि साक्षात्कारकर्ता एक कम-मूल्यवान आवेदक की तुलना में एक उच्च-मूल्यवान आवेदक को नियुक्त करेगा और न केवल सर्वश्रेष्ठ प्राप्त करने के लिए चिंतित होगा अर्थात् साक्षात्कारकर्ता एक आवेदक का चयन करने से कुछ मूल्य प्राप्त करेगा जो आवश्यक रूप से सर्वोत्तम नहीं है और व्युत्पन्न मूल्य चयनित के मूल्य के साथ बढ़ता है।

इस समस्या का प्रारूप बनाने के लिए मान लीजिए कि <math>n</math> आवेदकों के पास वास्तविक मूल्य हैं जो यादृच्छिक चर एक्स तैयार हैं 0, 1 पर एक [[समान वितरण (निरंतर)|समान वितरण निरंतर]] ऊपर वर्णित शास्त्रीय समस्या के समान साक्षात्कारकर्ता केवल यह देखता है कि क्या प्रत्येक आवेदक अब तक का सबसे अच्छा है एक उम्मीदवार प्रत्येक को मौके पर ही स्वीकार या अस्वीकार कर देना चाहिए और यदि वह पहुंच जाता है तो अंतिम को स्वीकार करना चाहिए साक्षात्कारकर्ता प्रत्येक आवेदक की वास्तविक सापेक्ष पद नहीं सीखता है वह केवल यह सीखता है कि आवेदक की सापेक्ष पद 1 है या नहीं जबकि इस संस्करण में भुगतान चयनित आवेदक के सही मूल्य द्वारा दिया गया है उदाहरण के लिए यदि वह एक आवेदक का चयन करता है जिसका सही मूल्य 0.8 है, तो वह 0.8 कमाएगा साक्षात्कारकर्ता का उद्देश्य चयनित आवेदक के [[अपेक्षित मूल्य]] को अधिकतम करना है।

चूंकि आवेदक के मान 0, 1 पर एक समान वितरण से प्राप्त करता है दिए गए tवें आवेदक का अपेक्षित मूल्य <math>x_{t}=\max\left\{x_1, x_2, \ldots, x_t\right\}</math> द्वारा दिया गया है