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

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

कंप्यूटर विज्ञान में, समस्या को इष्टतम उपसंरचना कहा जाता है यदि इसके उप-समस्याओं के इष्टतम समाधान से इष्टतम समाधान का निर्माण किया जा सकता है। इस प्रॉपर्टी का उपयोग किसी समस्या के लिए लालची एल्गोरिदम की उपयोगिता निर्धारित करने के लिए किया जाता है।

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

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

उदाहरण

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

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

परिभाषा

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

इष्टतम उपसंरचना के साथ समस्याएं

• सबसे लंबी आम अनुवर्ती समस्या
• सबसे लंबे समय तक बढ़ती अनुवर्ती
• सबसे लंबा मुरजबंध संबंधी सबस्ट्रिंग
• सबसे छोटा पथ समस्या सभी-जोड़े सबसे छोटा पथ सभी-जोड़े सबसे छोटा रास्ता
• कोई भी समस्या जिसे डायनेमिक प्रोग्रामिंग द्वारा हल किया जा सकता है।

इष्टतम उपसंरचना के बिना समस्याएं

• सबसे लंबी पथ समस्या
• जोड़-श्रृंखला घातांक
• सबसे कम लागत वाला एयरलाइन किराया। ऑनलाइन उड़ान खोज का उपयोग करते हुए, हम अधिकांशतः पाएंगे कि हवाई अड्डे A से हवाई अड्डे B तक की सबसे सस्ती उड़ान में हवाई अड्डे C के माध्यम से एक ही कनेक्शन सम्मिलित है, लेकिन हवाई अड्डे A से हवाई अड्डे C तक की सबसे सस्ती उड़ान में कुछ अन्य हवाई अड्डे D के माध्यम से कनेक्शन सम्मिलित है। चुकीं, यदि समस्या पैरामीटर के रूप में लेओवर्स की अधिकतम संख्या लेती है, तो समस्या में इष्टतम उपसंरचना होता है। A से B तक की सबसे सस्ती उड़ान जिसमें अधिकांश k लेओवर सम्मिलित हैं या तो सीधी उड़ान है; या A से कुछ एयरपोर्ट C के लिए सबसे सस्ती उड़ान जिसमें 0≤t<k के साथ कुछ पूर्णांक t के लिए अधिकतम t ठहराव सम्मिलित है, साथ ही C से B तक की सबसे सस्ती उड़ान जिसमें अधिकांश k−1−t ठहराव सम्मिलित हैं।

यह भी देखें

• गतिशील प्रोग्रामिंग
• इष्टतमता का सिद्धांत
• फूट डालो और जीतो एल्गोरिथ्म