क्रिस-क्रॉस कलन विधि

From Vigyanwiki
Revision as of 13:19, 6 May 2023 by alpha>Indicwiki (Created page with "{{Short description|Method for mathematical optimization}} {{About|an algorithm for mathematical optimization||Criss-cross (disambiguation){{!}}Criss-cross}} {{Use dmy dates|d...")
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
This article is about an algorithm for mathematical optimization. For other uses, see Criss-cross.

A three-डायमेंशनल क्यूब
क्रिस-क्रॉस एल्गोरिदम सबसे खराब स्थिति में क्ले-मिन्टी क्यूब के सभी 8 कोनों पर जाता है। यह औसतन 3 अतिरिक्त कोनों का दौरा करता है। क्ले-मिन्टी घन यहाँ दिखाए गए घन का एक क्षोभ है।

ऑप्टिमाइज़ेशन (गणित) में, क्रिस-क्रॉस कलन विधि रैखिक प्रोग्रामिंग के लिए एल्गोरिदम के परिवार में से कोई है। क्रिस-क्रॉस एल्गोरिथम के वेरिएंट भी रैखिक प्रोग्रामिंग और गैर-रैखिक प्रोग्रामिंग अनुकूलन (गणित) के साथ अधिक सामान्य समस्याओं को हल करते हैं; रैखिक-आंशिक प्रोग्रामिंग समस्याओं के लिए क्रिस-क्रॉस एल्गोरिदम हैं,[1][2] द्विघात प्रोग्रामिंग|द्विघात-प्रोग्रामिंग समस्याएं, और रैखिक संपूरकता समस्याएं।[3]

जॉर्ज डेंटजिग|जॉर्ज बी. डेंटजिग के सिंप्लेक्स एल्गोरिदम की तरह, क्रिस-क्रॉस एल्गोरिदम एक समय जटिलता नहीं है|रेखीय प्रोग्रामिंग के लिए बहुपद-समय एल्गोरिदम। दोनों एल्गोरिदम सभी 2 पर जाते हैंD आयाम D में एक (परेशान) इकाई घन के कोने, क्ले-मिन्टी घन (विक्टर क्ले और जॉर्ज जे. मिन्टी के बाद), सबसे खराब स्थिति वाली जटिलता में।[4][5]हालांकि, जब इसे एक यादृच्छिक कोने पर शुरू किया जाता है, तो क्रिस-क्रॉस एल्गोरिदम औसत-केस जटिलता|औसत विज़िट पर केवल डी अतिरिक्त कोने।[6][7][8] इस प्रकार, त्रि-आयामी घन के लिए, एल्गोरिथ्म सबसे खराब स्थिति में सभी 8 कोनों और औसतन ठीक 3 अतिरिक्त कोनों पर जाता है।

इतिहास

क्रिस-क्रॉस एल्गोरिथम स्वतंत्र रूप से तमस टेरलाकी द्वारा प्रकाशित किया गया था[9] और जेड और -मिन वांग नहीं;[10] संबंधित एल्गोरिदम अन्य लेखकों द्वारा अप्रकाशित रिपोर्ट में दिखाई दिए।[3]


रैखिक अनुकूलन के लिए सिंप्लेक्स एल्गोरिथ्म के साथ तुलना

See also: Linear programming, Simplex algorithm, and Bland's rule
अपने दूसरे चरण में, सिम्पलेक्स एल्गोरिथम पॉलीटॉप के किनारों पर तब तक क्रॉल करता है जब तक कि यह अंत में एक इष्टतम शीर्ष (ज्यामिति) तक नहीं पहुंच जाता। क्रिस-क्रॉस एल्गोरिथम उन आधारों पर विचार करता है जो शीर्षों से संबद्ध नहीं हैं, ताकि कुछ पुनरावृत्त संभव क्षेत्र के आंतरिक भाग में हो सकें, जैसे आंतरिक-बिंदु एल्गोरिदम; क्राइस-क्रॉस एल्गोरिथम संभव क्षेत्र के बाहर अव्यवहार्य पुनरावृति भी कर सकता है।

रैखिक प्रोग्रामिंग में, क्रिस-क्रॉस एल्गोरिथम आधारों के अनुक्रम के बीच पिवट करता है लेकिन सिंप्लेक्स एल्गोरिथम से भिन्न होता है। सिम्प्लेक्स एल्गोरिथम पहले चरण-एक समस्या को हल करके एक (प्राथमिक-) व्यवहार्य आधार पाता है; चरण दो में, सिंप्लेक्स एल्गोरिथम बुनियादी व्यवहार्य समाधानों के अनुक्रम के बीच पिवट करता है ताकि उद्देश्य फ़ंक्शन प्रत्येक पिवट के साथ घटता न हो, एक इष्टतम समाधान के साथ समाप्त हो (अंत में एक दोहरी व्यवहार्य समाधान भी ढूंढ रहा है)।[3][11]

क्रिस-क्रॉस एल्गोरिथम सिम्पलेक्स एल्गोरिथम की तुलना में सरल है, क्योंकि क्रिस-क्रॉस एल्गोरिथम में केवल एक चरण होता है। इसके धुरी नियम ब्लैंड के नियम के समान हैं। ब्लैंड के न्यूनतम-सूचकांक धुरी नियम।[12] योग्य पिवोट्स तय करते समय ब्लैंड का नियम उनके वास्तविक संख्या # स्वयंसिद्ध दृष्टिकोण के बजाय गुणांकों के केवल संकेत कार्यों का उपयोग करता है। ब्लैंड का नियम योग्य पिवोट्स के वास्तविक-संख्या क्रम का उपयोग करके कम लागत के मूल्यों की तुलना करके एक प्रवेश चर का चयन करता है।[12][13] ब्लैंड के नियम के विपरीत, क्रिस-क्रॉस एल्गोरिथम विशुद्ध रूप से संयोजी है, एक प्रवेश चर और एक छोड़ने वाले चर का चयन करते हुए उनके वास्तविक-संख्या क्रम के बजाय केवल गुणांक के संकेतों पर विचार करके।[3][11]क्रिस-क्रॉस एल्गोरिथम को रैखिक बीजगणित में बुनियादी परिणामों के रचनात्मक प्रमाण प्रस्तुत करने के लिए लागू किया गया है, जैसे कि भेड़िया लेम्मा.[14] जबकि अधिकांश सिंप्लेक्स वैरिएंट उद्देश्य में मोनोटोनिक होते हैं (सख्ती से गैर-पतित मामले में), क्रिस-क्रॉस एल्गोरिथम के अधिकांश वेरिएंट में एक मोनोटोन मेरिट फ़ंक्शन की कमी होती है जो व्यवहार में नुकसान हो सकता है।

विवरण

क्रिस-क्रॉस एल्गोरिथम एक मानक धुरी झांकी पर काम करता है (या झांकी के ऑन-द-फ्लाई परिकलित भागों, यदि संशोधित सिंप्लेक्स विधि की तरह लागू किया जाता है)। एक सामान्य चरण में, यदि झांकी प्रारंभिक या दोहरी अव्यवहार्य है, तो यह अनुक्रमणिका चयन नियम का उपयोग करके धुरी पंक्ति/स्तंभ के रूप में अव्यवहार्य पंक्तियों/स्तंभों में से एक का चयन करती है। एक महत्वपूर्ण संपत्ति यह है कि चयन अव्यवहार्य सूचकांकों के मिलन पर किया जाता है और एल्गोरिथम का मानक संस्करण स्तंभ और पंक्ति सूचकांकों में अंतर नहीं करता है (अर्थात, स्तंभ सूचकांक पंक्तियों में बुनियादी हैं)। यदि एक पंक्ति का चयन किया जाता है तो एल्गोरिथ्म दोहरे प्रकार के धुरी की स्थिति की पहचान करने के लिए सूचकांक चयन नियम का उपयोग करता है, जबकि यदि एक स्तंभ का चयन किया जाता है तो यह पंक्ति की स्थिति खोजने के लिए सूचकांक चयन नियम का उपयोग करता है और एक मूल प्रकार की धुरी करता है।

कम्प्यूटेशनल जटिलता: सबसे खराब और औसत मामले

File:Ellipsoid 2.png
खाचियान के दीर्घवृत्त एल्गोरिथम की सबसे खराब स्थिति कम्प्यूटेशनल जटिलता एक बहुपद है। क्रिस-क्रॉस एल्गोरिथम में घातीय जटिलता है।

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

लीनियर प्रोग्रामिंग के लिए कई एल्गोरिदम—खाचियान का दीर्घवृत्त एल्गोरिथ्म, करमरकर का कर्मकार का एल्गोरिद्म, और आंतरिक-बिंदु विधि |सेंट्रल-पाथ एल्गोरिदम—में बहुपद समय-जटिलता होती है (सबसे खराब स्थिति में जटिलता और इस प्रकार औसत केस जटिलता|औसत)। दीर्घवृत्ताकार और प्रक्षेपी एल्गोरिदम को क्रिस-क्रॉस एल्गोरिथम से पहले प्रकाशित किया गया था।

हालांकि, डेंटज़िग के सिंप्लेक्स एल्गोरिदम की तरह, क्रिस-क्रॉस एल्गोरिदम रैखिक प्रोग्रामिंग के लिए बहुपद-समय एल्गोरिदम नहीं है। Terlaky का क्रिस-क्रॉस एल्गोरिद्म सभी 2 पर जाता हैRoos के एक पेपर के अनुसार D आयाम D में एक (परेशान) घन के कोने; Roos का पेपर यूनिट क्यूब के विक्टर क्ले-मिन्टी निर्माण को संशोधित करता है, जिस पर सिम्पलेक्स एल्गोरिथम 2 लेता हैडी कदम।[3][4][5] सिम्पलेक्स एल्गोरिथम की तरह, क्रिस-क्रॉस एल्गोरिथम सबसे खराब स्थिति में त्रि-आयामी क्यूब के सभी 8 कोनों पर जाता है।

जब इसे घन के एक यादृच्छिक कोने में प्रारंभ किया जाता है, तो क्रिस-क्रॉस एल्गोरिदम केवल डी अतिरिक्त कोनों पर जाता है, हालांकि, फुकुदा, पुराना नाम और नमिकी द्वारा 1994 के पेपर के अनुसार।[6][7] तुच्छ रूप से, सिम्पलेक्स एल्गोरिद्म घन के लिए औसत डी चरण लेता है।[8][15] सिम्पलेक्स एल्गोरिथम की तरह, क्रिस-क्रॉस एल्गोरिथम औसतन तीन आयामी घन के ठीक 3 अतिरिक्त कोनों पर जाता है।

वेरिएंट

रेखीय प्रोग्रामिंग समस्याओं की तुलना में अधिक सामान्य समस्याओं को हल करने के लिए क्रिस-क्रॉस एल्गोरिथ्म का विस्तार किया गया है।

रैखिक बाधाओं के साथ अन्य अनुकूलन समस्याएं

रैखिक प्रोग्रामिंग के लिए, द्विघात प्रोग्रामिंग के लिए, और रैखिक पूरकता समस्या के लिए क्रिस-क्रॉस एल्गोरिथ्म के वेरिएंट हैं। पर्याप्त मैट्रिसेस के साथ रैखिक-पूरक समस्या;[3][6][16][17][18][19] इसके विपरीत, रैखिक संपूरकता समस्याओं के लिए, क्रिस-क्रॉस एल्गोरिथम केवल तभी समाप्त होता है जब मैट्रिक्स एक पर्याप्त मैट्रिक्स हो।[18][19]एक पर्याप्त मैट्रिक्स एक सकारात्मक-निश्चित मैट्रिक्स और एक पी-मैट्रिक्स दोनों का एक सामान्यीकरण है, जिसके प्रमुख नाबालिग प्रत्येक सकारात्मक हैं।[18][19][20] क्रिस-क्रॉस एल्गोरिथम को रैखिक-भिन्नात्मक प्रोग्रामिंग के लिए भी अनुकूलित किया गया है।[1][2]


वर्टेक्स गणना

क्रिस-क्रॉस एल्गोरिथम का उपयोग वर्टेक्स गणना समस्या के लिए एक एल्गोरिथम में किया गया था, जिसे 1992 में डेविड समीक्षाएं और कोमेई फुकुदा द्वारा प्रकाशित किया गया था।[21] एविस और फुकुदा ने एक एल्गोरिदम प्रस्तुत किया जो डी आयाम (वेक्टर स्पेस) में एन रैखिक असमानता की गैर-डीजेनेरेट प्रणाली द्वारा परिभाषित एक बहुतल के वी कोने ढूंढता है (या, दोहरे रूप से, डी आयामों में एन बिंदुओं के उत्तल पतवार के वी पहलू, जहां प्रत्येक फलक में सटीक रूप से दिए गए D बिंदु होते हैं) समय में बिग ओह नोटेशन (nDv) और O(nD) अंतरिक्ष जटिलता।[22]


ओरिएंटेड मैट्रोइड्स

मैक्स-फ्लो मिन-कट प्रमेय बताता है कि नेटवर्क के माध्यम से अधिकतम प्रवाह इसकी न्यूनतम कट की क्षमता है। उन्मुख मैट्रोइड्स के लिए क्रिस-क्रॉस एल्गोरिदम का उपयोग करके इस प्रमेय को सिद्ध किया जा सकता है।

क्रिस-क्रॉस एल्गोरिथम का अध्ययन अक्सर उन्मुख matroid (ओएम) के सिद्धांत का उपयोग करके किया जाता है, जो कि रैखिक-अनुकूलन सिद्धांत का एक संयोजी सार है।[17][23] दरअसल, ब्लैंड का पिवोटिंग नियम ओरिएंटेड-मैट्रॉइड थ्योरी पर उनके पिछले पेपर्स पर आधारित था। हालाँकि, ब्लैंड का नियम कुछ ओरिएंटेड-मैट्रोइड रैखिक-प्रोग्रामिंग समस्याओं पर साइकिल चलाना प्रदर्शित करता है।[17]लीनियर प्रोग्रामिंग के लिए पहला विशुद्ध रूप से मिश्रित एल्गोरिथम माइकल जे. टॉड (गणितज्ञ) | माइकल जे. टॉड द्वारा तैयार किया गया था।[17][24]टोड के एल्गोरिथ्म को न केवल उन्मुख मैट्रोइड्स की सेटिंग में रैखिक-प्रोग्रामिंग के लिए विकसित किया गया था, बल्कि द्विघात प्रोग्रामिंग | द्विघात-प्रोग्रामिंग समस्याओं और रैखिक पूरकता समस्या | रैखिक-पूरक समस्याओं के लिए भी विकसित किया गया था।[17][24] टोड का एल्गोरिदम यहां तक ​​​​कि राज्य के लिए जटिल है, दुर्भाग्य से, और इसके परिमित-अभिसरण प्रमाण कुछ जटिल हैं।[17]

क्रिस-क्रॉस एल्गोरिथम और इसके परिमित समाप्ति के प्रमाण को सरलता से कहा जा सकता है और उन्मुख मैट्रोइड्स की सेटिंग को आसानी से बढ़ाया जा सकता है। रैखिक व्यवहार्यता समस्याओं के लिए एल्गोरिथ्म को और सरल बनाया जा सकता है, जो कि रैखिक असमानताओं के साथ रैखिक प्रणालियों के लिए है; इन समस्याओं को उन्मुख मैट्रोइड्स के लिए तैयार किया जा सकता है।[14] क्राइस-क्रॉस एल्गोरिथ्म को उन समस्याओं के लिए अनुकूलित किया गया है जो रैखिक प्रोग्रामिंग की तुलना में अधिक जटिल हैं: द्विघात-प्रोग्रामिंग समस्या और रैखिक-पूरक समस्या के लिए ओरिएंटेड-मैट्रॉइड वेरिएंट भी हैं।[3][16][17]


सारांश

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

शोधकर्ताओं ने रेखीय-भिन्नात्मक प्रोग्रामिंग सहित कई अनुकूलन-समस्याओं के लिए क्रिस-क्रॉस एल्गोरिथम का विस्तार किया है। क्रिस-क्रॉस एल्गोरिथम ओरिएंटेड मैट्रोइड्स की सेटिंग में भी द्विघात प्रोग्रामिंग समस्याओं और रैखिक पूरकता समस्याओं को हल कर सकता है। सामान्यीकृत होने पर भी, क्रिस-क्रॉस एल्गोरिथम सरल रूप से कहा जाता है।

यह भी देखें

  • जैक एडमंड्स (कॉम्बिनेटरियल ऑप्टिमाइज़ेशन और ओरिएंटेड-मैट्रॉइड थिओरिस्ट के अग्रणी; कोमेई फुकुदा के डॉक्टरेट सलाहकार)

टिप्पणियाँ

  1. ↑ 1.0 1.1 Illés, Szirmai & Terlaky (1999)
  2. ↑ 2.0 2.1 Stancu-Minasian, I. M. (August 2006). "आंशिक प्रोग्रामिंग की छठी ग्रंथ सूची". Optimization. 55 (4): 405–428. doi:10.1080/02331930600819613. MR 2258634. S2CID 62199788.
  3. ↑ 3.0 3.1 3.2 3.3 3.4 3.5 3.6 Fukuda & Terlaky (1997)
  4. ↑ 4.0 4.1 Roos (1990)
  5. ↑ 5.0 5.1 Klee, Victor; Minty, George J. (1972). "How good is the simplex algorithm?". In Shisha, Oved (ed.). Inequalities III (Proceedings of the Third Symposium on Inequalities held at the University of California, Los Angeles, Calif., September 1–9, 1969, dedicated to the memory of Theodore S. Motzkin). New York-London: Academic Press. pp. 159–175. MR 0332165.
  6. ↑ 6.0 6.1 6.2 Fukuda & Terlaky (1997, p. 385)
  7. ↑ 7.0 7.1 Fukuda & Namiki (1994, p. 367)
  8. ↑ 8.0 8.1 The simplex algorithm takes on average D steps for a cube. Borgwardt (1987): Borgwardt, Karl-Heinz (1987). The simplex method: A probabilistic analysis. Algorithms and Combinatorics (Study and Research Texts). Vol. 1. Berlin: Springer-Verlag. pp. xii+268. ISBN 978-3-540-17096-9. MR 0868467.
  9. ↑ Terlaky (1985) and Terlaky (1987)
  10. ↑ Wang (1987)
  11. ↑ 11.0 11.1 Terlaky & Zhang (1993)
  12. ↑ 12.0 12.1 Bland, Robert G. (May 1977). "New finite pivoting rules for the simplex method". Mathematics of Operations Research. 2 (2): 103–107. doi:10.1287/moor.2.2.103. JSTOR 3689647. MR 0459599.
  13. ↑ Bland's rule is also related to an earlier least-index rule, which was proposed by Katta G. Murty for the linear complementarity problem, according to Fukuda & Namiki (1994).
  14. ↑ 14.0 14.1 Klafszky & Terlaky (1991)
  15. ↑ More generally, for the simplex algorithm, the expected number of steps is proportional to D for linear-programming problems that are randomly drawn from the Euclidean unit sphere, as proved by Borgwardt and by Smale.
  16. ↑ 16.0 16.1 Fukuda & Namiki (1994)
  17. ↑ 17.0 17.1 17.2 17.3 17.4 17.5 17.6 Björner, Anders; Las Vergnas, Michel; Sturmfels, Bernd; White, Neil; Ziegler, Günter (1999). "10 Linear programming". ओरिएंटेड मैट्रोइड्स. Cambridge University Press. pp. 417–479. doi:10.1017/CBO9780511586507. ISBN 978-0-521-77750-6. MR 1744046.
  18. ↑ 18.0 18.1 18.2 den Hertog, D.; Roos, C.; Terlaky, T. (1 July 1993). "रैखिक संपूरकता समस्या, पर्याप्त मैट्रिक्स और क्रिस-क्रॉस विधि" (PDF). Linear Algebra and Its Applications. 187: 1–14. doi:10.1016/0024-3795(93)90124-7.
  19. ↑ 19.0 19.1 19.2 Csizmadia, Zsolt; Illés, Tibor (2006). "पर्याप्त मैट्रिसेस के साथ रैखिक संपूरकता समस्याओं के लिए नए क्रिस-क्रॉस प्रकार के एल्गोरिदम" (pdf). Optimization Methods and Software. 21 (2): 247–266. doi:10.1080/10556780500095009. MR 2195759. S2CID 24418835.
  20. ↑ Cottle, R. W.; Pang, J.-S.; Venkateswaran, V. (March–April 1989). "पर्याप्त मैट्रिक्स और रैखिक संपूरकता समस्या". Linear Algebra and Its Applications. 114–115: 231–249. doi:10.1016/0024-3795(89)90463-1. MR 0986877.
  21. ↑ Avis & Fukuda (1992, p. 297)
  22. ↑ The v vertices in a simple arrangement of n hyperplanes in D dimensions can be found in O(n2Dv) time and O(nD) space complexity.
  23. ↑ The theory of oriented matroids was initiated by R. Tyrrell Rockafellar. (Rockafellar 1969):

    Rockafellar, R. T. (1969). "The elementary vectors of a subspace of (1967)" (PDF). In R. C. Bose and T. A. Dowling (ed.). Combinatorial Mathematics and its Applications. The University of North Carolina Monograph Series in Probability and Statistics. Chapel Hill, North Carolina: University of North Carolina Press. pp. 104–127. MR 0278972. PDF reprint.

    Rockafellar was influenced by the earlier studies of Albert W. Tucker and George J. Minty. Tucker and Minty had studied the sign patterns of the matrices arising through the pivoting operations of Dantzig's simplex algorithm.
  24. ↑ 24.0 24.1 Todd, Michael J. (1985). "ओरिएंटेड मैट्रोइड्स में रैखिक और द्विघात प्रोग्रामिंग". Journal of Combinatorial Theory. Series B. 39 (2): 105–133. doi:10.1016/0095-8956(85)90042-5. MR 0811116.


संदर्भ


बाहरी संबंध

| group5 = Metaheuristics | abbr5 = heuristic | list5 =

| below =

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

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

}}

Retrieved from ‘https://www.vigyanwiki.in/index.php?title=क्रिस-क्रॉस_कलन_विधि&oldid=175163’