कर्मकार का एल्गोरिथम

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

दर्शाने $n$ चर की संख्या के रूप में और $L$ एल्गोरिथम में इनपुट के बिट्स की संख्या के रूप में, कर्मकार के एल्गोरिथम की आवश्यकता होती है $O(n^{3.5}L)$ संचालन चालू $O(L)$-डिजिट संख्या, की तुलना में $O(n^{6}L)$ दीर्घवृत्त एल्गोरिथम के लिए इस तरह के संचालन। कर्मकार के एल्गोरिदम का रनटाइम इस प्रकार है

$O(n^{3.5}L^{2}\cdot \log L\cdot \log \log L),$

Schönhage–Strassen एल्गोरिथम का उपयोग करना|FFT-आधारित गुणन (बिग ओ नोटेशन देखें)।

कर्मकार का एल्गोरिथ्म आंतरिक-बिंदु विधियों की श्रेणी में आता है: समाधान के लिए वर्तमान अनुमान सरल विधि के रूप में व्यवहार्य सेट की सीमा का पालन नहीं करता है, लेकिन व्यवहार्य क्षेत्र के आंतरिक भाग के माध्यम से चलता है, इष्टतम समाधान के सन्निकटन में सुधार करता है। प्रत्येक पुनरावृत्ति के साथ एक निश्चित अंश द्वारा और तर्कसंगत डेटा के साथ एक इष्टतम समाधान में अभिसरण।

एल्गोरिथम

मैट्रिक्स रूप में एक रैखिक प्रोग्रामिंग समस्या पर विचार करें:

maximize cTx
subject to	Ax ≤ b.

कर्मकार का एल्गोरिथ्म इष्टतमता की ओर अगली व्यवहार्य दिशा निर्धारित करता है और एक कारक द्वारा वापस मापता है 0 < γ ≤ 1. यह कई स्रोतों में वर्णित है। कर्मकार ने भी पद्धति का विस्तार किया है पूर्णांक बाधाओं और गैर उत्तल समस्याओं के साथ समस्याओं को हल करने के लिए।

Algorithm Affine-Scaling

चूंकि वास्तविक एल्गोरिथम बल्कि जटिल है, शोधकर्ताओं ने इसके अधिक सहज संस्करण की तलाश की, और 1985 में affine स्केलिंग विकसित की, कर्मकर के एल्गोरिथ्म का एक संस्करण जो affine परिवर्तन का उपयोग करता है जहां कर्मकर ने प्रक्षेपी ज्यामिति का उपयोग किया, केवल चार साल बाद महसूस करने के लिए कि उनके पास था 1967 में सोवियत संघ के गणितज्ञ आई। आई। डिकिन द्वारा प्रकाशित एक एल्गोरिथम को फिर से खोजा। Affine-Scaling विधि को संक्षेप में निम्नानुसार वर्णित किया जा सकता है। एफ़िन-स्केलिंग एल्गोरिदम, जबकि छोटे पैमाने की समस्याओं पर लागू होता है, बहुपद समय एल्गोरिदम नहीं है।

Input:  A, b, c, $x^{0}$, रोक कसौटी, γ. 

$k\leftarrow 0$ do while stopping criterion not satisfied $v^{k}\leftarrow b-Ax^{k}$ $D_{v}\leftarrow \operatorname {diag} (v_{1}^{k},\ldots ,v_{m}^{k})$ $h_{x}\leftarrow (A^{T}D_{v}^{-2}A)^{-1}c$ $h_{v}\leftarrow -Ah_{x}$ if $h_{v}\geq 0$ then

        असीमित वापसी
    अगर अंत     

$\alpha \leftarrow \gamma \cdot \min\{-v_{i}^{k}/(h_{v})_{i}\,\,|\,\,(h_{v})_{i}<0,\,i=1,\ldots ,m\}$ $x^{k+1}\leftarrow x^{k}+\alpha h_{x}$ $k\leftarrow k+1$

अंत करो

• "←" denotes assignment. For instance, "largest ← item" means that the value of largest changes to the value of item.
• "return" terminates the algorithm and outputs the following value.

उदाहरण

उदाहरण समाधान

रैखिक कार्यक्रम पर विचार करें

${\begin{array}{lrclr}{\text{maximize}}&x_{1}+x_{2}\\{\text{subject to}}&2px_{1}+x_{2}&\leq &p^{2}+1,&p=0.0,0.1,0.2,\ldots ,0.9,1.0.\end{array}}$

अर्थात् 2 चर हैं $x_{1},x_{2}$ और 11 बाधाओं के अलग-अलग मूल्यों के साथ जुड़े $p$. यह आंकड़ा एल्गोरिथम के प्रत्येक पुनरावृत्ति को लाल वृत्त बिंदुओं के रूप में दिखाता है। बाधाओं को नीली रेखाओं के रूप में दिखाया गया है।

पेटेंट विवाद - क्या गणित का पेटेंट कराया जा सकता है?

जिस समय उन्होंने एल्गोरिद्म का आविष्कार किया, करमाकर को आईबीएम ने कैलिफोर्निया में आईबीएम सैन जोस अनुसंधान प्रयोगशाला में पोस्टडॉक्टोरल फेलो के रूप में नियुक्त किया था। 11 अगस्त, 1983 को उन्होंने स्टैनफोर्ड विश्वविद्यालय में एल्गोरिदम की व्याख्या करते हुए एक सेमिनार दिया, जिसमें उनकी संबद्धता अभी भी आईबीएम के रूप में सूचीबद्ध है। 1983 के आते-आते करमाकर ने एटी एंड टी में काम करना शुरू कर दिया और 1984 एसीएम कम्प्यूटिंग के सिद्धांत पर संगोष्ठी (एसटीओसी, 30 अप्रैल - 2 मई, 1984 को आयोजित) में एटी एंड टी बेल लेबोरेटरीज को अपनी संबद्धता बताते हुए अपना पेपर जमा किया। एटी एंड टी के टेलीफोन नेटवर्क को अनुकूलित करने के लिए एल्गोरिदम लागू करने के बाद, उन्होंने महसूस किया कि उनका आविष्कार व्यावहारिक महत्व का हो सकता है। अप्रैल 1985 में, एटी एंड टी ने तुरंत अपने एल्गोरिथम पर पेटेंट के लिए आवेदन किया।

सॉफ्टवेयर पेटेंट के मुद्दे पर चल रहे विवाद के लिए पेटेंट अधिक ईंधन बन गया। इसने कई गणितज्ञों को असहज कर दिया, जैसे कि रोनाल्ड रिवेस्ट (स्वयं RSA (एल्गोरिदम) एल्गोरिथम पर पेटेंट धारकों में से एक), जिन्होंने यह राय व्यक्त की कि अनुसंधान इस आधार पर आगे बढ़ा कि एल्गोरिदम मुक्त होना चाहिए। पेटेंट वास्तव में दिए जाने से पहले ही, यह तर्क दिया गया था कि हो सकता है कि कोई पूर्व कला हो जो लागू हो। फिलिप गिल और अन्य सहित संख्यात्मक विश्लेषण में विशेषज्ञता रखने वाले गणितज्ञों ने दावा किया कि यदि मापदंडों को उपयुक्त रूप से चुना जाता है, तो करमाकर का एल्गोरिथ्म लॉगरिदमिक बाधा समारोह के साथ अनुमानित न्यूटन बैरियर विधि के बराबर है। कानूनी विद्वान एंड्रयू चिन की राय है कि गिल का तर्क त्रुटिपूर्ण था, क्योंकि वे जिस विधि का वर्णन करते हैं वह एक एल्गोरिथम का गठन नहीं करती है, क्योंकि इसके लिए उन मापदंडों के विकल्पों की आवश्यकता होती है जो विधि के आंतरिक तर्क से पालन नहीं करते हैं, लेकिन बाहरी मार्गदर्शन पर निर्भर करते हैं, अनिवार्य रूप से कर्मकार का एल्गोरिदम। इसके अलावा, कर्मकार के योगदान को सभी पूर्व कार्यों के आलोक में स्पष्ट नहीं माना जाता है, जिसमें फियाको-मैककॉर्मिक, गिल और अन्य शामिल हैं, जिन्हें साल्ट्ज़मैन ने उद्धृत किया है। अमेरिकी सीनेट में पेटेंट पर बहस हुई थी और करमाकर के काम की आवश्यक मौलिकता की पहचान के रूप में प्रदान किया गया U.S. Patent 4,744,028: मई 1988 में कुशल संसाधन आवंटन के लिए तरीके और उपकरण।

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

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

संदर्भ

• Adler, Ilan; Karmarkar, Narendra; Resende, Mauricio G.C.; Veiga, Geraldo (1989). "An Implementation of Karmarkar's Algorithm for Linear Programming". Mathematical Programming. 44 (1–3): 297–335. doi:10.1007/bf01587095. S2CID 12851754.
• Narendra Karmarkar (1984). "A New Polynomial Time Algorithm for Linear Programming", Combinatorica, Vol 4, nr. 4, p. 373–395.

| group5 = Metaheuristics | abbr5 = heuristic | list5 =

• Evolutionary algorithm
• Hill climbing
• Local search
• Simulated annealing
• Tabu search

| below =

• Software

}} | group5 =Metaheuuristic |abbr5 = heuristic | list5 =*विकासवादी एल्गोरिथ्म

• पहाड़ी की चढ़ाई
• स्थानीय खोज
• तैयार किए हुयी धातु पे पानी चढाने की कला
• तब्बू खोज

| below =* सॉफ्टवेयर

}}