कंप्यूटर वैज्ञानिकों ने किसी भी संख्या में लोगों के लिए एक निष्पक्ष पाई एल्गोरिदम विकसित किया है

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

पाई साझा करना वास्तविक जीवन के कार्यों की एक विस्तृत श्रृंखला के लिए एक रूपक है, जिसमें एक निश्चित निरंतर वस्तु को विभाजित करना शामिल है, चाहे वह एक केक या भूमि का टुकड़ा हो, ऐसे लोगों के बीच जो इसके गुणों को अलग तरह से महत्व देते हैं। एक चॉकलेट कोटिंग पसंद करता है, दूसरा क्रीम फूल चाहता है। बाइबिल के समय से, एक एल्गोरिथ्म को दो लोगों के बीच ऐसी वस्तु को विभाजित करने के लिए जाना जाता है, जैसे कि कोई अन्य से ईर्ष्या नहीं करेगा: एक व्यक्ति केक को उसके लिए दो समान भागों में विभाजित करता है, और दूसरा उनमें से एक को चुनता है। उत्पत्ति में, अब्राहम (जिसे अब्राम के नाम से जाना जाता है) और लूत ने भूमि को विभाजित करने के लिए इस पद्धति का उपयोग किया, जब इब्राहीम ने एक अलगाव का आविष्कार किया और लूत ने जॉर्डन और कनान के बीच चयन किया।

1960- « » . , 1995 [Steven Brams] - [Alan Taylor] -. «» , – «», , , .

- , « , -, », [एरियल प्रोकैसिया], कार्नेगी मेलन विश्वविद्यालय में एक कंप्यूटर वैज्ञानिक, स्प्लिडिट के रचनाकारों में से एक, घरेलू कार्यों से साझा किराये की फीस के लिए, कार्यों के उचित साझा करने के लिए एक मुफ्त ऑनलाइन टूल।

पिछले 50 वर्षों में, Procaccia सहित कई गणितज्ञों और कंप्यूटर वैज्ञानिकों ने खुद को आश्वस्त किया है कि एक केक को n भागों में विभाजित करने के लिए कोई सीमित उचित एल्गोरिथ्म नहीं है।

"यह कार्य था जिसने मुझे समान विभाजनों के क्षेत्र में ले गया," वाल्टर स्ट्रोमविस्ट कहते हैं[वाल्टर स्ट्रोमक्विस्ट], पेंसिल्वेनिया में ब्रिन मावरे कॉलेज में गणित के प्रोफेसर, जिन्होंने 1980 में केक-शेयरिंग समस्या में अच्छे परिणाम प्राप्त किए। "मेरा सारा जीवन मैंने सोचा था कि मैं अपने खाली समय में इस काम पर लौटूंगा और साबित करूंगा कि परिणाम का ऐसा विस्तार सिद्धांत रूप में असंभव है" ।

लेकिन, अप्रैल में, कंप्यूटर विज्ञान के दो विशेषज्ञों ने साझाकरण में प्रतिभागियों की संख्या के आधार पर ऑपरेटिंग समय के साथ केक के उचित साझाकरण के लिए एल्गोरिथ्म प्रकाशित करके इन अपेक्षाओं का खंडन किया , न कि उनकी व्यक्तिगत प्राथमिकताओं पर। कार्नेगी मेलन के एक वैज्ञानिक, 27 वर्षीय साइमन मैकेंजी , पीएचडी, ने 10 अक्टूबर को 57 वें वार्षिक IEEE कंप्यूटर साइंस बेसिक्स में अपना काम प्रस्तुत किया।

एल्गोरिथ्म बेहद जटिल है। एन प्रतिभागियों के बीच एक केक विभाजन को एन तक की आवश्यकता हो सकती है^{n n n n n} चरण, लगभग समान कटौती के साथ। यहां तक ​​कि प्रतिभागियों की एक छोटी संख्या के लिए, यह संख्या ब्रह्मांड में परमाणुओं की संख्या से अधिक है। लेकिन शोधकर्ताओं के पास पहले से ही एल्गोरिदम को सरल बनाने और तेज करने के लिए विचार हैं, न्यू साउथ वेल्स विश्वविद्यालय में एक 35 वर्षीय कंप्यूटर विज्ञान विशेषज्ञ , हरिस अजीज के अनुसार , जो ऑस्ट्रेलियाई डेटा अनुसंधान समूह Data61 में काम करता है। प्रोकैसिया के अनुसार, निष्पक्ष विभाजन

के सिद्धांत का अध्ययन करने वाले विशेषज्ञ इस पर विचार करते हैं "निश्चित रूप से दशकों के लिए सबसे अच्छा परिणाम है।"

केक के टुकड़े

अज़ीज़ और मैकेंज़ी एल्गोरिथ्म 1960 के दशक में गणितज्ञ जॉन सेल्फ्रिज और जॉन कॉनवे द्वारा स्वतंत्र रूप से आविष्कार की गई एक सुंदर प्रक्रिया पर आधारित है , जो आपको एक केक को तीन में विभाजित करने की अनुमति देता है।



यदि ऐलिस, बॉब, और चार्ली (ए, बी, सी) केक को विभाजित करना चाहते हैं, तो एल्गोरिथ्म चार्ली को केक को तीन टुकड़ों में विभाजित करने के साथ शुरू होता है जो उसके समान दिखते हैं। ऐलिस और बॉब उन टुकड़ों को चुनते हैं जिन्हें वे पसंद करते हैं। यदि वे अलग-अलग टुकड़े चुनते हैं - वॉइला, सभी को वही मिलता है जो वे चाहते हैं।

यदि ऐलिस और बॉब एक ​​टुकड़े को चुनते हैं, तो बॉब इस टुकड़े के एक छोटे से हिस्से को काट देता है ताकि टुकड़ा उसके दृष्टिकोण से, केक के दूसरे टुकड़े के बराबर हो जाए - एक वह जो बॉब दूसरे स्थान पर चुनेगा। कटे हुए अवशेषों को स्थगित कर दिया जाता है। अब ऐलिस को शेष तीन में से अपने लिए सबसे अच्छा टुकड़ा चुनना होगा, और फिर बॉब का चयन करेगा - इस शर्त के साथ कि वह उसके द्वारा काटे गए टुकड़े को ले जाएगा, यदि ऐलिस उसका चयन नहीं करता है। चार्ली को तीसरा टुकड़ा मिलता है।

नतीजतन, कोई भी किसी की भी कल्पना नहीं करता है। एलिस ने पहला चुना। बॉब को उसके बराबर मूल्य के दो टुकड़े मिले। चार्ली को तीन मूल टुकड़ों में से एक मिला, जिसे उन्होंने खुद काटा।

केवल एक छोटा कट-ऑफ रहता है। लेकिन इसे पहले एल्गोरिथ्म शुरू किए बिना और बिना खतना और विकल्पों के एक अंतहीन चक्र में गिरने के बिना विभाजित किया जा सकता है, क्योंकि चार्ली किसी भी मामले में अपने टुकड़े से संतुष्ट है - और यहां तक ​​कि अगर कटे हुए टुकड़े को मिला है, तो इसके लिए उपांग में पूरे शेष को प्राप्त होगा, के लिए चार्ली बेईमान नहीं लगेगा, क्योंकि कट टुकड़ा और शेष केक के टुकड़े के बराबर का टुकड़ा देगा - आखिरकार, उसने शुरुआत से ही इन टुकड़ों को काट दिया। अजीज और मैकेंज़ी ने चार्ली की स्थिति को "प्रमुख" बताया।

अब, यदि, उदाहरण के लिए, ऐलिस को कट टुकड़ा मिला, तो बॉब ने ट्रिम को तीन भागों में काट दिया, उसके दृष्टिकोण से बराबर, ऐलिस खुद के लिए इनमें से एक टुकड़े का चयन करता है, फिर चार्ली का चयन करता है, फिर बॉब का। हर कोई खुश है: ऐलिस ने पहले चुना, चार्ली को बॉब की तुलना में एक टुकड़ा बेहतर मिलता है (और वह परवाह नहीं करता है कि ऐलिस ने कितना लिया), और बॉब के दृष्टिकोण से, सभी तीन टुकड़े बराबर हैं।

ब्रह्म्स और टेलर ने अपने 1995 के एल्गोरिथ्म को विकसित करने के लिए "प्रभुत्व" संपत्ति (लेकिन एक अलग नाम के साथ) का उपयोग किया, लेकिन उन्होंने अपने विचार को तब तक समाप्त नहीं किया जब तक कि एक सीमित एल्गोरिथ्म दिखाई नहीं दिया। अगले 20 वर्षों में, किसी ने भी सबसे अच्छा परिणाम हासिल नहीं किया है। "और प्रयासों की कमी के कारण नहीं," प्रोकैसिया कहते हैं।

अनप्रोफेशनल केक डिवाइडर

जब अजीज और मैकेंज़ी (ए एंड एम) ने कुछ साल पहले इस कार्य को करने का फैसला किया, तो वे केक साझा करने के कार्य में नए थे। अजीज ने कहा, "हमारे पास उतने अनुभव नहीं थे जितने लोगों ने इस पर गहनता से काम किया।" "हालांकि यह आमतौर पर एक खामी है, हमारे मामले में यह एक फायदा था, क्योंकि हमने अलग तरह से सोचा था।"

A & M ने तीन प्रतिभागियों को खरोंच से विभाजित करने के कार्य का अध्ययन करके शुरू किया, और विश्लेषण के परिणामस्वरूप चार प्रतिभागियों के लिए एक सीमित निष्पक्ष एल्गोरिदम आया , जो पिछले साल उनके द्वारा प्रकाशित किया गया था।

वे तुरंत यह दिखाने में सक्षम नहीं थे कि चार से अधिक प्रतिभागियों की संख्या के लिए अपने एल्गोरिदम का विस्तार कैसे किया जाए, लेकिन उन्होंने उत्साहपूर्वक इस कार्य को लिया। अजीज कहते हैं, "चार प्रतिभागियों से संबंधित काम भेजने के बाद, हम वास्तव में काम को जल्दी जारी रखना चाहते थे, जब तक कि कोई अधिक अनुभवी और चतुर व्यक्ति इसे स्वतंत्र रूप से एन प्रतिभागियों के मामले में सामान्यीकृत न कर दे।" और लगभग एक साल के बाद, उनकी खोज सफल रही।

सेल्फ्रिज-कॉनवे एल्गोरिथ्म की तरह, एआईएम प्रोटोकॉल लगातार अलग-अलग प्रतिभागियों को केक को समान भागों में काटने के लिए प्रदान करता है, और दूसरों को केक के टुकड़ों को काटने और चुनने के लिए। लेकिन एल्गोरिथ्म में अन्य चरण भी हैं, उदाहरण के लिए, प्रतिभागियों के बीच प्रमुख संबंधों की संख्या बढ़ाने के लिए, विशेष तरीके से केक के टुकड़ों का आवधिक आदान-प्रदान।

ये रिश्ते A & M को कार्य की जटिलता को कम करने की अनुमति देते हैं। यदि, उदाहरण के लिए, तीन प्रतिभागी शेष पर हावी हैं, तो उन्हें पहले से ही केक के अपने टुकड़ों को खाने के लिए भेजा जा सकता है - वे इस बात से खुश होंगे कि चाहे जो बचा हो। इसके बाद, कम प्रतिभागी रहते हैं, और सीमित संख्या में ऐसे चरणों के बाद, हर कोई संतुष्ट होता है और पूरे केक को विभाजित किया जाता है।

"एल्गोरिथ्म की जटिलता को देखते हुए, यह कोई आश्चर्य की बात नहीं है कि इसे विकसित करने में इतना समय लगा।" लेकिन एएंडएम पहले से ही मानता है कि वे एल्गोरिथ्म को सरल बना सकते हैं ताकि इसे टुकड़ों के आदान-प्रदान की आवश्यकता न हो और सिर्फ ^{n n} चरणों में जगह ले सके । अजीज के अनुसार, वे पहले से ही इन परिणामों पर काम कर रहे हैं।

ब्राह्म ने चेतावनी दी कि एक सरल एल्गोरिथ्म में भी व्यावहारिक अनुप्रयोग नहीं होगा - आखिरकार, प्रतिभागियों द्वारा प्राप्त केक के टुकड़ों में केक के विभिन्न हिस्सों से कई छोटे टुकड़ों को शामिल किया जाएगा। यह दृष्टिकोण विशेष रूप से उपयोगी नहीं है यदि, उदाहरण के लिए, आप भूमि को विभाजित कर रहे हैं।

लेकिन गणित और कंप्यूटर वैज्ञानिकों के लिए जो समस्या का अध्ययन कर रहे हैं, नया परिणाम "पूरे विषय को हल करता है", स्ट्रोमक्विस्ट कहते हैं।

अब जब शोधकर्ताओं को पता है कि केक को सीमित संख्या में चरणों में विभाजित किया जा सकता है, तो अगले कदम के अनुसार, Procaccia के अनुसार, एईएम विधि द्वारा चरणों की संख्या पर ऊपरी सीमा और इसके लिए आवश्यक चरणों की संख्या पर निचली सीमा के बीच के अंतर को समझना है। प्रोकैसिया पहले ही साबित कर चुकी है कि केक के उचित पृथक्करण के लिए एल्गोरिथ्म n से कम में पास नहीं हो सकता है² चरण - लेकिन चरणों की संख्या ^{n n n n n} और यहां तक ​​कि n ^{n n} की तुलना में छोटी है ।

अजीज कहते हैं कि शोधकर्ताओं को अब यह पता लगाना है कि इस अंतर को कैसे कम किया जाए। "मुझे लगता है कि प्रगति दोनों दिशाओं में हो सकती है।"