एलपी-प्रकार की समस्या

From Vigyanwiki
Revision as of 23:36, 21 May 2023 by alpha>Payal Nayak

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

परिभाषा

एलपी-प्रकार की समस्याओं को शारिर & और वेल्ज़ल (1992) द्वारा परिभाषित किया गया था, जिसमें एक को इनपुट के रूप में तत्वों का एक परिमित सेट S दिया जाता है और एक समारोह f जो पूरी तरह से ऑर्डर किए गए सेट से मूल्यों के लिए S के सबसेट को मैप करता है। दो प्रमुख गुणों को संतुष्ट करने के लिए फ़ंक्शन आवश्यक है:

  • मोनोटोनिकिटी: हर दो सेट A ⊆ B ⊆ S, f(A) ≤ f(B) ≤ f(S) के लिए
  • स्थानीयता: हर दो सेट A ⊆ B ⊆ S और S में हर तत्व x के लिए अगर f(A) = f(B) = f(A ∪ {x}) तो f(A) = f(B ∪ {x}).

एलपी-प्रकार की समस्या का आधार एक सेट B ⊆ S उस संपत्ति के साथ है कि बी के प्रत्येक उचित उपसमुच्चय में बी की तुलना में एफ का छोटा मान होता है, और एलपी-प्रकार की समस्या के आयाम (या संयोजक आयाम) को आधार की अधिकतम प्रमुखता के रूप में परिभाषित किया गया है।

यह माना जाता है कि एक ऑप्टिमाइज़ेशन एल्गोरिदम फ़ंक्शन f का मूल्यांकन केवल उन सेटों पर कर सकता है जो स्वयं आधार हैं या जो किसी एक तत्व को आधार में जोड़कर बनते हैं। वैकल्पिक रूप से, एल्गोरिथम को दो आदिम संचालनों तक सीमित किया जा सकता है: एक उल्लंघन परीक्षण जो एक आधार B और एक तत्व x के लिए निर्धारित करता है कि क्या f(B) = f(B ∪ {x}), और एक आधार संगणना जो (उसी इनपुट के साथ) B ∪ {x}का आधार पाता है, एल्गोरिथम के प्रदर्शन का कार्य केवल इन प्रतिबंधित मूल्यांकनों या आदिमों का उपयोग करके f(S) का मूल्यांकन करना है।

उदाहरण और अनुप्रयोग

LP बॉल्स

एक रेखीय कार्यक्रम को d गैर-नकारात्मक वास्तविक चर की एक प्रणाली द्वारा परिभाषित किया जा सकता है, जो n रैखिक असमानता बाधाओं के अधीन है, साथ में एक गैर-नकारात्मक रैखिक उद्देश्य फ़ंक्शन को कम किया जा सकता है। इसे एलपी-प्रकार की समस्याओं के ढांचे में रखा जा सकता है S को बाधाओं का सेट होने और f(A) (बाधाओं के एक सबसेट A के लिए) को परिभाषित करके छोटे रैखिक कार्यक्रम का न्यूनतम उद्देश्य फ़ंक्शन Aके रूप में परिभाषित किया जा सकता है। उपयुक्त सामान्य स्थिति धारणाओं के साथ (एक ही इष्टतम उद्देश्य फ़ंक्शन मान वाले एकाधिक समाधान बिंदुओं को रोकने के लिए), यह एलपी-प्रकार की समस्या की मोनोटोनिकिटी और स्थानीयता आवश्यकताओं को पूरा करता है, और चर के संख्या d के बराबर संयोजी आयाम है।[1] इसी तरह, एक पूर्णांक कार्यक्रम (रैखिक बाधाओं के संग्रह और एक रैखिक उद्देश्य समारोह के रूप में, एक रैखिक कार्यक्रम के रूप में, लेकिन अतिरिक्त प्रतिबंध के साथ कि चर को केवल पूर्णांक मान लेना चाहिए) एक एलपी की मोनोटोनिकिटी और स्थानीयता गुणों दोनों को संतुष्ट करता है -प्रकार की समस्या, रैखिक कार्यक्रमों के लिए समान सामान्य स्थिति मान्यताओं के साथ बेल (1977) और स्कार्फ (1977) के प्रमेयों से पता चलता है कि d चर के साथ एक पूर्णांक कार्यक्रम के लिए कॉम्बिनेटरियल डायमेंशन अधिकतम 2dहैं।[1]

कम्प्यूटेशनल ज्यामिति में कई प्राकृतिक अनुकूलन समस्याएं एलपी-प्रकार हैं:

सबसे छोटी वृत्त समस्या

* सबसे छोटी वृत्त समस्या एक वृत्त की न्यूनतम त्रिज्या ज्ञात करने की समस्या है जिसमें तल में n बिंदुओं का एक सेट दिया गया है। यह मोनोटोनिकिटी को संतुष्ट करता है (अधिक अंक जोड़ने से केवल सर्कल बड़ा हो सकता है) और स्थानीयता (यदि सेट के लिए सबसे छोटा सर्कल A के लिए सबसे छोटे सर्कल में B और xशामिल हैं, तो उसी वृत्त में B ∪ {x}) भी शामिल है) क्योंकि सबसे छोटा वृत्त हमेशा कुछ तीन बिंदुओं द्वारा निर्धारित किया जाता है, सबसे छोटी वृत्त समस्या में संयोजी आयाम तीन होता है, भले ही इसे द्वि-आयामी यूक्लिडियन ज्यामिति का उपयोग करके परिभाषित किया गया हो।[2] अधिक आम तौर पर, d आयामों में बिंदुओं की सबसे छोटी संलग्न गेंद संयोजी आयाम d + 1. की एलपी-प्रकार की समस्या बनाती है। सबसे छोटी सर्कल समस्या को गेंदों के एक सेट को घेरने वाली सबसे छोटी वृत्त के लिए सामान्यीकृत किया जा सकता है,[3] सबसे छोटी गेंद के लिए जो गेंदों के प्रत्येक सेट को छूती या घेरती है,[4] भारित 1-केंद्र समस्या के लिए,[5] या गैर-यूक्लिडियन स्थानों में इसी तरह की छोटी संलग्न गेंद की समस्याओं के लिए, जैसे कि ब्रेगमैन डायवर्जेंस द्वारा परिभाषित दूरी के साथ अंतरिक्ष।[6] सबसे छोटे घेरने वाले दीर्घवृत्ताभ को खोजने की संबंधित समस्या भी एक एलपी-प्रकार की समस्या है, लेकिन एक बड़े संयोजी आयाम के साथ, d(d + 3)/2.[7]

  • माना K0, K1, ... d-आयामी यूक्लिडियन अंतरिक्ष में n उत्तल सेट का अनुक्रम बनें, और मान लीजिए कि हम इस अनुक्रम का सबसे लंबा उपसर्ग (कंप्यूटर विज्ञान) खोजना चाहते हैं जिसमें एक सामान्य चौराहा बिंदु हो। इसे एलपी-प्रकार की समस्या के रूप में व्यक्त किया जा सकता है जिसमें f(A) = −i जहां Ki A का पहला सदस्य है जो A के एक अन्तर्विभाजक उपसर्ग से संबंधित नहीं है, और जहां f(A) = −n यदि ऐसा कोई सदस्य नहीं है। इस प्रणाली का संयोजन आयाम d + 1है। [8]
  • मान लीजिए कि हमें त्रि-आयामी अंतरिक्ष में अक्ष-संरेखित आयताकार बक्से का एक संग्रह दिया गया है, और हम अंतरिक्ष के सकारात्मक ऑक्टेंट में निर्देशित एक रेखा खोजना चाहते हैं जो सभी बक्से के माध्यम से कटती है। इसे मिश्रित आयाम 4 के साथ एलपी-प्रकार की समस्या के रूप में व्यक्त किया जा सकता है।[9]
  • दो उत्तल पॉलीटोप्स के बीच निकटतम दूरी खोजने की समस्या, उनके सेट के शिखर द्वारा निर्दिष्ट, एलपी-प्रकार की समस्या के रूप में प्रदर्शित की जा सकती है। इस सूत्रीकरण में, सेट S दोनों पॉलीटोप्स में सभी कोने का सेट है, और फ़ंक्शन वैल्यू f(A) दो पॉलीटोप्स में दो सबसेट A के उत्तल वर्टिकल के बीच सबसे छोटी दूरी की उपेक्षा है। समस्या का संयोजी आयाम d + 1 है यदि दो पॉलीटॉप असंयुक्त हैं, या दो बहुशीर्ष या d + 2 यदि उनके पास एक गैर-रिक्त चौराहा है।[1]*मान लीजिए कि S = {f0, f1, ...} क्वासिकोनवेक्स फ़ंक्शन का समुच्चय है। फिर बिंदुवार अधिकतम maxi fi स्वयं क्वासिकॉनवेक्स है, और maxi fi का न्यूनतम मूल्य खोजने की समस्या एक एलपी-प्रकार की समस्या है। इसमें अधिकतम संयोजनात्मक आयाम है 2d + 1है, जहां d कार्यों के डोमेन का आयाम है, लेकिन पर्याप्त रूप से सुचारू कार्यों के लिए अधिकतम d + 1 संयोजी आयाम छोटा है, कई अन्य एलपी-प्रकार की समस्याओं को भी इस तरह क्वासिकोनवेक्स कार्यों का उपयोग करके व्यक्त किया जा सकता है; उदाहरण के लिए, सबसे छोटी एन्क्लोजिंग सर्कल समस्या maxi fi को न्यूनतम करने की समस्या है, जहां प्रत्येक कार्य fi दिए गए बिंदुओं में से किसी एक से यूक्लिडियन दूरी को मापता है।[10]

एल्गोरिथम गेम थ्योरी में कुछ खेलों के इष्टतम परिणामों को निर्धारित करने के लिए एलपी-प्रकार की समस्याओं का भी उपयोग किया गया है,[11] परिमित तत्व विधि मेश में वर्टेक्स प्लेसमेंट में सुधार,[12] सुविधा स्थान की समस्याओं को हल करें,[13] कुछ एक्सपोनेंशियल-टाइम सर्च एल्गोरिदम की समय जटिलता का विश्लेषण करें,[14] और वस्तुओं की त्रि-आयामी स्थितियों को उनकी द्वि-आयामी छवियों से पुनर्निर्माण करता है।[15]


एल्गोरिदम

सीडेल

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

फंक्शन सीडेल(S, f, X) है
    आर := खाली समुच्चय
    बी := एक्स
    S के यादृच्छिक क्रमपरिवर्तन में x के लिए:
        अगर f(B) ≠ f(B ∪ {x}):
            बी := सीडेल(आर, एफ, एक्स ∪ {x})
        आर := आर ∪ {x}
    वापसी बी

संयोजी आयाम d के साथ एक समस्या में एल्गोरिथम के iवें पुनरावृत्ति में उल्लंघन परीक्षण केवल तभी विफल होता है जब x d − |X| शेष आधार तत्व, जो प्रायिकता के साथ अधिक से अधिक होता है (d − |X|)/i. इस गणना के आधार पर, यह दिखाया जा सकता है कि एल्गोरिथम द्वारा किए गए उल्लंघन परीक्षणों की कुल अपेक्षित संख्या O(d! n) हैं n में रैखिक है लेकिन d.घातीय से भी खराब है।

क्लार्कसन

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

समारोह पुनरावर्ती (एस, एफ) है
    X := खाली सेट
    दोहराना
        R := आकार d√n के साथ S का एक यादृच्छिक उपसमुच्चय
        बी := आर के लिए आधार ∪ एक्स, रिकर्सिवली परिकलित
        व := {x | एफ(बी) ≠ एफ(बी ∪ {x})}
        एक्स := एक्स ∪ वी
    जब तक वी खाली न हो जाए
    वापसी बी

प्रत्येक पुनरावृत्ति में, V का अपेक्षित आकार O(√n)है [16] और जब भी V खाली नहीं होता है, तो इसमें S के अंतिम आधार का कम से कम एक नया तत्व शामिल होता है इसलिए, एल्गोरिथ्म अधिकांश विचलन पर प्रदर्शन करता है, प्रत्येक n उल्लंघन परीक्षण करता है और O(d√n)आकार की एक उप-समस्या के लिए एकल पुनरावर्ती कॉल करता है।

क्लार्कसन का पुनरावृत्त एल्गोरिथ्म Sके प्रत्येक तत्व को भार प्रदान करता है, शुरू में वे सभी बराबर होते हैं। इसके बाद यह यादृच्छिक रूप से S से 9d2 तत्वों का एक सेट R चुनता है और पिछले एल्गोरिथम की तरह सेट B और V की गणना करता है। यदि V का कुल वजन S के कुल वजन का अधिकतम 2/(9d − 1) गुना है (जैसा कि निरंतर प्रायिकता के साथ होता है) तब एल्गोरिथ्म V के प्रत्येक तत्व के भार को दोगुना कर देता है और पहले की तरह यह इस प्रक्रिया को तब तक दोहराता है V खाली हो जाता है। प्रत्येक पुनरावृत्ति में, इष्टतम आधार का वजन एस के कुल वजन की तुलना में अधिक दर से बढ़ने के लिए दिखाया जा सकता है जिससे यह अनुसरण करता है कि एल्गोरिथम को O(log n) पुनरावृत्तियों के भीतर समाप्त होना चाहिए।

किसी दिए गए समस्या को हल करने के लिए पुनरावर्ती एल्गोरिदम का उपयोग करके, पुनरावर्ती कॉल के लिए पुनरावृत्ति एल्गोरिदम पर स्विच करना, और फिर पुनरावृत्त एल्गोरिदम द्वारा की गई कॉल के लिए सेडेल के एल्गोरिदम पर स्विच करना संभव है, यह संभव है कि O का उपयोग करके दी गई एलपी-प्रकार की समस्या को हल किया जाए O(dn + d! dO(1) log n) उल्लंघन परीक्षण।

जब एक रेखीय प्रोग्राम पर लागू किया जाता है, तो इस एल्गोरिथम की व्याख्या एक दोहरी सरल विधि के रूप में की जा सकती है।[17] उल्लंघन परीक्षण और आधार संगणना प्रिमिटिव से परे कुछ अतिरिक्त कम्प्यूटेशनल प्रिमिटिव के साथ, इस विधि को नियतात्मक बनाया जा सकता है।[18]


माटूसेक, शारिर और वेलज़ल

माटूसेक, शारिर और & वेलज़ल (1996) एक एल्गोरिदम का वर्णन करता है जो रैखिक कार्यक्रमों की एक अतिरिक्त संपत्ति का उपयोग करता है जो हमेशा अन्य एलपी-प्रकार की समस्याओं से नहीं होता है, कि सभी आधारों में एक दूसरे की समान कार्डिनैलिटी होती है। यदि किसी एलपी-प्रकार की समस्या में यह गुण नहीं है, तो इसे d नए डमी तत्वों को जोड़कर और फ़ंक्शन f को संशोधित करके इसके पुराने मान f(A) और संख्या का min(d,|A|), लेक्सिकोग्राफिक रूप का आदेश दिया।

एक समय में एस के तत्वों को जोड़ने या तत्वों के नमूने खोजने के बजाय, Matoušek, Sharir & Welzl (1996) एक एल्गोरिथ्म का वर्णन करते हैं जो एक समय में तत्वों को हटा देता है। प्रत्येक चरण में यह एक आधार C रखता है जो प्रारंभ में डमी तत्वों का सेट हो सकता है। इसे निम्नलिखित स्यूडोकोड के साथ वर्णित किया जा सकता है: 

समारोह msw(S, f, C) है
    अगर एस = सी तो
        वापसी सी
    S \ C का एक यादृच्छिक तत्व x चुनें
    बी = एमएसडब्ल्यू (एस \ एक्स, एफ, सी)
    अगर f(B) ≠ f(B ∪ {x}) तो
        बी := आधार(बी ∪ {x})
        बी := एमएसडब्ल्यू(एस, एफ, बी)
    वापसी बी

एल्गोरिथम के अधिकांश पुनरावर्ती कॉलों में, उल्लंघन परीक्षण सफल होता है और यदि कथन छोड़ दिया जाता है। हालाँकि, एक छोटी सी संभावना के साथ उल्लंघन परीक्षण विफल हो जाता है और एल्गोरिथ्म एक अतिरिक्त आधार संगणना और फिर एक अतिरिक्त पुनरावर्ती कॉल करता है। जैसा कि लेखक दिखाते हैं, एल्गोरिदम के लिए अपेक्षित समय 'एन' में रैखिक है और d log nके वर्ग रूट में घातीय है इस पद्धति को क्लार्कसन की पुनरावर्ती और पुनरावृत्ति प्रक्रियाओं के साथ जोड़कर, समय निर्भरता के इन दो रूपों को एक दूसरे से अलग किया जा सकता है, जिसके परिणामस्वरूप एक एल्गोरिथ्म होता है जो बाहरी पुनरावर्ती एल्गोरिथ्म में O(dn) उल्लंघन परीक्षण करता है और एक संख्या जो कि घातीय है का वर्गमूल d log d एल्गोरिथम के निचले स्तरों में।[19]


रूपांतर

आउटलेयर के साथ अनुकूलन

माटूसेक (1995) एलपी-प्रकार की अनुकूलन समस्याओं की भिन्नता पर विचार करता है जिसमें सेट के साथ एक दिया जाता है S और उद्देश्य फ़ंक्शन f, एक संख्या k; कार्य शेष सेट पर जितना संभव हो उतना छोटा उद्देश्य कार्य करने के लिए S से k तत्वों को निकालना है। उदाहरण के लिए, जब सबसे छोटी वृत्त समस्या पर लागू किया जाता है, तो यह सबसे छोटा वृत्त देता है जिसमें समतल बिंदुओं के दिए गए सेट के k के अलावा सभी शामिल होते हैं। वह दिखाता है कि, सभी गैर-पतित एलपी-प्रकार की समस्याओं के लिए (अर्थात, ऐसी समस्याएं जिनमें सभी आधारों के अलग-अलग मूल्य हैं) इस समस्या को O(nkd), समय में हल किया जा सकता है O(kd) एलपी-प्रकार के एक सेट को हल करके S के सबसेट द्वारा परिभाषित समस्याएं।

निहित समस्याएं

कुछ ज्यामितीय अनुकूलन समस्याओं को एलपी-प्रकार की समस्याओं के रूप में व्यक्त किया जा सकता है जिसमें एलपी-प्रकार के निर्माण में तत्वों की संख्या अनुकूलन समस्या के लिए इनपुट डेटा मानों की संख्या से काफी अधिक है। एक उदाहरण के रूप में, विमान में nबिंदुओं के संग्रह पर विचार करें, जिनमें, से प्रत्येक स्थिर वेग से गतिमान है। किसी भी समय, इस प्रणाली का व्यास इसके दो बिंदुओं के बीच की अधिकतम दूरी है। उस समय को खोजने की समस्या जिस पर व्यास को कम किया जा सकता है, बिंदुवार O(n2) अर्ध-उत्तल कार्यों को न्यूनतम करने के रूप में तैयार किया जा सकता है, प्रत्येक जोड़ी बिंदुओं के लिए एक, समय के एक फ़ंक्शन के रूप में जोड़ी के बीच यूक्लिडियन दूरी को मापता है। इस प्रकार इसे O(n2) तत्वों के एक सेट पर संयोजी आयाम दो की LP-प्रकार की समस्या के रूप में हल किया जा सकता है, लेकिन यह सेट इनपुट बिंदुओं की संख्या से काफी बड़ा है।[20]

चैन (2004) अंतर्निहित रूप से परिभाषित एलपी-प्रकार की समस्याओं को हल करने के लिए एक एल्गोरिथ्म का वर्णन करता है जैसे कि यह एक जिसमें प्रत्येक एलपी-प्रकार तत्व कुछ स्थिर k के लिए इनपुट मानों के k-tuple द्वारा निर्धारित किया जाता है। अपने दृष्टिकोण को लागू करने के लिए, एक निर्णय एल्गोरिदम मौजूद होना चाहिए जो किसी दिए गए एलपी-प्रकार के आधार बी के लिए निर्धारित कर सकता है और n इनपुट मानों के S सेट कर सकता है, चाहे B और S द्वारा निर्धारित एलपी-प्रकार की समस्या का आधार हो।

चान का एल्गोरिदम निम्न चरणों का पालन करता है:

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

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

उदाहरण के लिए, गतिमान बिंदुओं के न्यूनतम व्यास के लिए, निर्णय एल्गोरिथ्म को केवल एक निश्चित समय पर बिंदुओं के एक समूह के व्यास की गणना करने की आवश्यकता होती है, एक समस्या O(n log n) घूर्णन कैलीपर्स तकनीक का उपयोग करते हुए समय में हल किया जा सकता है इसलिए, चान के एल्गोरिदम को उस समय को खोजने के लिए जिस पर व्यास कम किया जाता है, O(n log n).में भी समय लगता है। चैन इस विधि का उपयोग डी-आयामी यूक्लिडियन अंतरिक्ष में केंद्रबिंदु (ज्यामिति) का एक बिंदु खोजने के लिए n इंगित करता है, समय O(nd − 1 + n log n). उत्तल बहुभुज पर समान वितरण के लिए अधिकतम तुकी गहराई का एक बिंदु खोजने के लिए ब्रास, हेनरिक-लिटान & और मोरिन (2003) द्वारा इसी तरह की तकनीक का उपयोग किया गया था।

इतिहास और संबंधित समस्याएं

रैखिक प्रोग्रामिंग के लिए रैखिक समय एल्गोरिदम की खोज और अवलोकन कि एक ही एल्गोरिदम कई मामलों में ज्यामितीय अनुकूलन समस्याओं को हल करने के लिए इस्तेमाल किया जा सकता है जो रैखिक कार्यक्रम नहीं थे, कम से कम मेगिडो (1983, 1984), जिन्होंने एक रैखिक अपेक्षित समय दिया तीन-चर रैखिक कार्यक्रमों और सबसे छोटी सर्कल समस्या दोनों के लिए एक रैखिक अपेक्षित समय एल्गोरिथम दिया। हालांकि, मेगिडो ने रैखिक प्रोग्रामिंग के सामान्यीकरण को संयोजी के बजाय ज्यामितीय रूप से तैयार किया, सेट के सिस्टम पर एक सार समस्या के बजाय एक उत्तल अनुकूलन समस्या के रूप में। इसी प्रकार, डायर (1986) और क्लार्कसन (क्लार्कसन 1995के 1988 के सम्मेलन संस्करण में) ने देखा कि उनके तरीकों को उत्तल कार्यक्रमों के साथ-साथ रैखिक कार्यक्रमों पर भी लागू किया जा सकता है। डायर (1992) ने दिखाया कि न्यूनतम घेरने वाली दीर्घवृत्ताभ समस्या को गैर-रैखिक बाधाओं की एक छोटी संख्या जोड़कर उत्तल अनुकूलन समस्या के रूप में भी तैयार किया जा सकता है। कम आयामी रैखिक प्रोग्रामिंग और संबंधित समस्याओं के लिए समय सीमा में सुधार करने के लिए यादृच्छिकता का उपयोग क्लार्कसन और डायर & एंड फ्रेज़ (1989)द्वारा किया गया था।

स्थानीयता और एकरसता के स्वयंसिद्धों को संतुष्ट करने वाले कार्यों के संदर्भ में एलपी-प्रकार की समस्याओं की परिभाषा है शारिर & और वेलज़ल (1992)है, लेकिन उसी समय सीमा में अन्य लेखकों ने रैखिक कार्यक्रमों के वैकल्पिक संयुक्त सामान्यीकरण तैयार किए। उदाहरण के लिए, गार्टनर (1995), द्वारा विकसित एक ढांचे में फ़ंक्शन f को Sके सबसेट पर कुल ऑर्डरिंग द्वारा प्रतिस्थापित किया जाता है। कुल ऑर्डर बनाने के लिए एलपी-प्रकार की समस्या में संबंधों को तोड़ना संभव है, लेकिन केवल संयोजी आयाम में वृद्धि की कीमत पर।[21]

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

रैखिक कार्यक्रमों और रैखिक संपूरकता समस्याओं दोनों का एक और सार सामान्यीकरण, द्वारा तैयार किया गया स्टिकनी & एंड वॉटसन (1978) द्वारा तैयार किए गए और बाद में कई अन्य लेखकों द्वारा अध्ययन किए गए दोनों रैखिक कार्यक्रमों और रैखिक पूरकता समस्याओं का एक और सार सामान्यीकरण, संपत्ति के साथ एक हाइपरक्यूब के किनारों के उन्मुखीकरण से संबंधित है कि हाइपरक्यूब के प्रत्येक चेहरे (एक चेहरे के रूप में संपूर्ण हाइपरक्यूब सहित) में एक अद्वितीय सिंक होता है, एक शीर्ष जिसमें कोई बाहरी किनारा नहीं होता है। इस प्रकार का एक ओरिएंटेशन एलपी-प्रकार की समस्या से एक हाइपरक्यूब के शिखर के साथ एस के उपसमुच्चय को इस तरह से बनाया जा सकता है कि दो उपसमुच्चय एक ही तत्व से भिन्न होते हैं यदि और केवल यदि संबंधित कोने निकट हैं और यदि f(A) ≠ f(B) है तो A ⊆ B को B की ओर उन्मुख करना और अन्यथा A की ओर उन्मुख करना। परिणामी ओरिएंटेशन में अतिरिक्त संपत्ति है कि यह एक निर्देशित विश्वकोश ग्राफ बनाता है, जिससे यह दिखाया जा सकता है कि एक यादृच्छिक एल्गोरिथ्म पूरे हाइपरक्यूब (एलपी-प्रकार की समस्या का इष्टतम आधार) के अद्वितीय सिंक को कई चरणों में पा सकता है। n के वर्गमूल में चरघातांकी।[22]

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


टिप्पणियाँ

  1. ↑ 1.0 1.1 1.2 Matoušek, Sharir & Welzl (1996).
  2. ↑ Although the smallest circle problem was first stated to be an LP-type problem by Matoušek, Sharir & Welzl (1996), several earlier papers described algorithms for this problem based on ideas from low-dimensional linear programming, including Megiddo (1983) and Welzl (1991).
  3. ↑ Fischer & Gärtner (2004).
  4. ↑ Löffler & van Kreveld (2010).
  5. ↑ Dyer (1986).
  6. ↑ Nielsen & Nock (2008).
  7. ↑ Matoušek, Sharir & Welzl (1996); Welzl (1991).
  8. ↑ Chan (2004).
  9. ↑ Amenta (1994).
  10. ↑ Amenta, Bern & Eppstein (1999); Eppstein (2005).
  11. ↑ Halman (2007).
  12. ↑ Amenta, Bern & Eppstein (1999).
  13. ↑ Puerto, Rodríguez-Chía & Tamir (2010).
  14. ↑ Eppstein (2006).
  15. ↑ Li (2007).
  16. ↑ Tail bounds on the size of V are also known: see Gärtner & Welzl (2001).
  17. ↑ Kalai (1992).
  18. ↑ Chazelle & Matoušek (1996).
  19. ↑ Matoušek, Sharir & Welzl (1996). A very similar time bound for linear programming was also given by Kalai (1992).
  20. ↑ The LP-type formulation of this problem was given by Chan (2004), but it was studied earlier using other algorithmic methods by Gupta, Janardan & Smid (1996). Chan also cites an unpublished manuscript by Clarkson for an O(n log n) time algorithm, matching the time that can be achieved by the implicit LP-type approach.
  21. ↑ Matoušek (2009).
  22. ↑ Szabó & Welzl (2001).
  23. ↑ Gärtner et al. (2008); Brise & Gärtner (2011).


संदर्भ

Retrieved from ‘https://www.vigyanwiki.in/index.php?title=एलपी-प्रकार_की_समस्या&oldid=173647’