इष्टतम सबस्ट्रक्चर

चित्रा 1. इष्टतम सबस्ट्रक्चर का उपयोग करके सबसे छोटा रास्ता ढूँढना। संख्याएँ पथ की लंबाई दर्शाती हैं; सीधी रेखाएँ सिंगल एज (ग्राफ़ थ्योरी) को दर्शाती हैं, लहरदार रेखाएँ सबसे छोटे पथ (ग्राफ़ थ्योरी) को दर्शाती हैं, यानी, ऐसे अन्य कोने भी हो सकते हैं जो यहाँ नहीं दिखाए गए हैं।

कंप्यूटर विज्ञान में, एक समस्या को इष्टतम उपसंरचना कहा जाता है यदि इसके उप-समस्याओं के इष्टतम समाधान से एक इष्टतम समाधान का निर्माण किया जा सकता है। इस संपत्ति का उपयोग किसी समस्या के लिए लालची एल्गोरिदम की उपयोगिता निर्धारित करने के लिए किया जाता है।^[1] आमतौर पर, एक लालची एल्गोरिदम का उपयोग इष्टतम सबस्ट्रक्चर के साथ समस्या को हल करने के लिए किया जाता है यदि यह प्रेरण द्वारा सिद्ध किया जा सकता है कि यह प्रत्येक चरण में इष्टतम है।^[1]अन्यथा, बशर्ते समस्या अतिव्यापी उप-समस्याओं को भी प्रदर्शित करे, विभाजित करें और जीतें एल्गोरिदम | विभाजित करें और जीतें विधियों या गतिशील प्रोग्रामिंग का उपयोग किया जा सकता है। यदि कोई उपयुक्त लालची एल्गोरिदम नहीं हैं और समस्या अतिव्यापी उप-समस्याओं को प्रदर्शित करने में विफल रहती है, तो समाधान स्थान की अक्सर एक लंबी लेकिन सीधी खोज सबसे अच्छा विकल्प है।

ऑप्टिमाइज़ेशन (गणित) के लिए गतिशील प्रोग्रामिंग के अनुप्रयोग में, रिचर्ड बेलमैन का बेलमैन समीकरण # बेलमैन का इष्टतमता का सिद्धांत इस विचार पर आधारित है कि कुछ शुरुआती अवधि टी से कुछ समाप्ति अवधि टी तक एक गतिशील अनुकूलन समस्या को हल करने के लिए, एक को स्पष्ट रूप से करना होगा बाद की तिथियों से शुरू होने वाली उप-समस्याओं को हल करें, जहां t<s<T। यह इष्टतम सबस्ट्रक्चर का एक उदाहरण है। इष्टतमता के सिद्धांत का उपयोग बेलमैन समीकरण को प्राप्त करने के लिए किया जाता है, जो दर्शाता है कि टी से शुरू होने वाली समस्या का मान एस से शुरू होने वाली समस्या के मूल्य से कैसे संबंधित है।

उदाहरण

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

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

परिभाषा

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