द्विघात असाइनमेंट समस्या: Difference between revisions
From Vigyanwiki
No edit summary |
No edit summary |
||
| Line 1: | Line 1: | ||
{{Short description|Combinatorial optimization problem}} | {{Short description|Combinatorial optimization problem}} | ||
द्विघात | '''द्विघात मानांकन समस्या''' (क्यूएपी) मुख्य रूप से ऑप्टिमाइज़ेशन (गणित) या गणित में संचालन होने वाले अनुसंधान की शाखा में मूलभूत संयोजन अनुकूलन समस्याओं में से प्रमुख है, जो कि कोपमैन्स और बेकमैन द्वारा पहली बार प्रारंभ की गई सुविधाओं की स्थान समस्याओं की श्रेणी से है।<ref>Koopmans TC, Beckmann M (1957). Assignment problems and the location of economic activities. Econometrica 25(1):53-76</ref> इस प्रकारी की समस्याएं निम्नलिखित वास्तविक जीवन की समस्याओं का प्रारूप तैयार करती है। | ||
:n सुविधाओं | :यहाँ पर n सुविधाओं और स्थानों का समुच्चय है। इस प्रकार स्थानों की प्रत्येक जोड़ी के लिए एक सीमित दूरी निर्दिष्ट की जाती है और प्रत्येक जोड़ी सुविधाओं के लिए वजन या प्रवाह निर्दिष्ट किया जाता है, उदाहरण के लिए, दो सुविधाओं के बीच परिवहन की गई आपूर्ति की मात्रा इसका प्रमुख उदाहरण हैं। इस प्रकार की समस्याओं से संबंधित प्रवाह द्वारा गुणा की जाने वाली दूरियों के योग को कम करने के इस लक्ष्य के साथ सभी सुविधाओं को विभिन्न स्थानों पर आवंटित रहती है। | ||
सहजता से, इस प्रकार के लागत फ़ंक्शन एक-दूसरे के बीच उच्च प्रवाह वाली सुविधाओं को एक-दूसरे के समीप रखने के लिए प्रोत्साहित किए जाते हैं। | |||
समस्या कथन [[असाइनमेंट समस्या]] से मिलता | इस प्रकार की समस्या से जुड़े कथन के फलस्वरूप [[असाइनमेंट समस्या|मानांकन समस्या]] से मिलता जुलता है, इसके अतिरिक्त हानि फलन द्विघात असमानताओं के संदर्भ में व्यक्त किया जाता है। | ||
==औपचारिक गणितीय परिभाषा== | ==औपचारिक गणितीय परिभाषा== | ||
द्विघात | द्विघात मानांकन समस्या की औपचारिक परिभाषा इस प्रकार है: | ||
: समान आकार के दो | : समान आकार के दो समुच्चय, P (सुविधाएं) और L (स्थान), [[वजन समारोह|भार फलन]] w: P × P → '[[वास्तविक संख्या]]' और दूरी फ़ंक्शन d: L × L → 'वास्तविक संख्या' के साथ दिए गए हैं। इसके आक्षेप f : P → L (मानांकन) इस प्रकार खोजें कि लागत फलन को प्रदर्शित करता हैं: | ||
::<math>\sum_{a,b\in P}w(a,b)\cdot d(f(a), f(b))</math> | ::<math>\sum_{a,b\in P}w(a,b)\cdot d(f(a), f(b))</math> | ||
:न्यूनतम किया गया | :यहाँ इसका न्यूनतम मान प्रदर्शित किया गया है। | ||
सामान्यतः वजन और दूरी के कार्यों को वर्गाकार वास्तविक मान वाले [[मैट्रिक्स (गणित)|आव्यूह (गणित)]] के रूप में देखा जाता है, जिससे कि लागत फ़ंक्शन को इस प्रकार लिखा जाता हैं: | |||
:<math>\sum_{a,b\in P}w_{a,b}d_{f(a),f(b)}</math> | :<math>\sum_{a,b\in P}w_{a,b}d_{f(a),f(b)}</math> | ||
आव्यूह संकेतन में: | |||
:<math>\min_{X\in\Pi_n} \operatorname{trace}(WXDX^T)</math> | :<math>\min_{X\in\Pi_n} \operatorname{trace}(WXDX^T)</math> | ||
जहाँ <math>\Pi_n</math> मुख्य रूप से <math>n \times n</math> समुच्चय है, इसके अनुसार क्रमपरिवर्तन आव्यूह, <math>W</math> मुख्यतः भार आव्यूह को प्रदर्शित करता है और <math>D</math> दूरी आव्यूह को प्रदर्शित करती है। | |||
== कम्प्यूटेशनल जटिलता == | == कम्प्यूटेशनल जटिलता == | ||
समस्या [[ एनपी कठिन |एनपी | यहाँ पर यह समस्या [[ एनपी कठिन |एनपी]] के लिए जटिल रहती है, इसलिए इस बहुपद के लिए उचित समय में इस समस्या को हल करने के लिए कोई ज्ञात [[कलन विधि]] नहीं है, और यहां तक कि छोटे उदाहरणों के लिए भी लंबे गणना समय की आवश्यकता हो सकती है। यह भी सिद्ध हुआ कि समस्या में किसी भी (स्थिर) कारक के लिए बहुपद समय में चलने वाला सन्निकटन एल्गोरिदम नहीं है, जब तक कि P = NP के समान न हो जाये।<ref>{{Cite journal|title = P-Complete Approximation Problems | ||
|last1 = Sahni|first1 = Sartaj | |last1 = Sahni|first1 = Sartaj | ||
|last2 = Gonzalez |first2 = Teofilo | |last2 = Gonzalez |first2 = Teofilo | ||
| Line 35: | Line 34: | ||
|pages = 555–565 | |pages = 555–565 | ||
|journal = Journal of the ACM|doi = 10.1145/321958.321975|hdl = 10338.dmlcz/103883 | |journal = Journal of the ACM|doi = 10.1145/321958.321975|hdl = 10338.dmlcz/103883 | ||
|hdl-access = free}}</ref> [[ट्रैवलिंग सेल्समैन की समस्या]] (टीएसपी) को क्यूएपी के विशेष | |hdl-access = free}}</ref> इस प्रकार [[ट्रैवलिंग सेल्समैन की समस्या]] (टीएसपी) को क्यूएपी के विशेष स्थिति के रूप में देखा जा सकता है, यदि यह कोई मानता है कि प्रवाह सभी सुविधाओं को केवल वलय के साथ जोड़ता है, इसके आधार पर सभी प्रवाह का गैर-शून्य (स्थिर) मान समान है, और सभी दूरियां समान होती हैं, इसके आधार पर टीएसपी उदाहरण की संबंधित दूरी को प्रकट करती हैं। इसके मानक संयोजन के आधार पर अनुकूलन समस्याओं की कई अन्य समस्याओं को इस रूप में लिखा जा सकता है। | ||
== अनुप्रयोग == | == अनुप्रयोग == | ||
मूल संयंत्र स्थान सूत्रीकरण के | मूल संयंत्र स्थान सूत्रीकरण के अतिरिक्त, क्यूएपी [[मुद्रित सर्किट बोर्ड]] या एकीकृत सर्किट पर परस्पर जुड़े [[इलेक्ट्रॉनिक घटक|इलेक्ट्रॉनिक घटकों]] की नियुक्ति की समस्या के लिए गणितीय प्रारूप है, जो इलेक्ट्रॉनिक्स में [[कंप्यूटर एडेड डिजाइन]] के [[स्थान और मार्ग|स्थान और मूल]] चरण का भाग है। | ||
==यह भी देखें== | ==यह भी देखें== | ||
*[[द्विघात बाधा असाइनमेंट समस्या]] | *[[द्विघात बाधा असाइनमेंट समस्या|द्विघात समस्या के मूल्यांकन से जुड़ी समस्या]] | ||
== संदर्भ == | == संदर्भ == | ||
Revision as of 22:32, 10 August 2023
द्विघात मानांकन समस्या (क्यूएपी) मुख्य रूप से ऑप्टिमाइज़ेशन (गणित) या गणित में संचालन होने वाले अनुसंधान की शाखा में मूलभूत संयोजन अनुकूलन समस्याओं में से प्रमुख है, जो कि कोपमैन्स और बेकमैन द्वारा पहली बार प्रारंभ की गई सुविधाओं की स्थान समस्याओं की श्रेणी से है।[1] इस प्रकारी की समस्याएं निम्नलिखित वास्तविक जीवन की समस्याओं का प्रारूप तैयार करती है।
- यहाँ पर n सुविधाओं और स्थानों का समुच्चय है। इस प्रकार स्थानों की प्रत्येक जोड़ी के लिए एक सीमित दूरी निर्दिष्ट की जाती है और प्रत्येक जोड़ी सुविधाओं के लिए वजन या प्रवाह निर्दिष्ट किया जाता है, उदाहरण के लिए, दो सुविधाओं के बीच परिवहन की गई आपूर्ति की मात्रा इसका प्रमुख उदाहरण हैं। इस प्रकार की समस्याओं से संबंधित प्रवाह द्वारा गुणा की जाने वाली दूरियों के योग को कम करने के इस लक्ष्य के साथ सभी सुविधाओं को विभिन्न स्थानों पर आवंटित रहती है।
सहजता से, इस प्रकार के लागत फ़ंक्शन एक-दूसरे के बीच उच्च प्रवाह वाली सुविधाओं को एक-दूसरे के समीप रखने के लिए प्रोत्साहित किए जाते हैं।
इस प्रकार की समस्या से जुड़े कथन के फलस्वरूप मानांकन समस्या से मिलता जुलता है, इसके अतिरिक्त हानि फलन द्विघात असमानताओं के संदर्भ में व्यक्त किया जाता है।
औपचारिक गणितीय परिभाषा
द्विघात मानांकन समस्या की औपचारिक परिभाषा इस प्रकार है:
- समान आकार के दो समुच्चय, P (सुविधाएं) और L (स्थान), भार फलन w: P × P → 'वास्तविक संख्या' और दूरी फ़ंक्शन d: L × L → 'वास्तविक संख्या' के साथ दिए गए हैं। इसके आक्षेप f : P → L (मानांकन) इस प्रकार खोजें कि लागत फलन को प्रदर्शित करता हैं:
- यहाँ इसका न्यूनतम मान प्रदर्शित किया गया है।
सामान्यतः वजन और दूरी के कार्यों को वर्गाकार वास्तविक मान वाले आव्यूह (गणित) के रूप में देखा जाता है, जिससे कि लागत फ़ंक्शन को इस प्रकार लिखा जाता हैं:
आव्यूह संकेतन में:
जहाँ मुख्य रूप से समुच्चय है, इसके अनुसार क्रमपरिवर्तन आव्यूह, मुख्यतः भार आव्यूह को प्रदर्शित करता है और दूरी आव्यूह को प्रदर्शित करती है।
कम्प्यूटेशनल जटिलता
यहाँ पर यह समस्या एनपी के लिए जटिल रहती है, इसलिए इस बहुपद के लिए उचित समय में इस समस्या को हल करने के लिए कोई ज्ञात कलन विधि नहीं है, और यहां तक कि छोटे उदाहरणों के लिए भी लंबे गणना समय की आवश्यकता हो सकती है। यह भी सिद्ध हुआ कि समस्या में किसी भी (स्थिर) कारक के लिए बहुपद समय में चलने वाला सन्निकटन एल्गोरिदम नहीं है, जब तक कि P = NP के समान न हो जाये।[2] इस प्रकार ट्रैवलिंग सेल्समैन की समस्या (टीएसपी) को क्यूएपी के विशेष स्थिति के रूप में देखा जा सकता है, यदि यह कोई मानता है कि प्रवाह सभी सुविधाओं को केवल वलय के साथ जोड़ता है, इसके आधार पर सभी प्रवाह का गैर-शून्य (स्थिर) मान समान है, और सभी दूरियां समान होती हैं, इसके आधार पर टीएसपी उदाहरण की संबंधित दूरी को प्रकट करती हैं। इसके मानक संयोजन के आधार पर अनुकूलन समस्याओं की कई अन्य समस्याओं को इस रूप में लिखा जा सकता है।
अनुप्रयोग
मूल संयंत्र स्थान सूत्रीकरण के अतिरिक्त, क्यूएपी मुद्रित सर्किट बोर्ड या एकीकृत सर्किट पर परस्पर जुड़े इलेक्ट्रॉनिक घटकों की नियुक्ति की समस्या के लिए गणितीय प्रारूप है, जो इलेक्ट्रॉनिक्स में कंप्यूटर एडेड डिजाइन के स्थान और मूल चरण का भाग है।
यह भी देखें
संदर्भ
- Notes
- ↑ Koopmans TC, Beckmann M (1957). Assignment problems and the location of economic activities. Econometrica 25(1):53-76
- ↑ Sahni, Sartaj; Gonzalez, Teofilo (July 1976). "P-Complete Approximation Problems". Journal of the ACM. 23 (3): 555–565. doi:10.1145/321958.321975. hdl:10338.dmlcz/103883.
- Sources
- Michael R. Garey and David S. Johnson (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman. ISBN 0-7167-1045-5. A2.5: ND43, pg.218.
बाहरी संबंध
- https://www.opt.math.tugraz.at/qaplib/ QAPLIB - A Quadratic Assignment Problem Library
- http://www.wiomax.com/team/xie/maos-qap-quadratic-assignment-problem-project-portal/ MAOS-QAP - Java-based Quadratic Assignment Problem Solver
- https://CRAN.R-project.org/package=qap - R package qap: Heuristics for the Quadratic Assignment Problem
- https://apps.microsoft.com/store/detail/qapsolver/9N7WMCFB6NZZ - Metaheuristic QAP solver for Windows 10/11
