डीएए - त्वरित गाइड

एल्गोरिथ्म एक गणना, डेटा प्रोसेसिंग, और स्वचालित तर्क कार्यों को पूरा करने के लिए संचालन के चरणों का एक समूह है। एक एल्गोरिथ्म एक कुशल विधि है जिसे समय और स्थान की परिमित मात्रा के भीतर व्यक्त किया जा सकता है।

एक एल्गोरिथ्म एक बहुत ही सरल और कुशल तरीके से किसी विशेष समस्या के समाधान का प्रतिनिधित्व करने का सबसे अच्छा तरीका है। यदि हमारे पास एक विशिष्ट समस्या के लिए एक एल्गोरिथम है, तो हम इसे किसी भी प्रोग्रामिंग भाषा में लागू कर सकते हैं, जिसका अर्थ है कि एalgorithm is independent from any programming languages।

एल्गोरिदम डिजाइन

एल्गोरिथ्म डिजाइन के महत्वपूर्ण पहलुओं में न्यूनतम समय और स्थान का उपयोग करके एक समस्या को हल करने के लिए एक कुशल एल्गोरिदम बनाना शामिल है।

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

समस्या विकास कदम

निम्नलिखित चरण कम्प्यूटेशनल समस्याओं को हल करने में शामिल हैं।

• समस्या की परिभाषा
• एक मॉडल का विकास
• एक एल्गोरिथ्म की विशिष्टता
• एक एल्गोरिथ्म डिजाइनिंग
• एक एल्गोरिथ्म की शुद्धता की जाँच
• एक एल्गोरिथम का विश्लेषण
• एक एल्गोरिथ्म का कार्यान्वयन
• कार्यक्रम का परीक्षण
• Documentation

एल्गोरिदम के लक्षण

एल्गोरिदम की मुख्य विशेषताएं इस प्रकार हैं -

• एल्गोरिदम में एक विशिष्ट नाम होना चाहिए

• एल्गोरिदम में इनपुट और आउटपुट के स्पष्ट रूप से निर्धारित सेट होने चाहिए

• एल्गोरिदम असंदिग्ध संचालन के साथ सुव्यवस्थित हैं

• एल्गोरिदम समय की एक सीमित मात्रा में रुकते हैं। एल्गोरिथ्म को अनंत के लिए नहीं चलना चाहिए, अर्थात, एल्गोरिथ्म को किसी बिंदु पर समाप्त होना चाहिए

स्यूडोकोड

Pseudocode सादे पाठ के साथ जुड़े अस्पष्टता के बिना एक एल्गोरिथ्म का एक उच्च-स्तरीय विवरण देता है, लेकिन एक विशेष प्रोग्रामिंग भाषा के वाक्यविन्यास को जानने की आवश्यकता के बिना भी।

एल्गोरिथ्म को मौलिक कार्यों के एक सेट के रूप में दर्शाने के लिए स्यूडोकोड का उपयोग करके रनिंग टाइम को अधिक सामान्य तरीके से अनुमानित किया जा सकता है जिसे तब गिना जा सकता है।

एल्गोरिथ्म और स्यूडोकोड के बीच अंतर

एक एल्गोरिथ्म कुछ विशिष्ट विशेषताओं के साथ एक औपचारिक परिभाषा है जो एक प्रक्रिया का वर्णन करता है, जिसे एक विशिष्ट कार्य करने के लिए ट्यूरिंग-पूर्ण कंप्यूटर मशीन द्वारा निष्पादित किया जा सकता है। आम तौर पर, कंप्यूटर विज्ञान में किसी भी उच्च स्तरीय कार्य का वर्णन करने के लिए "एल्गोरिथ्म" शब्द का उपयोग किया जा सकता है।

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

उदाहरण के लिए, प्रविष्टि सॉर्ट के लिए एक एल्गोरिथ्म निम्नलिखित है।

Algorithm: Insertion-Sort 
Input: A list L of integers of length n  
Output: A sorted list L1 containing those integers present in L 
Step 1: Keep a sorted list L1 which starts off empty  
Step 2: Perform Step 3 for each element in the original list L  
Step 3: Insert it into the correct position in the sorted list L1.  
Step 4: Return the sorted list 
Step 5: Stop

यहाँ एक छद्मकोश है जो वर्णन करता है कि एल्गोरिथ्म सम्मिलन-क्रम में ऊपर वर्णित उच्च स्तरीय अमूर्त प्रक्रिया को और अधिक यथार्थवादी तरीके से कैसे वर्णित किया जा सकता है।

for i <- 1 to length(A) 
   x <- A[i] 
   j <- i 
   while j > 0 and A[j-1] > x 
      A[j] <- A[j-1] 
      j <- j - 1 
   A[j] <- x

इस ट्यूटोरियल में, एल्गोरिदम को pseudocode के रूप में प्रस्तुत किया जाएगा, जो कि C, C ++, Java, Python, और अन्य प्रोग्रामिंग भाषाओं के कई मामलों में समान है।

एल्गोरिदम के सैद्धांतिक विश्लेषण में, मनमाने ढंग से बड़े इनपुट के लिए जटिलता समारोह का अनुमान लगाने के लिए, स्पर्शोन्मुख अर्थों में उनकी जटिलता का अनुमान लगाना आम है। अवधि"analysis of algorithms" डोनाल्ड नथ द्वारा गढ़ा गया था।

एल्गोरिथम विश्लेषण कम्प्यूटेशनल जटिलता सिद्धांत का एक महत्वपूर्ण हिस्सा है, जो एक विशिष्ट कम्प्यूटेशनल समस्या को हल करने के लिए एल्गोरिदम के आवश्यक संसाधनों के लिए सैद्धांतिक अनुमान प्रदान करता है। अधिकांश एल्गोरिदम को मनमानी लंबाई के इनपुट के साथ काम करने के लिए डिज़ाइन किया गया है। एल्गोरिदम का विश्लेषण उसे निष्पादित करने के लिए आवश्यक समय और अंतरिक्ष संसाधनों की मात्रा का निर्धारण है।

आमतौर पर, एल्गोरिथ्म की दक्षता या चलने का समय एक फ़ंक्शन के रूप में कहा जाता है, जो इनपुट लंबाई से संबंधित चरणों की संख्या से संबंधित है time complexity, या स्मृति की मात्रा, के रूप में जाना जाता है space complexity।

विश्लेषण की आवश्यकता है

इस अध्याय में, हम एल्गोरिदम के विश्लेषण की आवश्यकता पर चर्चा करेंगे और किसी विशेष समस्या के लिए एक बेहतर एल्गोरिदम का चयन कैसे करें क्योंकि एक कम्प्यूटेशनल समस्या को विभिन्न एल्गोरिदम द्वारा हल किया जा सकता है।

एक विशिष्ट समस्या के लिए एक एल्गोरिथ्म पर विचार करके, हम पैटर्न मान्यता को विकसित करना शुरू कर सकते हैं ताकि इस एल्गोरिथ्म की मदद से इसी प्रकार की समस्याओं को हल किया जा सके।

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

एल्गोरिथ्म का विश्लेषण एल्गोरिथ्म की समस्या को सुलझाने की क्षमता का विश्लेषण करने की प्रक्रिया है समय और आकार के संदर्भ में आवश्यक है (कार्यान्वयन के दौरान भंडारण के लिए स्मृति का आकार)। हालांकि, एल्गोरिदम के विश्लेषण की मुख्य चिंता आवश्यक समय या प्रदर्शन है। आम तौर पर, हम निम्नलिखित प्रकार के विश्लेषण करते हैं -

• Worst-case - आकार के किसी भी उदाहरण पर उठाए गए कदमों की अधिकतम संख्या a।

• Best-case - आकार के किसी भी उदाहरण पर उठाए गए कदमों की न्यूनतम संख्या a।

• Average case - आकार के किसी भी उदाहरण पर उठाए गए कदमों की औसत संख्या a।

• Amortized - आकार के इनपुट पर लागू संचालन का एक क्रम a समय के साथ औसतन।

एक समस्या को हल करने के लिए, हमें समय के साथ-साथ अंतरिक्ष की जटिलता पर भी विचार करने की आवश्यकता है क्योंकि कार्यक्रम एक प्रणाली पर चल सकता है जहां मेमोरी सीमित है लेकिन पर्याप्त स्थान उपलब्ध है या इसके विपरीत हो सकता है। इस संदर्भ में, यदि हम तुलना करते हैंbubble sort तथा merge sort। बबल सॉर्ट को अतिरिक्त मेमोरी की आवश्यकता नहीं होती है, लेकिन मर्ज सॉर्ट के लिए अतिरिक्त स्थान की आवश्यकता होती है। हालांकि मर्ज सॉर्ट की तुलना में बबल सॉर्ट की समय जटिलता अधिक होती है, लेकिन अगर प्रोग्राम को किसी वातावरण में चलाने की आवश्यकता है, तो बबल सॉर्ट को लागू करने की आवश्यकता हो सकती है, जहां मेमोरी बहुत सीमित है।

एक एल्गोरिथ्म के संसाधन खपत को मापने के लिए, इस अध्याय में चर्चा की गई विभिन्न रणनीतियों का उपयोग किया जाता है।

असममित विश्लेषण

किसी फ़ंक्शन का स्पर्शोन्मुख व्यवहार f(n) की वृद्धि को दर्शाता है f(n) जैसा n बड़ा हो जाता है।

हम आम तौर पर के छोटे मूल्यों की अनदेखी करते हैं n, क्योंकि हम आम तौर पर यह अनुमान लगाने में रुचि रखते हैं कि बड़े इनपुट पर कार्यक्रम कितना धीमा होगा।

अंगूठे का एक अच्छा नियम यह है कि स्पर्शोन्मुख विकास दर जितनी धीमी होगी, एल्गोरिथम उतना ही बेहतर होगा। हालांकि यह हमेशा सच नहीं होता है।

उदाहरण के लिए, एक रैखिक एल्गोरिथ्म $f(n) = d * n + k$ हमेशा asymptotically एक द्विघात से बेहतर है, $f(n) = c.n^2 + q$।

पुनरावृत्ति समीकरणों को हल करना

पुनरावृत्ति एक समीकरण या असमानता है जो छोटे आदानों पर इसके मूल्य के संदर्भ में एक फ़ंक्शन का वर्णन करता है। आवर्ती का उपयोग आम तौर पर विभाजन और विजय प्रतिमान में किया जाता है।

हम मानते हैं T(n) आकार की समस्या पर चलने का समय होना n।

यदि समस्या का आकार काफी छोटा है, तो कहें n < c कहाँ पे c एक स्थिर है, सीधा समाधान निरंतर समय लेता है, जिसे इस प्रकार लिखा जाता है θ(1)। यदि समस्या का विभाजन आकार के साथ कई उप-समस्याओं का उत्पादन करता है$\frac{n}{b}$।

समस्या को हल करने के लिए, आवश्यक समय है a.T(n/b)। यदि हम विभाजन के लिए आवश्यक समय पर विचार करते हैंD(n) और उप-समस्याओं के परिणामों के संयोजन के लिए आवश्यक समय है C(n)पुनरावृत्ति संबंध का प्रतिनिधित्व इस प्रकार किया जा सकता है -

$$T(n)=\begin{cases}\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\theta(1) & if\:n\leqslant c\\a T(\frac{n}{b})+D(n)+C(n) & otherwise\end{cases}$$

निम्नलिखित तरीकों का उपयोग करके एक पुनरावृत्ति संबंध को हल किया जा सकता है -

• Substitution Method - इस पद्धति में, हम एक बाध्य अनुमान लगाते हैं और गणितीय प्रेरण का उपयोग करके हम यह साबित करते हैं कि हमारी धारणा सही थी।

• Recursion Tree Method - इस विधि में, एक पुनरावृत्ति वृक्ष का निर्माण होता है जहाँ प्रत्येक नोड लागत का प्रतिनिधित्व करता है।

• Master’s Theorem - पुनरावृत्ति संबंध की जटिलता को खोजने के लिए यह एक और महत्वपूर्ण तकनीक है।

परिशोधित विश्लेषण

अमूर्त विश्लेषण आमतौर पर कुछ एल्गोरिदम के लिए उपयोग किया जाता है जहां समान संचालन का एक क्रम किया जाता है।

• परिशोधित विश्लेषण अलग-अलग संचालन के अनुक्रम की लागत को बाध्य करने के बजाय, पूरे अनुक्रम की वास्तविक लागत पर एक बाध्य प्रदान करता है।

• परिशोधित विश्लेषण औसत-केस विश्लेषण से भिन्न होता है; संभावना परिशोधन विश्लेषण में शामिल नहीं है। परिशोधित विश्लेषण सबसे खराब स्थिति में प्रत्येक ऑपरेशन के औसत प्रदर्शन की गारंटी देता है।

यह केवल विश्लेषण के लिए एक उपकरण नहीं है, यह डिजाइन के बारे में सोचने का एक तरीका है, क्योंकि डिजाइनिंग और विश्लेषण बारीकी से संबंधित हैं।

एकत्र करने की विधि

कुल विधि एक समस्या के बारे में वैश्विक दृष्टिकोण देती है। इस विधि में, यदिn संचालन में सबसे खराब समय लगता है T(n)कुल मिलाकर। फिर प्रत्येक ऑपरेशन की परिशोधन लागत हैT(n)/n। हालांकि अलग-अलग संचालन में अलग-अलग समय लग सकता है, इस पद्धति में अलग-अलग लागत की उपेक्षा की जाती है।

लेखा विधि

इस पद्धति में, अलग-अलग शुल्क उनकी वास्तविक लागत के अनुसार अलग-अलग परिचालनों को सौंपे जाते हैं। यदि किसी ऑपरेशन की बढ़ी हुई लागत इसकी वास्तविक लागत से अधिक है, तो अंतर को क्रेडिट के रूप में ऑब्जेक्ट को सौंपा गया है। यह क्रेडिट बाद के कार्यों के लिए भुगतान करने में मदद करता है जिसके लिए वास्तविक लागत से कम परिशोधन लागत होती है।

यदि वास्तविक लागत और परिशोधित लागत i^th संचालन कर रहे हैं $c_{i}$ तथा $\hat{c_{l}}$, फिर

$$\displaystyle\sum\limits_{i=1}^n \hat{c_{l}}\geqslant\displaystyle\sum\limits_{i=1}^n c_{i}$$

संभावित विधि

यह विधि क्रेडिट के रूप में प्रीपेड काम पर विचार करने के बजाय संभावित ऊर्जा के रूप में प्रीपेड कार्य का प्रतिनिधित्व करती है। यह ऊर्जा भविष्य के संचालन के लिए भुगतान करने के लिए जारी की जा सकती है।

अगर हम प्रदर्शन करते हैं n एक प्रारंभिक डेटा संरचना के साथ संचालन शुरू होता है D₀। हम मानते हैं,c_i वास्तविक लागत के रूप में और D_i के डेटा संरचना के रूप में i^thऑपरेशन। एक वास्तविक संख्या के लिए संभावित फ़ंक्शन potential मैप्स Ф (D_i), की सम्भावना है D_i। परिशोधन लागत$\hat{c_{l}}$ द्वारा परिभाषित किया जा सकता है

$$\hat{c_{l}}=c_{i}+\Phi (D_{i})-\Phi (D_{i-1})$$

इसलिए, कुल परिशोधित लागत है

$$\displaystyle\sum\limits_{i=1}^n \hat{c_{l}}=\displaystyle\sum\limits_{i=1}^n (c_{i}+\Phi (D_{i})-\Phi (D_{i-1}))=\displaystyle\sum\limits_{i=1}^n c_{i}+\Phi (D_{n})-\Phi (D_{0})$$

गतिशील तालिका

यदि तालिका के लिए आवंटित स्थान पर्याप्त नहीं है, तो हमें तालिका को बड़े आकार की तालिका में कॉपी करना होगा। इसी तरह, यदि बड़ी संख्या में सदस्यों को तालिका से मिटा दिया जाता है, तो तालिका को छोटे आकार के साथ फिर से जोड़ना एक अच्छा विचार है।

परिशोधित विश्लेषण का उपयोग करके, हम दिखा सकते हैं कि सम्मिलन और विलोपन की परिशोधित लागत एक गतिशील तालिका में निरंतर और अप्रयुक्त स्थान है जो कुल अंतरिक्ष के निरंतर अंश से अधिक नहीं है।

इस ट्यूटोरियल के अगले अध्याय में, हम संक्षेप में एसिम्प्टोटिक नोटिफिकेशन पर चर्चा करेंगे।

एल्गोरिथ्म की डिजाइनिंग में, एल्गोरिथ्म की जटिलता विश्लेषण एक अनिवार्य पहलू है। मुख्य रूप से, एल्गोरिथम जटिलता अपने प्रदर्शन के बारे में चिंतित है कि यह कितनी तेजी से या धीमा काम करता है।

एक एल्गोरिथ्म की जटिलता डेटा और प्रसंस्करण समय को संसाधित करने के लिए आवश्यक मेमोरी की मात्रा के संदर्भ में एल्गोरिथ्म की दक्षता का वर्णन करती है।

एक एल्गोरिथ्म की जटिलता का दो दृष्टिकोणों में विश्लेषण किया गया है: Time तथा Space।

समय जटिलता

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

अंतरिक्ष जटिलता

यह एक फ़ंक्शन है जो एल्गोरिथ्म में इनपुट के आकार के संदर्भ में एक एल्गोरिथ्म मेमोरी की मात्रा का वर्णन करता है। हम अक्सर "अतिरिक्त" मेमोरी की आवश्यकता की बात करते हैं, इनपुट को स्टोर करने के लिए आवश्यक मेमोरी की गिनती नहीं करते हैं। फिर, हम इसे मापने के लिए प्राकृतिक (लेकिन निश्चित-लंबाई) इकाइयों का उपयोग करते हैं।

अंतरिक्ष जटिलता को कभी-कभी अनदेखा कर दिया जाता है क्योंकि उपयोग की जाने वाली जगह न्यूनतम और / या स्पष्ट होती है, हालांकि कभी-कभी यह समय के रूप में महत्वपूर्ण मुद्दा बन जाता है।

असममित संकेतन

एल्गोरिथ्म का निष्पादन समय अनुदेश सेट, प्रोसेसर गति, डिस्क I / O गति, आदि पर निर्भर करता है। इसलिए, हम एक एल्गोरिथ्म की दक्षता का आंकलन करते हैं।

एक एल्गोरिथ्म के समय समारोह द्वारा दर्शाया गया है T(n), कहाँ पे n इनपुट आकार है।

एक एल्गोरिथ्म की जटिलता का प्रतिनिधित्व करने के लिए विभिन्न प्रकार के स्पर्शोन्मुख संकेतन का उपयोग किया जाता है। एक एल्गोरिथ्म की रनिंग टाइम जटिलता की गणना करने के लिए एसिम्प्टोटिक नोटेशन का उपयोग किया जाता है।

• O - बिग ओह

• Ω - बड़ा ओमेगा

• θ - बिग थीटा

• o - छोटे ओह

• ω - थोड़ा ओमेगा

ओ: असममित ऊपरी बाउंड

'ओ' (बिग ओह) सबसे अधिक इस्तेमाल किया जाने वाला अंकन है। एक समारोहf(n) का प्रतिनिधित्व किया जा सकता है g(n) अर्थात् O(g(n)), यदि सकारात्मक पूर्णांक का मान मौजूद है n जैसा n₀ और एक सकारात्मक स्थिरांक c ऐसा है कि -

$f(n)\leqslant c.g(n)$ के लिये $n > n_{0}$ सभी मामले में

इसलिए, कार्य करें g(n) फ़ंक्शन के लिए एक ऊपरी बाध्य है f(n), जैसा g(n) से अधिक तेजी से बढ़ता है f(n)।

उदाहरण

आइए एक दिए गए कार्य पर विचार करें, $f(n) = 4.n^3 + 10.n^2 + 5.n + 1$

मानते हुए $g(n) = n^3$,

$f(n)\leqslant 5.g(n)$ के सभी मूल्यों के लिए $n > 2$

इसलिए, की जटिलता f(n) के रूप में प्रतिनिधित्व किया जा सकता है $O(g(n))$, अर्थात $O(n^3)$

Pt: असममित निचला बाउंड

हम कहते हैं कि $f(n) = \Omega (g(n))$ जब वहाँ मौजूद है c उस $f(n)\geqslant c.g(n)$ सभी पर्याप्त रूप से बड़े मूल्य के लिए n। यहाँnएक सकारात्मक पूर्णांक है। इसका मतलब है फंक्शनg फ़ंक्शन के लिए एक कम बाध्य है f; के एक निश्चित मूल्य के बादn, f नीचे कभी नहीं जाएगा g।

उदाहरण

आइए एक दिए गए कार्य पर विचार करें, $f(n) = 4.n^3 + 10.n^2 + 5.n + 1$।

मानते हुए $g(n) = n^3$, $f(n)\geqslant 4.g(n)$ के सभी मूल्यों के लिए $n > 0$।

इसलिए, की जटिलता f(n) के रूप में प्रतिनिधित्व किया जा सकता है $\Omega (g(n))$, अर्थात $\Omega (n^3)$

pt: एसिम्प्टोटिक टाइट बाउंड

हम कहते हैं कि $f(n) = \theta(g(n))$ जब वहाँ मौजूद हैं c₁ तथा c₂ उस $c_{1}.g(n) \leqslant f(n) \leqslant c_{2}.g(n)$ सभी पर्याप्त रूप से बड़े मूल्य के लिए n। यहाँn एक सकारात्मक पूर्णांक है।

इसका मतलब है फंक्शन g कार्य के लिए एक तंग बाध्य है f।

उदाहरण

आइए एक दिए गए कार्य पर विचार करें, $f(n) = 4.n^3 + 10.n^2 + 5.n + 1$

मानते हुए $g(n) = n^3$, $4.g(n) \leqslant f(n) \leqslant 5.g(n)$ के सभी बड़े मूल्यों के लिए n।

इसलिए, की जटिलता f(n) के रूप में प्रतिनिधित्व किया जा सकता है $\theta (g(n))$, अर्थात $\theta (n^3)$।

ओ - संकेतन

द्वारा प्रदान की गई स्पर्शोन्मुख ऊपरी सीमा O-notationहो सकता है या स्पर्शोन्मुख रूप से तंग न हो। बद्ध$2.n^2 = O(n^2)$ asymptotically तंग है, लेकिन बाध्य है $2.n = O(n^2)$ नहीं है।

हम प्रयोग करते हैं o-notation एक ऊपरी सीमा को निरूपित करने के लिए जो कि विषम रूप से तंग नहीं है।

हम औपचारिक रूप से परिभाषित करते हैं o(g(n)) (सेट के रूप में जी के छोटे-ओह) f(n) = o(g(n)) किसी भी सकारात्मक निरंतर के लिए $c > 0$ और वहाँ एक मूल्य मौजूद है $n_{0} > 0$, ऐसा है कि $0 \leqslant f(n) \leqslant c.g(n)$।

सहज रूप से, में o-notation, कार्यक्रम f(n) के सापेक्ष नगण्य हो जाता है g(n) जैसा nअनंतता; अर्थात्,

$$\lim_{n \rightarrow \infty}\left(\frac{f(n)}{g(n)}\right) = 0$$

उदाहरण

आइए हम एक ही कार्य पर विचार करें, $f(n) = 4.n^3 + 10.n^2 + 5.n + 1$

मानते हुए $g(n) = n^{4}$,

$$\lim_{n \rightarrow \infty}\left(\frac{4.n^3 + 10.n^2 + 5.n + 1}{n^4}\right) = 0$$

इसलिए, की जटिलता f(n) के रूप में प्रतिनिधित्व किया जा सकता है $o(g(n))$, अर्थात $o(n^4)$।

ation - संकेतन

हम प्रयोग करते हैं ω-notationएक निचली सीमा को निरूपित करने के लिए जो कि विषम रूप से तंग नहीं है। औपचारिक रूप से, हालांकि, हम परिभाषित करते हैंω(g(n)) (थोड़ा-ओ-जी के जी के) सेट के रूप में f(n) = ω(g(n)) किसी भी सकारात्मक निरंतर के लिए C > 0 और वहाँ एक मूल्य मौजूद है $n_{0} > 0$, कि $ 0 \ leqslant cg (n) <f (n) $।

उदाहरण के लिए, $\frac{n^2}{2} = \omega (n)$, परंतु $\frac{n^2}{2} \neq \omega (n^2)$। रिश्ता$f(n) = \omega (g(n))$ तात्पर्य है कि निम्नलिखित सीमा मौजूद है

$$\lim_{n \rightarrow \infty}\left(\frac{f(n)}{g(n)}\right) = \infty$$

अर्थात्, f(n) के सापेक्ष बड़े पैमाने पर हो जाता है g(n) जैसा n अनंत तक पहुंचता है।

उदाहरण

हमें एक ही कार्य पर विचार करें, $f(n) = 4.n^3 + 10.n^2 + 5.n + 1$

मानते हुए $g(n) = n^2$,

$$\lim_{n \rightarrow \infty}\left(\frac{4.n^3 + 10.n^2 + 5.n + 1}{n^2}\right) = \infty$$

इसलिए, की जटिलता f(n) के रूप में प्रतिनिधित्व किया जा सकता है $o(g(n))$, अर्थात $\omega (n^2)$।

अप्रीरी और अपोस्टारी विश्लेषण

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

एक एल्गोरिथ्म के अपोस्टियारी विश्लेषण का मतलब है कि हम एक सिस्टम पर चलने के बाद ही एक एल्गोरिथ्म का विश्लेषण करते हैं। यह सीधे सिस्टम पर निर्भर करता है और सिस्टम से सिस्टम में बदलाव करता है।

एक उद्योग में, हम Apostiari विश्लेषण नहीं कर सकते क्योंकि सॉफ्टवेयर आम तौर पर एक अनाम उपयोगकर्ता के लिए बनाया जाता है, जो इसे उद्योग में मौजूद लोगों से अलग एक प्रणाली पर चलाता है।

Apriori में, यही कारण है कि हम समय और स्थान की जटिलता को निर्धारित करने के लिए असममित नोटेशन का उपयोग करते हैं क्योंकि वे कंप्यूटर से कंप्यूटर में बदलते हैं; हालाँकि, asymptotically वे समान हैं।

इस अध्याय में, हम एक एल्गोरिथ्म की आवश्यकता वाले स्थान की मात्रा के संबंध में कम्प्यूटेशनल समस्याओं की जटिलता पर चर्चा करेंगे।

अंतरिक्ष जटिलता समय जटिलता की कई विशेषताओं को साझा करती है और उनकी कम्प्यूटेशनल कठिनाइयों के अनुसार समस्याओं को वर्गीकृत करने का एक और तरीका है।

अंतरिक्ष जटिलता क्या है?

अंतरिक्ष की जटिलता स्मृति (स्पेस) की मात्रा का वर्णन करने वाला एक फ़ंक्शन है जो एल्गोरिथ्म में इनपुट की मात्रा के संदर्भ में एक एल्गोरिथ्म लेता है।

हम अक्सर बोलते हैं extra memoryजरूरत है, इनपुट को स्टोर करने के लिए आवश्यक मेमोरी को गिनना नहीं। फिर, हम इसे मापने के लिए प्राकृतिक (लेकिन निश्चित-लंबाई) इकाइयों का उपयोग करते हैं।

हम बाइट्स का उपयोग कर सकते हैं, लेकिन इसका उपयोग करना आसान है, कहते हैं, उपयोग किए गए पूर्णांकों की संख्या, निश्चित-आकार की संरचनाओं की संख्या, आदि।

अंत में, हम जिस फ़ंक्शन के साथ आते हैं वह यूनिट का प्रतिनिधित्व करने के लिए आवश्यक बाइट्स की वास्तविक संख्या से स्वतंत्र होगा।

अंतरिक्ष जटिलता को कभी-कभी अनदेखा कर दिया जाता है क्योंकि उपयोग की जाने वाली जगह न्यूनतम और / या स्पष्ट होती है, हालांकि कभी-कभी यह समय की जटिलता के रूप में महत्वपूर्ण मुद्दा बन जाता है

परिभाषा

लश्कर M निर्धारक हो Turing machine (TM)कि सभी आदानों पर टिका है। की अंतरिक्ष जटिलताM कार्य है $f \colon N \rightarrow N$, कहाँ पे f(n) टेप की कोशिकाओं की अधिकतम संख्या है और M लंबाई के किसी भी इनपुट को स्कैन करता है M। यदि अंतरिक्ष की जटिलताM है f(n), हम कह सकते हैं कि M अंतरिक्ष में चलता है f(n)।

हम स्पर्शोन्मुख संकेतन का उपयोग करके ट्यूरिंग मशीन की अंतरिक्ष जटिलता का अनुमान लगाते हैं।

लश्कर $f \colon N \rightarrow R^+$एक समारोह हो। अंतरिक्ष जटिलता वर्गों को निम्नानुसार परिभाषित किया जा सकता है -

SPACE = {L | L is a language decided by an O(f(n)) space deterministic TM}

SPACE = {L | L is a language decided by an O(f(n)) space non-deterministic TM}

PSPACE एक नियतात्मक ट्यूरिंग मशीन पर बहुपद स्थान में निर्णायक भाषाओं का वर्ग है।

दूसरे शब्दों में, PSPACE = U_k SPACE (n^k)

सैविच की प्रमेय

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

समय की जटिलता के लिए, इस तरह के अनुकरण के लिए समय में एक घातीय वृद्धि की आवश्यकता होती है। अंतरिक्ष जटिलता के लिए, यह प्रमेय दिखाता है कि कोई भी गैर-नियतात्मक ट्यूरिंग मशीन जो उपयोग करती हैf(n) अंतरिक्ष को नियतात्मक TM में परिवर्तित किया जा सकता है जो उपयोग करता है f²(n) अंतरिक्ष।

इसलिए, सैविच की प्रमेय में कहा गया है कि, किसी भी कार्य के लिए, $f \colon N \rightarrow R^+$, कहाँ पे $f(n) \geqslant n$

NSPACE(f(n)) ⊆ SPACE(f(n))

जटिलता वर्गों के बीच संबंध

निम्नलिखित चित्र विभिन्न जटिलता वर्गों के बीच संबंधों को दर्शाते हैं।

अब तक, हमने इस ट्यूटोरियल में पी और एनपी कक्षाओं की चर्चा नहीं की है। इन पर बाद में चर्चा की जाएगी।

कई एल्गोरिदम प्रकृति में पुनरावर्ती हैं जो किसी दिए गए समस्या को हल करने के लिए पुनरावर्ती उप-समस्याओं से निपटते हैं।

में divide and conquer approach, एक समस्या को छोटी समस्याओं में विभाजित किया जाता है, फिर छोटी समस्याओं को स्वतंत्र रूप से हल किया जाता है, और अंत में छोटी समस्याओं के समाधान को बड़ी समस्या के समाधान में जोड़ा जाता है।

आम तौर पर, डिवाइड-एंड-कॉनकोर एल्गोरिदम के तीन भाग होते हैं -

• Divide the problem उप-समस्याओं की संख्या में जो एक ही समस्या के छोटे उदाहरण हैं।

• Conquer the sub-problemsउन्हें पुन: हल करके। यदि वे पर्याप्त छोटे हैं, तो आधार मामलों के रूप में उप-समस्याओं को हल करें।

• Combine the solutions मूल समस्या के समाधान में उप-समस्याओं के लिए।

फूट डालो और जीतो दृष्टिकोण के पेशेवरों और विपक्ष

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

इस दृष्टिकोण में, अधिकांश एल्गोरिदम को पुनरावृत्ति का उपयोग करके डिज़ाइन किया गया है, इसलिए स्मृति प्रबंधन बहुत अधिक है। पुनरावर्ती फ़ंक्शन स्टैक के लिए उपयोग किया जाता है, जहां फ़ंक्शन स्थिति को संग्रहीत करने की आवश्यकता होती है।

फूट डालो और जीतो का आवेदन

निम्नलिखित कुछ समस्याएं हैं, जो विभाजन और विजय दृष्टिकोण का उपयोग करके हल की जाती हैं।

• संख्याओं के अनुक्रम का अधिकतम और न्यूनतम ज्ञात करना
• स्ट्रैसेन का मैट्रिक्स गुणन
• मर्ज़ सॉर्ट
• द्विआधारी खोज

आइए हम एक सरल समस्या पर विचार करें जिसे विभाजित करके और तकनीक को जीतकर हल किया जा सकता है।

समस्या का विवरण

एल्गोरिथ्म विश्लेषण में मैक्स-मिन समस्या एक सरणी में अधिकतम और न्यूनतम मूल्य पा रही है।

उपाय

किसी दिए गए सरणी में अधिकतम और न्यूनतम संख्या खोजने के लिए numbers[] आकार का nनिम्नलिखित एल्गोरिथ्म का उपयोग किया जा सकता है। पहले हम इसका प्रतिनिधित्व कर रहे हैंnaive method और फिर हम प्रस्तुत करेंगे divide and conquer approach।

Nave विधि

Nave विधि किसी भी समस्या को हल करने के लिए एक मूल विधि है। इस विधि में, अधिकतम और न्यूनतम संख्या अलग-अलग पाई जा सकती है। अधिकतम और न्यूनतम संख्या खोजने के लिए, निम्नलिखित सरल एल्गोरिथ्म का उपयोग किया जा सकता है।

Algorithm: Max-Min-Element (numbers[]) 
max := numbers[1] 
min := numbers[1] 

for i = 2 to n do 
   if numbers[i] > max then  
      max := numbers[i] 
   if numbers[i] < min then  
      min := numbers[i] 
return (max, min)

विश्लेषण

Naive विधि में तुलना की संख्या है 2n - 2।

विभाजन की संख्या को विभाजित और जीत के दृष्टिकोण का उपयोग करके कम किया जा सकता है। निम्नलिखित तकनीक है।

विभाजित और दृष्टिकोण को जीतें

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

इस दी गई समस्या में, सरणी में तत्वों की संख्या है $y - x + 1$, कहाँ पे y से अधिक या बराबर है x।

$\mathbf{\mathit{Max - Min(x, y)}}$ किसी सरणी के अधिकतम और न्यूनतम मान लौटाएगा $\mathbf{\mathit{numbers[x...y]}}$।

Algorithm: Max - Min(x, y) 
if y – x ≤ 1 then  
   return (max(numbers[x], numbers[y]), min((numbers[x], numbers[y])) 
else 
   (max1, min1):= maxmin(x, ⌊((x + y)/2)⌋) 
   (max2, min2):= maxmin(⌊((x + y)/2) + 1)⌋,y) 
return (max(max1, max2), min(min1, min2))

विश्लेषण

लश्कर T(n) द्वारा की गई तुलनाओं की संख्या हो $\mathbf{\mathit{Max - Min(x, y)}}$, जहां तत्वों की संख्या $n = y - x + 1$।

अगर T(n) संख्याओं का प्रतिनिधित्व करता है, फिर पुनरावृत्ति संबंध के रूप में प्रतिनिधित्व किया जा सकता है

$$T(n) = \begin{cases}T\left(\lfloor\frac{n}{2}\rfloor\right)+T\left(\lceil\frac{n}{2}\rceil\right)+2 & for\: n>2\\1 & for\:n = 2 \\0 & for\:n = 1\end{cases}$$

चलिए हम मान लेते हैं n की शक्ति के रूप में है 2। इसलिये,n = 2^k कहाँ पे k पुनरावृत्ति पेड़ की ऊंचाई है।

इसलिए,

$$T(n) = 2.T (\frac{n}{2}) + 2 = 2.\left(\begin{array}{c}2.T(\frac{n}{4}) + 2\end{array}\right) + 2 ..... = \frac{3n}{2} - 2$$

Naquerve विधि की तुलना में, विभाजित और जीत के दृष्टिकोण में, तुलना की संख्या कम है। हालाँकि, दोनों दृष्टिकोणों को स्पर्शोन्मुख संकेतन का उपयोग करके दर्शाया गया हैO(n)।

इस अध्याय में, हम मर्ज सॉर्ट पर चर्चा करेंगे और इसकी जटिलता का विश्लेषण करेंगे।

समस्या का विवरण

संख्याओं की सूची को छांटने की समस्या खुद को तुरंत विभाजित और जीतने वाली रणनीति के लिए उधार देती है: सूची को दो हिस्सों में विभाजित करें, प्रत्येक आधे को पुन: क्रमबद्ध करें, और फिर दो क्रमबद्ध उप-सूचियों को मर्ज करें।

उपाय

इस एल्गोरिथ्म में, संख्याएँ एक सरणी में संग्रहीत होती हैं numbers[]। यहाँ,p तथा q एक उप-सरणी की शुरुआत और अंत सूचकांक का प्रतिनिधित्व करता है।

Algorithm: Merge-Sort (numbers[], p, r) 
if p < r then  
q = ⌊(p + r) / 2⌋ 
Merge-Sort (numbers[], p, q) 
    Merge-Sort (numbers[], q + 1, r) 
    Merge (numbers[], p, q, r)

Function: Merge (numbers[], p, q, r)
n1 = q – p + 1 
n2 = r – q 
declare leftnums[1…n1 + 1] and rightnums[1…n2 + 1] temporary arrays 
for i = 1 to n1 
   leftnums[i] = numbers[p + i - 1] 
for j = 1 to n2 
   rightnums[j] = numbers[q+ j] 
leftnums[n1 + 1] = ∞ 
rightnums[n2 + 1] = ∞ 
i = 1 
j = 1 
for k = p to r 
   if leftnums[i] ≤ rightnums[j] 
      numbers[k] = leftnums[i] 
      i = i + 1 
   else
      numbers[k] = rightnums[j] 
      j = j + 1

विश्लेषण

आइए विचार करें, मर्ज-सॉर्ट का समय चल रहा है T(n)। इसलिये,

$T(n)=\begin{cases}c & if\:n\leqslant 1\\2\:x\:T(\frac{n}{2})+d\:x\:n & otherwise\end{cases}$जहाँ c और d स्थिर हैं

इसलिए, इस पुनरावृत्ति संबंध का उपयोग करते हुए,

$$T(n) = 2^i T(\frac{n}{2^i}) + i.d.n$$

जैसा, $i = log\:n,\: T(n) = 2^{log\:n} T(\frac{n}{2^{log\:n}}) + log\:n.d.n$

$=\:c.n + d.n.log\:n$

इसलिए, $T(n) = O(n\:log\:n)$

उदाहरण

निम्नलिखित उदाहरण में, हमने मर्ज-सॉर्ट एल्गोरिथ्म को चरण दर चरण दिखाया है। सबसे पहले, प्रत्येक पुनरावृति सरणी को दो उप-सरणियों में विभाजित किया जाता है, जब तक कि उप-सरणी में केवल एक तत्व नहीं होता है। जब इन उप-सरणियों को आगे विभाजित नहीं किया जा सकता है, तो मर्ज संचालन किया जाता है।

इस अध्याय में, हम फूट डालो और जीतो विधि पर आधारित एक और एल्गोरिथ्म पर चर्चा करेंगे।

समस्या का विवरण

बाइनरी खोज को एक क्रमबद्ध सरणी पर किया जा सकता है। इस दृष्टिकोण में, एक तत्व का सूचकांकxयह निर्धारित किया जाता है कि तत्व तत्वों की सूची से संबंधित है या नहीं। यदि सरणी अनसोल्ड है, तो स्थिति को निर्धारित करने के लिए रैखिक खोज का उपयोग किया जाता है।

उपाय

इस एल्गोरिथ्म में, हम यह जानना चाहते हैं कि क्या तत्व है x किसी सरणी में संग्रहीत संख्याओं के समूह के अंतर्गत आता है numbers[]। कहाँ पेl तथा r एक उप-सरणी के बाएं और दाएं सूचकांक का प्रतिनिधित्व करते हैं जिसमें खोज ऑपरेशन किया जाना चाहिए।

Algorithm: Binary-Search(numbers[], x, l, r)
if l = r then  
   return l  
else 
   m := ⌊(l + r) / 2⌋ 
   if x ≤ numbers[m]  then 
      return Binary-Search(numbers[], x, l, m) 
   else 
      return Binary-Search(numbers[], x, m+1, r)

विश्लेषण

रेखीय खोज में चलता है O(n)समय। जबकि द्विआधारी खोज में परिणाम उत्पन्न करता हैO(log n) समय

लश्कर T(n) एक सरणी में सबसे खराब स्थिति में तुलना की संख्या हो n तत्वों।

इसलिये,

$$T(n)=\begin{cases}0 & if\:n= 1\\T(\frac{n}{2})+1 & otherwise\end{cases}$$

इस पुनरावृत्ति संबंध का उपयोग करना $T(n) = log\:n$।

इसलिए, द्विआधारी खोज का उपयोग करता है $O(log\:n)$ समय।

उदाहरण

इस उदाहरण में, हम तत्व 63 को खोजने जा रहे हैं।

इस अध्याय में, पहले हम मैट्रिक्स गुणन की सामान्य विधि के बारे में चर्चा करेंगे और बाद में हम स्ट्रैसेन के मैट्रिक्स गुणन एल्गोरिथम पर चर्चा करेंगे।

समस्या का विवरण

आइए हम दो मैट्रिक्स पर विचार करें X तथा Y। हम परिणामी मैट्रिक्स की गणना करना चाहते हैंZ by multiplying X and Y.

Naïve Method

First, we will discuss naïve method and its complexity. Here, we are calculating Z = X × Y. Using Naïve method, two matrices (X and Y) can be multiplied if the order of these matrices are p × q and q × r. Following is the algorithm.

Algorithm: Matrix-Multiplication (X, Y, Z) 
for i = 1 to p do 
   for j = 1 to r do 
      Z[i,j] := 0 
      for k = 1 to q do 
         Z[i,j] := Z[i,j] + X[i,k] × Y[k,j]

Complexity

Here, we assume that integer operations take O(1) time. There are three for loops in this algorithm and one is nested in other. Hence, the algorithm takes O(n³) time to execute.

Strassen’s Matrix Multiplication Algorithm

In this context, using Strassen’s Matrix multiplication algorithm, the time consumption can be improved a little bit.

Strassen’s Matrix multiplication can be performed only on square matrices where n is a power of 2. Order of both of the matrices are n × n.

Divide X, Y and Z into four (n/2)×(n/2) matrices as represented below −

$Z = \begin{bmatrix}I & J \\K & L \end{bmatrix}$ $X = \begin{bmatrix}A & B \\C & D \end{bmatrix}$ and $Y = \begin{bmatrix}E & F \\G & H \end{bmatrix}$

Using Strassen’s Algorithm compute the following −

$$M_{1} \: \colon= (A+C) \times (E+F)$$

$$M_{2} \: \colon= (B+D) \times (G+H)$$

$$M_{3} \: \colon= (A-D) \times (E+H)$$

$$M_{4} \: \colon= A \times (F-H)$$

$$M_{5} \: \colon= (C+D) \times (E)$$

$$M_{6} \: \colon= (A+B) \times (H)$$

$$M_{7} \: \colon= D \times (G-E)$$

Then,

$$I \: \colon= M_{2} + M_{3} - M_{6} - M_{7}$$

$$J \: \colon= M_{4} + M_{6}$$

$$K \: \colon= M_{5} + M_{7}$$

$$L \: \colon= M_{1} - M_{3} - M_{4} - M_{5}$$

Analysis

$T(n)=\begin{cases}c & if\:n= 1\\7\:x\:T(\frac{n}{2})+d\:x\:n^2 & otherwise\end{cases}$ where c and d are constants

Using this recurrence relation, we get $T(n) = O(n^{log7})$

Hence, the complexity of Strassen’s matrix multiplication algorithm is $O(n^{log7})$.

Among all the algorithmic approaches, the simplest and straightforward approach is the Greedy method. In this approach, the decision is taken on the basis of current available information without worrying about the effect of the current decision in future.

Greedy algorithms build a solution part by part, choosing the next part in such a way, that it gives an immediate benefit. This approach never reconsiders the choices taken previously. This approach is mainly used to solve optimization problems. Greedy method is easy to implement and quite efficient in most of the cases. Hence, we can say that Greedy algorithm is an algorithmic paradigm based on heuristic that follows local optimal choice at each step with the hope of finding global optimal solution.

In many problems, it does not produce an optimal solution though it gives an approximate (near optimal) solution in a reasonable time.

Components of Greedy Algorithm

Greedy algorithms have the following five components −

• A candidate set − A solution is created from this set.

• A selection function − Used to choose the best candidate to be added to the solution.

• A feasibility function − Used to determine whether a candidate can be used to contribute to the solution.

• An objective function − Used to assign a value to a solution or a partial solution.

• A solution function − Used to indicate whether a complete solution has been reached.

Areas of Application

Greedy approach is used to solve many problems, such as

• Finding the shortest path between two vertices using Dijkstra’s algorithm.

• Finding the minimal spanning tree in a graph using Prim’s /Kruskal’s algorithm, etc.

Where Greedy Approach Fails

In many problems, Greedy algorithm fails to find an optimal solution, moreover it may produce a worst solution. Problems like Travelling Salesman and Knapsack cannot be solved using this approach.

The Greedy algorithm could be understood very well with a well-known problem referred to as Knapsack problem. Although the same problem could be solved by employing other algorithmic approaches, Greedy approach solves Fractional Knapsack problem reasonably in a good time. Let us discuss the Knapsack problem in detail.

Knapsack Problem

Given a set of items, each with a weight and a value, determine a subset of items to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible.

The knapsack problem is in combinatorial optimization problem. It appears as a subproblem in many, more complex mathematical models of real-world problems. One general approach to difficult problems is to identify the most restrictive constraint, ignore the others, solve a knapsack problem, and somehow adjust the solution to satisfy the ignored constraints.

Applications

In many cases of resource allocation along with some constraint, the problem can be derived in a similar way of Knapsack problem. Following is a set of example.

• Finding the least wasteful way to cut raw materials
• portfolio optimization
• Cutting stock problems

Problem Scenario

A thief is robbing a store and can carry a maximal weight of W into his knapsack. There are n items available in the store and weight of i^th item is w_i and its profit is p_i. What items should the thief take?

In this context, the items should be selected in such a way that the thief will carry those items for which he will gain maximum profit. Hence, the objective of the thief is to maximize the profit.

Based on the nature of the items, Knapsack problems are categorized as

• Fractional Knapsack
• Knapsack

Fractional Knapsack

In this case, items can be broken into smaller pieces, hence the thief can select fractions of items.

According to the problem statement,

• There are n items in the store

• Weight of i^th item $w_{i} > 0$

• Profit for i^th item $p_{i} > 0$ and

• Capacity of the Knapsack is W

In this version of Knapsack problem, items can be broken into smaller pieces. So, the thief may take only a fraction x_i of i^th item.

$$0 \leqslant x_{i} \leqslant 1$$

The i^th item contributes the weight $x_{i}.w_{i}$ to the total weight in the knapsack and profit $x_{i}.p_{i}$ to the total profit.

Hence, the objective of this algorithm is to

$$maximize\:\displaystyle\sum\limits_{n=1}^n (x_{i}.p_{}i)$$

subject to constraint,

$$\displaystyle\sum\limits_{n=1}^n (x_{i}.w_{}i) \leqslant W$$

It is clear that an optimal solution must fill the knapsack exactly, otherwise we could add a fraction of one of the remaining items and increase the overall profit.

Thus, an optimal solution can be obtained by

$$\displaystyle\sum\limits_{n=1}^n (x_{i}.w_{}i) = W$$

In this context, first we need to sort those items according to the value of $\frac{p_{i}}{w_{i}}$, so that $\frac{p_{i}+1}{w_{i}+1}$ ≤ $\frac{p_{i}}{w_{i}}$ . Here, x is an array to store the fraction of items.

Algorithm: Greedy-Fractional-Knapsack (w[1..n], p[1..n], W) 
for i = 1 to n 
   do x[i] = 0 
weight = 0 
for i = 1 to n 
   if weight + w[i] ≤ W then  
      x[i] = 1 
      weight = weight + w[i] 
   else 
      x[i] = (W - weight) / w[i] 
      weight = W 
      break 
return x

Analysis

If the provided items are already sorted into a decreasing order of $\mathbf{\frac{p_{i}}{w_{i}}}$, then the whileloop takes a time in O(n); Therefore, the total time including the sort is in O(n logn).

Example

Let us consider that the capacity of the knapsack W = 60 and the list of provided items are shown in the following table −

Item	A	B	C	D
Profit	280	100	120	120
Weight	40	10	20	24
Ratio $(\frac{p_{i}}{w_{i}})$	7	10	6	5

As the provided items are not sorted based on $\mathbf{\frac{p_{i}}{w_{i}}}$. After sorting, the items are as shown in the following table.

Item	B	A	C	D
Profit	100	280	120	120
Weight	10	40	20	24
Ratio $(\frac{p_{i}}{w_{i}})$	10	7	6	5

Solution

After sorting all the items according to $\frac{p_{i}}{w_{i}}$. First all of B is chosen as weight of B is less than the capacity of the knapsack. Next, item A is chosen, as the available capacity of the knapsack is greater than the weight of A. Now, C is chosen as the next item. However, the whole item cannot be chosen as the remaining capacity of the knapsack is less than the weight of C.

Hence, fraction of C (i.e. (60 − 50)/20) is chosen.

Now, the capacity of the Knapsack is equal to the selected items. Hence, no more item can be selected.

The total weight of the selected items is 10 + 40 + 20 * (10/20) = 60

And the total profit is 100 + 280 + 120 * (10/20) = 380 + 60 = 440

This is the optimal solution. We cannot gain more profit selecting any different combination of items.

Problem Statement

In job sequencing problem, the objective is to find a sequence of jobs, which is completed within their deadlines and gives maximum profit.

Solution

Let us consider, a set of n given jobs which are associated with deadlines and profit is earned, if a job is completed by its deadline. These jobs need to be ordered in such a way that there is maximum profit.

It may happen that all of the given jobs may not be completed within their deadlines.

Assume, deadline of i^th job J_i is d_i and the profit received from this job is p_i. Hence, the optimal solution of this algorithm is a feasible solution with maximum profit.

Thus, $D(i) > 0$ for $1 \leqslant i \leqslant n$.

Initially, these jobs are ordered according to profit, i.e. $p_{1} \geqslant p_{2} \geqslant p_{3} \geqslant \:... \: \geqslant p_{n}$.

Algorithm: Job-Sequencing-With-Deadline (D, J, n, k) 
D(0) := J(0) := 0 
k := 1 
J(1) := 1   // means first job is selected 
for i = 2 … n do 
   r := k 
   while D(J(r)) > D(i) and D(J(r)) ≠ r do 
      r := r – 1 
   if D(J(r)) ≤ D(i) and D(i) > r then 
      for l = k … r + 1 by -1 do 
         J(l + 1) := J(l) 
         J(r + 1) := i 
         k := k + 1

Analysis

In this algorithm, we are using two loops, one is within another. Hence, the complexity of this algorithm is $O(n^2)$.

Example

Let us consider a set of given jobs as shown in the following table. We have to find a sequence of jobs, which will be completed within their deadlines and will give maximum profit. Each job is associated with a deadline and profit.

Job	J1	J2	J3	J4	J5
Deadline	2	1	3	2	1
Profit	60	100	20	40	20

Solution

To solve this problem, the given jobs are sorted according to their profit in a descending order. Hence, after sorting, the jobs are ordered as shown in the following table.

Job	J2	J1	J4	J3	J5
Deadline	1	2	2	3	1
Profit	100	60	40	20	20

From this set of jobs, first we select J₂, as it can be completed within its deadline and contributes maximum profit.

• Next, J₁ is selected as it gives more profit compared to J₄.

• In the next clock, J₄ cannot be selected as its deadline is over, hence J₃ is selected as it executes within its deadline.

• The job J₅ is discarded as it cannot be executed within its deadline.

Thus, the solution is the sequence of jobs (J₂, J₁, J₃), which are being executed within their deadline and gives maximum profit.

Total profit of this sequence is 100 + 60 + 20 = 180.

Merge a set of sorted files of different length into a single sorted file. We need to find an optimal solution, where the resultant file will be generated in minimum time.

If the number of sorted files are given, there are many ways to merge them into a single sorted file. This merge can be performed pair wise. Hence, this type of merging is called as 2-way merge patterns.

As, different pairings require different amounts of time, in this strategy we want to determine an optimal way of merging many files together. At each step, two shortest sequences are merged.

To merge a p-record file and a q-record file requires possibly p + q record moves, the obvious choice being, merge the two smallest files together at each step.

Two-way merge patterns can be represented by binary merge trees. Let us consider a set of n sorted files {f₁, f₂, f₃, …, f_n}. Initially, each element of this is considered as a single node binary tree. To find this optimal solution, the following algorithm is used.

Algorithm: TREE (n)  
for i := 1 to n – 1 do  
   declare new node  
   node.leftchild := least (list) 
   node.rightchild := least (list) 
   node.weight) := ((node.leftchild).weight) + ((node.rightchild).weight)  
   insert (list, node);  
return least (list);

At the end of this algorithm, the weight of the root node represents the optimal cost.

Example

Let us consider the given files, f₁, f₂, f₃, f₄ and f₅ with 20, 30, 10, 5 and 30 number of elements respectively.

If merge operations are performed according to the provided sequence, then

M₁ = merge f₁ and f₂ => 20 + 30 = 50

M₂ = merge M₁ and f₃ => 50 + 10 = 60

M₃ = merge M₂ and f₄ => 60 + 5 = 65

M₄ = merge M₃ and f₅ => 65 + 30 = 95

Hence, the total number of operations is

50 + 60 + 65 + 95 = 270

Now, the question arises is there any better solution?

बढ़ते क्रम में उनके आकार के अनुसार संख्याओं को क्रमबद्ध करने पर, हमें निम्नलिखित अनुक्रम मिलते हैं -

f₄, f₃, f₁, f₂, f₅

इसलिए, इस अनुक्रम पर मर्ज संचालन किया जा सकता है

M₁ = merge f₄ and f₃ => 5 + 10 = 15

M₂ = merge M₁ and f₁ => 15 + 20 = 35

M₃ = merge M₂ and f₂ => 35 + 30 = 65

M₄ = merge M₃ and f₅ => 65 + 30 = 95

इसलिए, संचालन की कुल संख्या है

15 + 35 + 65 + 95 = 210

जाहिर है, यह पिछले वाले से बेहतर है।

इस संदर्भ में, हम अब इस एल्गोरिथ्म का उपयोग करके समस्या को हल करने जा रहे हैं।

प्रारंभिक सेट

चरण 1

चरण 2

चरण 3

चरण 4

इसलिए, समाधान 15 + 35 + 60 + 95 = 205 संख्याओं की तुलना करता है।

अनुकूलन समस्याओं में डायनामिक प्रोग्रामिंग का भी उपयोग किया जाता है। डिवाइड-एंड-कॉंकर विधि की तरह, डायनामिक प्रोग्रामिंग उपप्रोम्बलों के समाधानों को जोड़कर समस्याओं को हल करता है। इसके अलावा, डायनामिक प्रोग्रामिंग एल्गोरिथ्म प्रत्येक उप-समस्या को एक बार हल करता है और फिर एक तालिका में इसके उत्तर को बचाता है, जिससे हर बार उत्तर को पुन: कंप्यूटिंग के काम से बचा जाता है।

एक समस्या के दो मुख्य गुण बताते हैं कि डायनामिक प्रोग्रामिंग का उपयोग करके दी गई समस्या को हल किया जा सकता है। ये गुण हैंoverlapping sub-problems and optimal substructure।

ओवरलैपिंग उप-समस्याएं

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

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

इष्टतम उप-संरचना

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

उदाहरण के लिए, सबसे छोटी पथ समस्या में निम्नलिखित इष्टतम सबस्ट्रक्चर गुण हैं -

यदि एक नोड x स्रोत नोड से सबसे कम पथ पर स्थित है u गंतव्य के लिए नोड v, फिर सबसे छोटा रास्ता u सेवा v से सबसे छोटे मार्ग का संयोजन है u सेवा x, और सबसे छोटा रास्ता x सेवा v।

फ्लोयड-वारशॉल और बेलमैन-फोर्ड जैसे मानक ऑल पेयर शॉर्टेस्ट पाथ एल्गोरिदम डायनेमिक प्रोग्रामिंग के विशिष्ट उदाहरण हैं।

डायनामिक प्रोग्रामिंग दृष्टिकोण के चरण

डायनामिक प्रोग्रामिंग एल्गोरिथ्म को निम्नलिखित चार चरणों का उपयोग करके बनाया गया है -

• एक इष्टतम समाधान की संरचना की विशेषता।
• एक इष्टतम समाधान के मूल्य को पुन: परिभाषित करें।
• एक इष्टतम समाधान के मूल्य की गणना करें, आमतौर पर नीचे-ऊपर फैशन में।
• गणना की गई जानकारी से एक इष्टतम समाधान का निर्माण।

गतिशील प्रोग्रामिंग दृष्टिकोण के अनुप्रयोग

• मैट्रिक्स चेन गुणा
• सबसे लंबा सामान्य परिणाम
• ट्रैवलिंग सेल्समैन की समस्या

इस ट्यूटोरियल में, पहले हमने लालची दृष्टिकोण का उपयोग करके फ्रैक्शनल नॅप्सैक समस्या पर चर्चा की है। हमने दिखाया है कि लालची दृष्टिकोण फ्रैक्शनल नॅपैक के लिए एक इष्टतम समाधान देता है। हालांकि, यह अध्याय 0-1 नैकपैक समस्या और इसके विश्लेषण को कवर करेगा।

0-1 नैकपैक में, आइटम को तोड़ा नहीं जा सकता है, जिसका अर्थ है कि चोर को आइटम को एक पूरे के रूप में लेना चाहिए या इसे छोड़ देना चाहिए। इसे 0-1 नैकपैक के रूप में कहने के पीछे कारण है।

इसलिए, 0-1 नैकपैक के मामले में, का मूल्य x_i दोनोंमेसे एक हो सकता है 0 या 1, जहाँ अन्य बाधाएँ समान रहती हैं।

0-1 नैकपैक को लालची दृष्टिकोण से हल नहीं किया जा सकता है। लालची दृष्टिकोण एक इष्टतम समाधान सुनिश्चित नहीं करता है। कई उदाहरणों में, लालची दृष्टिकोण एक इष्टतम समाधान दे सकता है।

निम्नलिखित उदाहरण हमारे बयान को स्थापित करेंगे।

उदाहरण 1

आइए हम इस बात पर विचार करें कि नैकस्पैक की क्षमता W = 25 है और आइटम निम्न तालिका में दिखाए गए हैं।

मद	ए	ख	सी	घ
फायदा	24	18	18	10
वजन	24	10	10	7

प्रति यूनिट वजन पर लाभ पर विचार किए बिना (p_i/w_i), अगर हम इस समस्या को हल करने के लिए लालची दृष्टिकोण लागू करते हैं, तो पहले आइटम Aचुना जाएगा क्योंकि यह सभी तत्वों के बीच अधिकतम _i मम लाभ में योगदान देगा ।

आइटम का चयन करने के बाद A, और आइटम का चयन नहीं किया जाएगा। इसलिए, इस मद के लिए निर्धारित कुल लाभ है24। जबकि, आइटम का चयन करके इष्टतम समाधान प्राप्त किया जा सकता है,B और सी, जहां कुल लाभ 18 + 18 = 36 है।

उदाहरण -2

समग्र लाभ के आधार पर वस्तुओं का चयन करने के बजाय, इस उदाहरण में आइटमों का चयन अनुपात p _i / w _{i के} आधार पर किया जाता है । आइए हम मानते हैं कि नैकस्पैक की क्षमता डब्ल्यू = 60 है और आइटम निम्न तालिका में दिखाए गए हैं।

मद	ए	ख	सी
कीमत	100	280	120
वजन	10	40	20
अनुपात	10	7	6

लालची दृष्टिकोण का उपयोग करना, पहले आइटम Aचूना गया। फिर, अगले आइटमBचुना जाता है। इसलिए, कुल लाभ है100 + 280 = 380। हालाँकि, आइटम का चयन करके इस उदाहरण का इष्टतम समाधान प्राप्त किया जा सकता है,B तथा C, जहां कुल लाभ होता है 280 + 120 = 400।

इसलिए, यह निष्कर्ष निकाला जा सकता है कि लालची दृष्टिकोण एक इष्टतम समाधान नहीं दे सकता है।

0-1 नैकपैक को हल करने के लिए, डायनामिक प्रोग्रामिंग दृष्टिकोण की आवश्यकता होती है।

समस्या का विवरण

एक चोर एक दुकान चोरी कर रहा है और एक अधिकतम ले जा सकता है _मैं के मल वजनWउसकी गुत्थी में। वहांn के आइटम और वजन i^th आइटम है w_i और इस मद का चयन करने का लाभ है p_i। चोर को क्या सामान लेना चाहिए?

डायनेमिक-प्रोग्रामिंग दृष्टिकोण

लश्कर i एक इष्टतम समाधान में सबसे अधिक संख्या वाली वस्तु हो S के लिये Wडॉलर। फिरS^' = S - {i} के लिए एक इष्टतम समाधान है W - w_i डॉलर और समाधान के लिए मूल्य S है V_i उप-समस्या का मूल्य।

हम इस तथ्य को निम्नलिखित सूत्र में व्यक्त कर सकते हैं: परिभाषित करें c[i, w] वस्तुओं के लिए समाधान होना 1,2, … , iऔर अधिकतम _आई मम वजनw।

एल्गोरिथ्म निम्नलिखित जानकारी लेता है

• अधिकतम _मैं मम वजनW

• मदों की संख्या n

• दो क्रम v = <v₁, v₂, …, v_n> तथा w = <w₁, w₂, …, w_n>

Dynamic-0-1-knapsack (v, w, n, W) 
for w = 0 to W do 
   c[0, w] = 0 
for i = 1 to n do 
   c[i, 0] = 0 
   for w = 1 to W do 
      if wi ≤ w then 
         if vi + c[i-1, w-wi] then 
            c[i, w] = vi + c[i-1, w-wi] 
         else c[i, w] = c[i-1, w] 
      else 
         c[i, w] = c[i-1, w]

शुरू करने के लिए आइटम के सेट को टेबल से घटाया जा सकता है c[n, w] और पीछे की ओर ट्रेसिंग जहां से इष्टतम मान आए।

यदि c [i, w] = c [i-1, w] , तो आइटमi समाधान का हिस्सा नहीं है, और हम साथ अनुरेखण जारी रखते हैं c[i-1, w]। अन्यथा, आइटमi समाधान का हिस्सा है, और हम साथ अनुरेखण जारी रखते हैं c[i-1, w-W]।

विश्लेषण

यह एल्गोरिथ्म (( n , w ) बार लेता है क्योंकि तालिका c में ( n + 1) है। ( w + 1) प्रविष्टियां, जहां प्रत्येक प्रविष्टि को गणना करने के लिए each (1) समय की आवश्यकता होती है।

सबसे लंबे समय तक चलने वाली सामान्य समस्या सबसे लंबे अनुक्रम का पता लगा रही है जो कि दिए गए तार में मौजूद है।

परिणाम को

आइए एक अनुक्रम पर विचार करें S = <s ₁ , s ₂ , s ₃ , s ₄ ,…, s _n >।

एक सीक्वेंस Z = <z ₁ , z ₂ , z ₃ , z ₄ ,…, z _m > S पर S को S का आफ्टरनून कहा जाता है, अगर और केवल अगर इसे कुछ तत्वों के S डिलीट से प्राप्त किया जा सकता है।

सामान्य परिणाम

मान लीजिए, X तथा Yतत्वों के एक सीमित सेट पर दो अनुक्रम हैं। हम कह सकते हैं किZ का एक सामान्य परिणाम है X तथा Y, अगर Z दोनों का एक परिणाम है X तथा Y।

सबसे लंबा सामान्य परिणाम

यदि अनुक्रम का एक सेट दिया जाता है, तो सबसे लंबे समय तक चलने वाली समस्या बाद में उन सभी अनुक्रमों की एक सामान्य अनुवर्तीता है जो अधिकतम लंबाई का है।

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

Nave विधि

लश्कर X लंबाई का एक क्रम हो m तथा Y लंबाई का एक क्रम n। के हर बाद के लिए जाँच करेंX चाहे वह इसके बाद का हो Y, और सबसे लंबे समय तक पाए जाने वाले सामान्य परिणाम लौटाएं।

वहां 2^m के बाद के X। परीक्षण अनुक्रम है या नहीं यह एक के बाद हैY लेता है O(n)समय। इस प्रकार, भोले एल्गोरिदम ले जाएगाO(n2^m) समय।

गतिशील प्रोग्रामिंग

चलो एक्स = <एक्स ₁ , एक्स ₂ , एक्स ₃ , ..., एक्स _मीटर > और वाई = <y ₁ , वाई ₂ , वाई ₃ , ..., वाई _एन > क्रम हो। एक तत्व की लंबाई की गणना करने के लिए निम्नलिखित एल्गोरिथ्म का उपयोग किया जाता है।

इस प्रक्रिया में, तालिका C[m, n] पंक्ति प्रमुख क्रम और एक अन्य तालिका में गणना की जाती है B[m,n] इष्टतम समाधान के निर्माण के लिए गणना की जाती है।

Algorithm: LCS-Length-Table-Formulation (X, Y)
m := length(X) 
n := length(Y) 
for i = 1 to m do 
   C[i, 0] := 0 
for j = 1 to n do 
   C[0, j] := 0 
for i = 1 to m do 
   for j = 1 to n do 
      if xi = yj 
         C[i, j] := C[i - 1, j - 1] + 1 
         B[i, j] := ‘D’ 
      else 
         if C[i -1, j] ≥ C[i, j -1] 
            C[i, j] := C[i - 1, j] + 1 
            B[i, j] := ‘U’ 
         else 
         C[i, j] := C[i, j - 1]
         B[i, j] := ‘L’ 
return C and B

Algorithm: Print-LCS (B, X, i, j)
if i = 0 and j = 0 
   return  
if B[i, j] = ‘D’ 
   Print-LCS(B, X, i-1, j-1) 
   Print(xi) 
else if B[i, j] = ‘U’ 
   Print-LCS(B, X, i-1, j) 
else 
   Print-LCS(B, X, i, j-1)

यह एल्गोरिथ्म सबसे लंबे समय तक चलने वाले सामान्य प्रिंट को प्रिंट करेगा X तथा Y।

विश्लेषण

तालिका, बाहरी को आबाद करने के लिए for पाश iterates m समय और भीतर for पाश iterates nबार। इसलिए, एल्गोरिथ्म की जटिलता ओ (एम, एन) है , जहांm तथा n दो तारों की लंबाई है।

उदाहरण

इस उदाहरण में, हमारे पास दो तार हैं X = BACDB तथा Y = BDCB सबसे लंबे समय तक सामान्य परिणाम खोजने के लिए।

एल्गोरिथ्म एलसीएस-लंबाई-तालिका-निर्माण (जैसा कि ऊपर कहा गया है) के बाद, हमने टेबल सी (बाएं हाथ की तरफ दिखाया गया है) और टेबल बी (दाहिने हाथ की तरफ दिखाया गया है) की गणना की है।

टेबल बी में, 'डी', 'एल' और 'यू' के बजाय, हम क्रमशः विकर्ण तीर, बाएं तीर और ऊपर तीर का उपयोग कर रहे हैं। तालिका बी बनाने के बाद, LCS फ़ंक्शन LCS-Print द्वारा निर्धारित किया जाता है। परिणाम बीसीबी है।

ए spanning tree एक अप्रत्यक्ष ग्राफ़ का एक सबसेट है जिसमें सभी किनारों को न्यूनतम संख्या में किनारों से जोड़ा गया है।

यदि सभी कोने एक ग्राफ में जुड़े हुए हैं, तो कम से कम एक फैले हुए पेड़ मौजूद हैं। एक ग्राफ में, एक से अधिक फैले हुए वृक्ष मौजूद हो सकते हैं।

गुण

• एक फैले हुए वृक्ष का कोई चक्र नहीं होता है।
• किसी भी शीर्ष पर किसी भी अन्य शीर्ष से पहुंचा जा सकता है।

उदाहरण

निम्नलिखित ग्राफ में, हाइलाइट किए गए किनारे एक फैले हुए पेड़ का निर्माण करते हैं।

न्यूनतम फैलाव वाला पेड़

ए Minimum Spanning Tree (MST)एक जुड़े भारित अप्रत्यक्ष ग्राफ के किनारों का एक सबसेट है जो न्यूनतम संभव कुल बढ़त वजन के साथ सभी कोने जोड़ता है। एक एमएसटी प्राप्त करने के लिए, प्राइम के एल्गोरिथ्म या क्रुस्कल के एल्गोरिथ्म का उपयोग किया जा सकता है। इसलिए, हम इस अध्याय में प्राइम के एल्गोरिथ्म पर चर्चा करेंगे।

जैसा कि हमने चर्चा की है, एक ग्राफ में एक से अधिक फैले हुए पेड़ हो सकते हैं। अगर वहाँn वर्टिकल की संख्या, फैले हुए वृक्ष होना चाहिए n - 1किनारों की संख्या। इस संदर्भ में, यदि ग्राफ़ का प्रत्येक किनारा एक भार के साथ जुड़ा हुआ है और एक से अधिक फैले हुए पेड़ मौजूद हैं, तो हमें ग्राफ़ के न्यूनतम फैले हुए पेड़ को खोजने की आवश्यकता है।

इसके अलावा, अगर कोई डुप्लिकेट वेटेड किनारों मौजूद हैं, तो ग्राफ में कई न्यूनतम फैले हुए पेड़ हो सकते हैं।

उपरोक्त ग्राफ में, हमने एक फैले हुए पेड़ को दिखाया है, हालांकि यह न्यूनतम फैले हुए पेड़ नहीं है। इस फैले हुए पेड़ की लागत (5 + 7 + 3 + 3 + 5 + 8 + 3 + 4) = 38 है।

न्यूनतम फैले हुए पेड़ को खोजने के लिए हम प्राइम के एल्गोरिथ्म का उपयोग करेंगे।

प्राइम का एल्गोरिथम

प्राइम का एल्गोरिथ्म न्यूनतम फैले हुए पेड़ को खोजने के लिए एक लालची दृष्टिकोण है। इस एल्गोरिथ्म में, एक एमएसटी बनाने के लिए हम एक अनियंत्रित शीर्ष से शुरू कर सकते हैं।

Algorithm: MST-Prim’s (G, w, r) 
for each u є G.V 
   u.key = ∞ 
   u.∏ = NIL 
r.key = 0 
Q = G.V 
while Q ≠ Ф 
   u = Extract-Min (Q) 
   for each v є G.adj[u] 
      if each v є Q and w(u, v) < v.key 
         v.∏ = u 
         v.key = w(u, v)

फ़ंक्शन एक्सट्रैक्ट-मिन न्यूनतम बढ़त लागत के साथ वर्टेक्स लौटाता है। यह फ़ंक्शन मिन-हीप पर काम करता है।

उदाहरण

प्राइम के एल्गोरिथ्म का उपयोग करते हुए, हम किसी भी शीर्ष से शुरू कर सकते हैं, हमें शीर्ष से शुरू करते हैं 1।

शिखर 3 शीर्ष से जुड़ा है 1 न्यूनतम बढ़त लागत के साथ, इसलिए बढ़त (1, 2) फैले पेड़ में जोड़ा जाता है।

अगला, किनारा (2, 3) माना जाता है कि यह किनारों के बीच न्यूनतम है {(1, 2), (2, 3), (3, 4), (3, 7)}।

अगले चरण में, हमें बढ़त मिलती है (3, 4) तथा (2, 4)न्यूनतम लागत के साथ। एज(3, 4) यादृच्छिक पर चुना गया है।

इसी तरह से, किनारों (4, 5), (5, 7), (7, 8), (6, 8) तथा (6, 9)चुने गए हैं। के रूप में सभी कोने का दौरा कर रहे हैं, अब एल्गोरिथ्म बंद हो जाता है।

फैले हुए वृक्ष की लागत (2 + 2 + 3 + 2 + 5 + 2 + 3 + 4) = 23 है। इस ग्राफ में कोई अधिक फैलाव वाला वृक्ष नहीं है, जिसकी लागत कम है 23।

डीजकस्ट्रा का एल्गोरिथम

दिज्क्स्ट्रा का एल्गोरिथ्म एक निर्देशित भारित ग्राफ G = (V, E) पर एकल-स्रोत लघु-पथ समस्या का हल करता है , जहां सभी किनारे गैर-नकारात्मक हैं (यानी, w (u, v) for 0 प्रत्येक किनारे के लिए (u, v) )) ई )।

निम्नलिखित एल्गोरिथ्म में, हम एक फ़ंक्शन का उपयोग करेंगे Extract-Min(), जो सबसे छोटी कुंजी के साथ नोड को निकालता है।

Algorithm: Dijkstra’s-Algorithm (G, w, s) 
for each vertex v Є G.V  
   v.d := ∞ 
   v.∏ := NIL 
s.d := 0 
S := Ф 
Q := G.V 
while Q ≠ Ф 
   u := Extract-Min (Q) 
   S := S U {u} 
   for each vertex v Є G.adj[u] 
      if v.d > u.d + w(u, v) 
         v.d := u.d + w(u, v) 
         v.∏ := u

विश्लेषण

इस एल्गोरिथ्म की जटिलता पूरी तरह से एक्सट्रैक्ट-मिन फ़ंक्शन के कार्यान्वयन पर निर्भर है। यदि अर्क मिन फ़ंक्शन को रैखिक खोज का उपयोग करके कार्यान्वित किया जाता है, तो इस एल्गोरिथ्म की जटिलता हैO(V² + E)।

इस एल्गोरिथ्म में, यदि हम मिन-हीप का उपयोग करते हैं Extract-Min() फ़ंक्शन नोड को वापस करने के लिए कार्य करता है Q सबसे छोटी कुंजी के साथ, इस एल्गोरिथ्म की जटिलता को और कम किया जा सकता है।

उदाहरण

आइए हम शीर्ष पर विचार करें 1 तथा 9क्रमशः शुरुआत और गंतव्य शीर्ष के रूप में। प्रारंभ में, प्रारंभ शीर्ष को छोड़कर सभी शीर्षों को the द्वारा चिह्नित किया जाता है और प्रारंभ शीर्ष को चिह्नित किया जाता है0।

शिखर	प्रारंभिक	चरण १ वी १	चरण 2 वी 3	चरण 3 वी 2	चरण 4 वी 4	चरण 5 वी 5	स्टेप 6 वी 7	चरण 7 वी 8	चरण 8 वी 6
1	0	0	0	0	0	0	0	0	0
2	∞	5	4	4	4	4	4	4	4
3	∞	2	2	2	2	2	2	2	2
4	∞	∞	∞	7	7	7	7	7	7
5	∞	∞	∞	1 1	9	9	9	9	9
6	∞	∞	∞	∞	∞	17	17	16	16
7	∞	∞	1 1	1 1	1 1	1 1	1 1	1 1	1 1
8	∞	∞	∞	∞	∞	16	13	13	13
9	∞	∞	∞	∞	∞	∞	∞	∞	20

इसलिए, वर्टेक्स की न्यूनतम दूरी 9 शीर्ष से 1 है 20। और रास्ता है

1 → 3 → 7 → 8 → 6 → 9

यह पथ पूर्ववर्ती सूचना के आधार पर निर्धारित किया जाता है।

बेलमैन फोर्ड एल्गोरिथम

यह एल्गोरिथ्म एक निर्देशित ग्राफ के एकल स्रोत सबसे छोटी पथ समस्या को हल करता है G = (V, E)जिसमें किनारे का वजन ऋणात्मक हो सकता है। इसके अलावा, यह एल्गोरिथ्म सबसे छोटा रास्ता खोजने के लिए लागू किया जा सकता है, अगर कोई नकारात्मक भारित चक्र मौजूद नहीं है।

Algorithm: Bellman-Ford-Algorithm (G, w, s) 
for each vertex v Є G.V  
   v.d := ∞ 
   v.∏ := NIL 
s.d := 0 
for i = 1 to |G.V| - 1 
   for each edge (u, v) Є G.E 
      if v.d > u.d + w(u, v) 
         v.d := u.d +w(u, v) 
         v.∏ := u 
for each edge (u, v) Є G.E 
   if v.d > u.d + w(u, v) 
      return FALSE 
return TRUE

विश्लेषण

सबसे पहला for लूप का उपयोग आरंभीकरण के लिए किया जाता है, जो अंदर चलता है O(V)बार। अगलाfor लूप रन |V - 1| किनारों पर गुजरता है, जो लेता हैO(E) बार।

इसलिए, बेलमैन-फोर्ड एल्गोरिथ्म में चलता है O(V, E) समय।

उदाहरण

निम्न उदाहरण से पता चलता है कि बेलमैन-फोर्ड एल्गोरिदम कैसे कदम से कदम काम करता है। इस ग्राफ में एक नकारात्मक बढ़त है लेकिन इसका कोई नकारात्मक चक्र नहीं है, इसलिए इस तकनीक का उपयोग करके समस्या को हल किया जा सकता है।

आरंभीकरण के समय, स्रोत को छोड़कर सभी कोने the द्वारा चिह्नित किए जाते हैं और स्रोत द्वारा चिह्नित किया जाता है 0।

पहले चरण में, स्रोत से आने वाले सभी कोने न्यूनतम लागत द्वारा अद्यतन किए जाते हैं। इसलिए, कोनेa तथा h अपडेट किए जाते हैं।

अगले चरण में, कोने a, b, f तथा e अपडेट किए जाते हैं।

इसी स्टेप के बाद, इस स्टेप वर्जन में b, f, c तथा g अपडेट किए जाते हैं।

यहाँ, कोने c तथा d अपडेट किए जाते हैं।

इसलिए, वर्टेक्स के बीच न्यूनतम दूरी s और शीर्ष d है 20।

पूर्ववर्ती सूचनाओं के आधार पर, पथ s → h → e → g → c → d है

एक मल्टीस्टेज ग्राफ G = (V, E) एक निर्देशित ग्राफ़ है जहाँ वर्टिकल को विभाजित किया गया है k (कहाँ पे k > 1) असंबद्ध सबसेट की संख्या S = {s₁,s₂,…,s_k}ऐसा किनारा (u, v) E में है, तो u v s _i और v ₁ s _{1 + 1} विभाजन में कुछ सबसेट के लिए और |s₁| = |s_k| = 1।

शीर्षासन s Є s₁ कहा जाता है source और शीर्ष t Є s_k कहा जाता है sink।

Gआमतौर पर इसे भारित ग्राफ माना जाता है। इस ग्राफ में, एक किनारे की लागत (i, j) को c (i, j) द्वारा दर्शाया गया है । इसलिए, स्रोत से पथ की लागतs डूबना t इस मार्ग में प्रत्येक किनारों की लागत का योग है।

मल्टीस्टेज ग्राफ समस्या स्रोत से न्यूनतम लागत के साथ रास्ता ढूंढ रही है s डूबना t।

उदाहरण

मल्टीस्टेज ग्राफ की अवधारणा को समझने के लिए निम्नलिखित उदाहरण पर विचार करें।

सूत्र के अनुसार, हमें लागत की गणना करनी होगी (i, j) निम्नलिखित चरणों का उपयोग कर

चरण -1: लागत (K-2, j)

इस चरण में, तीन नोड्स (नोड 4, 5. 6) के रूप में चुने गए हैं j। इसलिए, इस कदम पर न्यूनतम लागत चुनने के लिए हमारे पास तीन विकल्प हैं।

लागत (3, 4) = मिनट {c (4, 7) + लागत (7, 9), सी (4, 8) + लागत (8, 9)} = 7

लागत (3, 5) = मिनट {c (5, 7) + लागत (7, 9), सी (5, 8) + लागत (8, 9)} = 5

लागत (3, 6) = मिनट {c (6, 7) + लागत (7, 9), सी (6, 8) + लागत (8, 9)} = 5

चरण -2: लागत (K-3, j)

दो नोड्स को j के रूप में चुना जाता है क्योंकि स्टेज k - 3 = 2 पर दो नोड्स होते हैं, 2 और 3. इसलिए, मान i = 2 और j = 2 और 3 होता है।

लागत (2, 2) = मिनट {c (2, 4) + लागत (4, 8) + लागत (8, 9), सी (2, 6) +

लागत (6, 8) + लागत (8, 9)} = 8

लागत (2, 3) = {c (3, 4) + लागत (4, 8) + लागत (8, 9), सी (3, 5) + लागत (5, 8) + लागत (8, 9) c (3, 6) + लागत (6, 8) + लागत (8, 9)} = 10

चरण -3: लागत (K-4, j)

लागत (1, 1) = {c (1, 2) + लागत (2, 6) + लागत (6, 8) + लागत (8, 9), सी (1, 3) + लागत (3, 5) + लागत (5, 8) + लागत (8, 9))} = 12

c (1, 3) + लागत (3, 6) + लागत (6, 8 + लागत (8, 9))}} 13

इसलिए, न्यूनतम लागत वाला मार्ग है 1→ 3→ 5→ 8→ 9।

समस्या का विवरण

एक यात्री को एक सूची से सभी शहरों का दौरा करने की आवश्यकता है, जहां सभी शहरों के बीच की दूरी ज्ञात है और प्रत्येक शहर को बस एक बार जाना चाहिए। वह सबसे छोटा संभव मार्ग क्या है जो वह प्रत्येक शहर में एक बार आता है और मूल शहर में लौटता है?

उपाय

ट्रैवलिंग सेल्समैन समस्या सबसे कुख्यात कम्प्यूटेशनल समस्या है। हम प्रत्येक संभावित दौरे का मूल्यांकन करने और सर्वश्रेष्ठ का चयन करने के लिए जानवर-बल दृष्टिकोण का उपयोग कर सकते हैं। के लियेn एक ग्राफ में कोने की संख्या, वहाँ हैं (n - 1)! संभावनाओं की संख्या।

गतिशील प्रोग्रामिंग दृष्टिकोण का उपयोग करते हुए जानवर-बल के बजाय, समाधान कम समय में प्राप्त किया जा सकता है, हालांकि बहुपद समय एल्गोरिथ्म नहीं है।

आइए हम एक ग्राफ पर विचार करें G = (V, E), कहाँ पे V शहरों का एक सेट है और Eभारित किनारों का एक सेट है। एक किनारेe(u, v) उस कोने का प्रतिनिधित्व करता है u तथा vजुड़े हुए हैं। वर्टेक्स के बीच की दूरीu तथा v है d(u, v), जो गैर-नकारात्मक होना चाहिए।

मान लीजिए हमने शहर में शुरुआत की है 1 और कुछ शहरों का दौरा करने के बाद अब हम शहर में हैं j। इसलिए, यह एक आंशिक दौरा है। हमें निश्चित रूप से जानने की जरूरत हैj, क्योंकि यह निर्धारित करेगा कि कौन से शहर अगले यात्रा के लिए सबसे सुविधाजनक हैं। हमें सभी शहरों का अब तक पता करने की आवश्यकता है, ताकि हम उनमें से किसी को भी न दोहराएं। इसलिए, यह एक उपयुक्त उप-समस्या है।

शहरों के सबसेट के लिए S Є {1, 2, 3, ... , n} जिसमें शामिल है 1, तथा j Є S, चलो C(S, j) प्रत्येक नोड में आने वाले सबसे छोटे पथ की लंबाई हो S बिल्कुल एक बार, शुरू करने पर 1 और अंत में j।

कब |S| > 1, हम परिभाषित करते हैंC(S, 1) = = चूंकि पथ शुरू नहीं हो सकता है और समाप्त नहीं हो सकता है 1।

अब, व्यक्त करते हैं C(S, j)छोटी उप-समस्याओं के संदर्भ में। हम पर शुरू करने की जरूरत है1 और अंत में j। हमें इस तरह से अगले शहर का चयन करना चाहिए

$$C(S, j) = min \:C(S - \lbrace j \rbrace, i) + d(i, j)\:where\: i\in S \: and\: i \neq jc(S, j) = minC(s- \lbrace j \rbrace, i)+ d(i,j) \:where\: i\in S \: and\: i \neq j $$

Algorithm: Traveling-Salesman-Problem 
C ({1}, 1) = 0 
for s = 2 to n do 
   for all subsets S Є {1, 2, 3, … , n} of size s and containing 1 
      C (S, 1) = ∞ 
   for all j Є S and j ≠ 1 
      C (S, j) = min {C (S – {j}, i) + d(i, j) for i Є S and i ≠ j} 
Return minj C ({1, 2, 3, …, n}, j) + d(j, i)

विश्लेषण

सबसे ज्यादा हैं $2^n.n$उप-समस्याओं और प्रत्येक को हल करने के लिए रैखिक समय लगता है। इसलिए, कुल चलने का समय है$O(2^n.n^2)$।

उदाहरण

निम्नलिखित उदाहरण में, हम यात्रा विक्रेता समस्या को हल करने के लिए चरणों का वर्णन करेंगे।

उपरोक्त ग्राफ से, निम्न तालिका तैयार की जाती है।

	1	2	3	4
1	0	10	15	20
2	5	0	9	10
3	6	13	0	12
4	8	8	9	0

स = Φ

$$\small Cost (2,\Phi,1) = d (2,1) = 5\small Cost(2,\Phi,1)=d(2,1)=5$$

$$\small Cost (3,\Phi,1) = d (3,1) = 6\small Cost(3,\Phi,1)=d(3,1)=6$$

$$\small Cost (4,\Phi,1) = d (4,1) = 8\small Cost(4,\Phi,1)=d(4,1)=8$$

एस = 1

$$\small Cost (i,s) = min \lbrace Cost (j,s – (j)) + d [i,j]\rbrace\small Cost (i,s)=min \lbrace Cost (j,s)-(j))+ d [i,j]\rbrace$$

$$\small Cost (2,\lbrace 3 \rbrace,1) = d [2,3] + Cost (3,\Phi,1) = 9 + 6 = 15cost(2,\lbrace3 \rbrace,1)=d[2,3]+cost(3,\Phi ,1)=9+6=15$$

$$\small Cost (2,\lbrace 4 \rbrace,1) = d [2,4] + Cost (4,\Phi,1) = 10 + 8 = 18cost(2,\lbrace4 \rbrace,1)=d[2,4]+cost(4,\Phi,1)=10+8=18$$

$$\small Cost (3,\lbrace 2 \rbrace,1) = d [3,2] + Cost (2,\Phi,1) = 13 + 5 = 18cost(3,\lbrace2 \rbrace,1)=d[3,2]+cost(2,\Phi,1)=13+5=18$$

$$\small Cost (3,\lbrace 4 \rbrace,1) = d [3,4] + Cost (4,\Phi,1) = 12 + 8 = 20cost(3,\lbrace4 \rbrace,1)=d[3,4]+cost(4,\Phi,1)=12+8=20$$

$$\small Cost (4,\lbrace 3 \rbrace,1) = d [4,3] + Cost (3,\Phi,1) = 9 + 6 = 15cost(4,\lbrace3 \rbrace,1)=d[4,3]+cost(3,\Phi,1)=9+6=15$$

$$\small Cost (4,\lbrace 2 \rbrace,1) = d [4,2] + Cost (2,\Phi,1) = 8 + 5 = 13cost(4,\lbrace2 \rbrace,1)=d[4,2]+cost(2,\Phi,1)=8+5=13$$

एस = 2

$$\small Cost(2, \lbrace 3, 4 \rbrace, 1)=\begin{cases}d[2, 3] + Cost(3, \lbrace 4 \rbrace, 1) = 9 + 20 = 29\\d[2, 4] + Cost(4, \lbrace 3 \rbrace, 1) = 10 + 15 = 25=25\small Cost (2,\lbrace 3,4 \rbrace,1)\\\lbrace d[2,3]+ \small cost(3,\lbrace4\rbrace,1)=9+20=29d[2,4]+ \small Cost (4,\lbrace 3 \rbrace ,1)=10+15=25\end{cases}= 25$$

$$\small Cost(3, \lbrace 2, 4 \rbrace, 1)=\begin{cases}d[3, 2] + Cost(2, \lbrace 4 \rbrace, 1) = 13 + 18 = 31\\d[3, 4] + Cost(4, \lbrace 2 \rbrace, 1) = 12 + 13 = 25=25\small Cost (3,\lbrace 2,4 \rbrace,1)\\\lbrace d[3,2]+ \small cost(2,\lbrace4\rbrace,1)=13+18=31d[3,4]+ \small Cost (4,\lbrace 2 \rbrace ,1)=12+13=25\end{cases}= 25$$

$$\small Cost(4, \lbrace 2, 3 \rbrace, 1)=\begin{cases}d[4, 2] + Cost(2, \lbrace 3 \rbrace, 1) = 8 + 15 = 23\\d[4, 3] + Cost(3, \lbrace 2 \rbrace, 1) = 9 + 18 = 27=23\small Cost (4,\lbrace 2,3 \rbrace,1)\\\lbrace d[4,2]+ \small cost(2,\lbrace3\rbrace,1)=8+15=23d[4,3]+ \small Cost (3,\lbrace 2 \rbrace ,1)=9+18=27\end{cases}= 23$$

एस = ३

$$\small Cost(1, \lbrace 2, 3, 4 \rbrace, 1)=\begin{cases}d[1, 2] + Cost(2, \lbrace 3, 4 \rbrace, 1) = 10 + 25 = 35\\d[1, 3] + Cost(3, \lbrace 2, 4 \rbrace, 1) = 15 + 25 = 40\\d[1, 4] + Cost(4, \lbrace 2, 3 \rbrace, 1) = 20 + 23 = 43=35 cost(1,\lbrace 2,3,4 \rbrace),1)\\d[1,2]+cost(2,\lbrace 3,4 \rbrace,1)=10+25=35\\d[1,3]+cost(3,\lbrace 2,4 \rbrace,1)=15+25=40\\d[1,4]+cost(4,\lbrace 2,3 \rbrace ,1)=20+23=43=35\end{cases}$$

न्यूनतम लागत पथ 35 है।

लागत से शुरू करें {1, {2, 3, 4}, 1}, हम के लिए न्यूनतम मूल्य मिलता है d [1, 2]। कबs = 3, 1 से 2 तक पथ चुनें (लागत 10 है) फिर पीछे की ओर जाएं। कबs = 2, हम के लिए न्यूनतम मूल्य मिलता है d [4, 2]। 2 से 4 तक पथ का चयन करें (लागत 10 है) फिर पीछे की ओर जाएं।

कब s = 1, हम के लिए न्यूनतम मूल्य मिलता है d [4, 3]। पथ 4 से 3 का चयन करना (लागत 9 है), फिर हम तब तक जाएंगेs = Φकदम। हमें न्यूनतम मूल्य मिलता हैd [3, 1] (लागत 6 है)।

एक बाइनरी सर्च ट्री (BST) एक ऐसा पेड़ है जहां आंतरिक नोड्स में मुख्य मान संग्रहीत किए जाते हैं। बाहरी नोड्स नल नोड्स हैं। कुंजी को लेक्सिकोग्राफ़िक रूप से क्रमबद्ध किया गया है, अर्थात प्रत्येक आंतरिक नोड के लिए बाएं उप-ट्री की सभी कुंजी नोड की कुंजियों से कम है, और दाएँ उप-ट्री की सभी कुंजियाँ अधिक हैं।

जब हम चाबियों में से प्रत्येक को खोजने की आवृत्ति जानते हैं, तो पेड़ में प्रत्येक नोड तक पहुंचने की अपेक्षित लागत की गणना करना काफी आसान है। एक इष्टतम बाइनरी सर्च ट्री एक BST है, जिसमें प्रत्येक नोड का पता लगाने की न्यूनतम अपेक्षित लागत होती है

BST में एक तत्व का खोज समय है O(n), जबकि एक संतुलित-बीएसटी खोज समय है O(log n)। ऑप्टिमल कॉस्ट बाइनरी सर्च ट्री में फिर से खोज समय में सुधार किया जा सकता है, सबसे अधिक बार उपयोग किए जाने वाले डेटा को रूट में और रूट तत्व के करीब रखते हुए, पत्तियों के पास और पत्तियों में कम से कम अक्सर उपयोग किए गए डेटा को रखते हुए।

यहाँ, इष्टतम बाइनरी सर्च ट्री एल्गोरिथम प्रस्तुत किया गया है। पहले, हम प्रदान किए गए सेट से एक BST बनाते हैंn अलग-अलग चाबियों की संख्या < k₁, k₂, k₃, ... k_n >। यहाँ हम मानते हैं, एक कुंजी तक पहुँचने की संभावनाK_i है p_i। कुछ डमी कुंजी (d₀, d₁, d₂, ... d_n) जोड़े जाते हैं क्योंकि कुछ खोज उन मानों के लिए किए जा सकते हैं जो कुंजी सेट में मौजूद नहीं हैं K। हम मानते हैं, प्रत्येक डमी कुंजी के लिएd_i पहुंच की संभावना है q_i।

Optimal-Binary-Search-Tree(p, q, n) 
e[1…n + 1, 0…n],  
w[1…n + 1, 0…n], 
root[1…n + 1, 0…n]  
for i = 1 to n + 1 do 
   e[i, i - 1] := qi - 1 
   w[i, i - 1] := qi - 1  
for l = 1 to n do 
   for i = 1 to n – l + 1 do 
      j = i + l – 1 e[i, j] := ∞ 
      w[i, i] := w[i, i -1] + pj + qj 
      for r = i to j do 
         t := e[i, r - 1] + e[r + 1, j] + w[i, j] 
         if t < e[i, j] 
            e[i, j] := t 
            root[i, j] := r 
return e and root

विश्लेषण

एल्गोरिथ्म की आवश्यकता है O (n³) समय, तीन नेस्टेड के बाद से forछोरों का उपयोग किया जाता है। इनमें से प्रत्येक लूप सबसे अधिक लेता हैn मान।

उदाहरण

निम्नलिखित पेड़ को ध्यान में रखते हुए, लागत 2.80 है, हालांकि यह एक इष्टतम परिणाम नहीं है।

नोड	गहराई	संभावना	योगदान
k १	1	0.15	0.30
के २	0	0.10	0.10
के ३	2	0.05	0.15
के ४	1	0.10	0.20
के ५	2	0.20	0.60
घ ०	2	0.05	0.15
घ १	2	0.10	0.30
घ २	3	0.05	0.20
घ ३	3	0.05	0.20
घ ४	3	0.05	0.20
घ ५	3	0.10	0.40
Total			2.80

एक इष्टतम समाधान प्राप्त करने के लिए, इस अध्याय में चर्चा किए गए एल्गोरिथ्म का उपयोग करके, निम्न तालिकाओं को उत्पन्न किया जाता है।

निम्नलिखित तालिकाओं में, स्तंभ सूचकांक है i और पंक्ति सूचकांक है j।

इ	1	2	3	4	5	6
5	2.75	2.00	1.30	0.90	0.50	0.10
4	1.75	1.20	0.60	0.30	0.05
3	1.25	0.70	0.25	0.05
2	0.90	0.40	0.05
1	0.45	0.10
0	0.05

w	1	2	3	4	5	6
5	1.00	0.80	0.60	0.50	0.35	0.10
4	0.70	0.50	0.30	0.20	0.05
3	0.55	0.35	0.15	0.05
2	0.45	0.25	0.05
1	0.30	0.10
0	0.05

जड़	1	2	3	4	5
5	2	4	5	5	5
4	2	2	4	4
3	2	2	3
2	1	2
1	1

From these tables, the optimal tree can be formed.

There are several types of heaps, however in this chapter, we are going to discuss binary heap. A binary heap is a data structure, which looks similar to a complete binary tree. Heap data structure obeys ordering properties discussed below. Generally, a Heap is represented by an array. In this chapter, we are representing a heap by H.

As the elements of a heap is stored in an array, considering the starting index as 1, the position of the parent node of i^th element can be found at ⌊ i/2 ⌋ . Left child and right child of i^th node is at position 2i and 2i + 1.

A binary heap can be classified further as either a max-heap or a min-heap based on the ordering property.

Max-Heap

In this heap, the key value of a node is greater than or equal to the key value of the highest child.

Hence, H[Parent(i)] ≥ H[i]

Min-Heap

In mean-heap, the key value of a node is lesser than or equal to the key value of the lowest child.

Hence, H[Parent(i)] ≤ H[i]

In this context, basic operations are shown below with respect to Max-Heap. Insertion and deletion of elements in and from heaps need rearrangement of elements. Hence, Heapify function needs to be called.

Array Representation

A complete binary tree can be represented by an array, storing its elements using level order traversal.

Let us consider a heap (as shown below) which will be represented by an array H.

Considering the starting index as 0, using level order traversal, the elements are being kept in an array as follows.

Index	0	1	2	3	4	5	6	7	8	...
elements	70	30	50	12	20	35	25	4	8	...

In this context, operations on heap are being represented with respect to Max-Heap.

To find the index of the parent of an element at index i, the following algorithm Parent (numbers[], i) is used.

Algorithm: Parent (numbers[], i) 
if i == 1 
   return NULL 
else 
   [i / 2]

The index of the left child of an element at index i can be found using the following algorithm, Left-Child (numbers[], i).

Algorithm: Left-Child (numbers[], i) 
If 2 * i ≤ heapsize 
   return [2 * i] 
else 
   return NULL

The index of the right child of an element at index i can be found using the following algorithm, Right-Child(numbers[], i).

Algorithm: Right-Child (numbers[], i) 
if 2 * i < heapsize 
   return [2 * i + 1] 
else 
   return NULL

To insert an element in a heap, the new element is initially appended to the end of the heap as the last element of the array.

After inserting this element, heap property may be violated, hence the heap property is repaired by comparing the added element with its parent and moving the added element up a level, swapping positions with the parent. This process is called percolation up.

The comparison is repeated until the parent is larger than or equal to the percolating element.

Algorithm: Max-Heap-Insert (numbers[], key) 
heapsize = heapsize + 1 
numbers[heapsize] = -∞ 
i = heapsize 
numbers[i] = key 
while i > 1 and numbers[Parent(numbers[], i)] < numbers[i] 
   exchange(numbers[i], numbers[Parent(numbers[], i)]) 
   i = Parent (numbers[], i)

Analysis

Initially, an element is being added at the end of the array. If it violates the heap property, the element is exchanged with its parent. The height of the tree is log n. Maximum log n number of operations needs to be performed.

Hence, the complexity of this function is O(log n).

Example

Let us consider a max-heap, as shown below, where a new element 5 needs to be added.

Initially, 55 will be added at the end of this array.

After insertion, it violates the heap property. Hence, the element needs to swap with its parent. After swap, the heap looks like the following.

Again, the element violates the property of heap. Hence, it is swapped with its parent.

Now, we have to stop.

Heapify method rearranges the elements of an array where the left and right sub-tree of i^th element obeys the heap property.

Algorithm: Max-Heapify(numbers[], i) 
leftchild := numbers[2i] 
rightchild := numbers [2i + 1] 
if leftchild ≤ numbers[].size and numbers[leftchild] > numbers[i] 
   largest := leftchild 
else 
   largest := i 
if rightchild ≤ numbers[].size and numbers[rightchild] > numbers[largest] 
   largest := rightchild 
if largest ≠ i 
   swap numbers[i] with numbers[largest] 
   Max-Heapify(numbers, largest)

When the provided array does not obey the heap property, Heap is built based on the following algorithm Build-Max-Heap (numbers[]).

Algorithm: Build-Max-Heap(numbers[]) 
numbers[].size := numbers[].length 
fori = ⌊ numbers[].length/2 ⌋ to 1 by -1 
   Max-Heapify (numbers[], i)

Extract method is used to extract the root element of a Heap. Following is the algorithm.

Algorithm: Heap-Extract-Max (numbers[]) 
max = numbers[1] 
numbers[1] = numbers[heapsize] 
heapsize = heapsize – 1 
Max-Heapify (numbers[], 1) 
return max

Example

Let us consider the same example discussed previously. Now we want to extract an element. This method will return the root element of the heap.

After deletion of the root element, the last element will be moved to the root position.

Now, Heapify function will be called. After Heapify, the following heap is generated.

Bubble Sort is an elementary sorting algorithm, which works by repeatedly exchanging adjacent elements, if necessary. When no exchanges are required, the file is sorted.

This is the simplest technique among all sorting algorithms.

Algorithm: Sequential-Bubble-Sort (A) 
fori← 1 to length [A] do 
for j ← length [A] down-to i +1 do 
   if A[A] < A[j - 1] then 
      Exchange A[j] ↔ A[j-1]

Implementation

voidbubbleSort(int numbers[], intarray_size) { 
   inti, j, temp; 
   for (i = (array_size - 1); i >= 0; i--) 
   for (j = 1; j <= i; j++) 
      if (numbers[j - 1] > numbers[j]) { 
         temp = numbers[j-1]; 
         numbers[j - 1] = numbers[j]; 
         numbers[j] = temp; 
      } 
}

Analysis

Here, the number of comparisons are

1 + 2 + 3 +...+ (n - 1) = n(n - 1)/2 = O(n²)

Clearly, the graph shows the n² nature of the bubble sort.

In this algorithm, the number of comparison is irrespective of the data set, i.e. whether the provided input elements are in sorted order or in reverse order or at random.

Memory Requirement

From the algorithm stated above, it is clear that bubble sort does not require extra memory.

Example

Unsorted list:

5 2 1 4 3 7 6

1^st iteration:

5 > 2 swap	2 5 1 4 3 7 6
5 > 1 swap	2 1 5 4 3 7 6
5 > 4 swap	2 1 4 5 3 7 6
5 > 3 swap	2 1 4 3 5 7 6
5 < 7 no swap	2 1 4 3 5 7 6
7 > 6 swap	2 1 4 3 5 6 7

2^nd iteration:

2 > 1 swap	1 2 4 3 5 6 7
2 < 4 no swap	1 2 4 3 5 6 7
4 > 3 swap	1 2 3 4 5 6 7
4 < 5 no swap	1 2 3 4 5 6 7
5 < 6 no swap	1 2 3 4 5 6 7

There is no change in 3^rd, 4^th, 5^th and 6^th iteration.

Finally,

the sorted list is

1 2 3 4 5 6 7

Insertion sort is a very simple method to sort numbers in an ascending or descending order. This method follows the incremental method. It can be compared with the technique how cards are sorted at the time of playing a game.

The numbers, which are needed to be sorted, are known as keys. Here is the algorithm of the insertion sort method.

Algorithm: Insertion-Sort(A) 
for j = 2 to A.length 
   key = A[j] 
   i = j – 1 
   while i > 0 and A[i] > key 
      A[i + 1] = A[i] 
      i = i -1 
   A[i + 1] = key

Analysis

Run time of this algorithm is very much dependent on the given input.

If the given numbers are sorted, this algorithm runs in O(n) time. If the given numbers are in reverse order, the algorithm runs in O(n²) time.

Example

Unsorted list:

2 13 5 18 14

1^st iteration:

Key = a[2] = 13

a[1] = 2 < 13

Swap, no swap

2 13 5 18 14

2^nd iteration:

Key = a[3] = 5

a[2] = 13 > 5

Swap 5 and 13

2 5 13 18 14

Next, a[1] = 2 < 13

Swap, no swap

2 5 13 18 14

3^rd iteration:

Key = a[4] = 18

a[3] = 13 < 18,

a[2] = 5 < 18,

a[1] = 2 < 18

Swap, no swap

2 5 13 18 14

4^th iteration:

Key = a[5] = 14

a[4] = 18 > 14

Swap 18 and 14

2 5 13 14 18

Next, a[3] = 13 < 14,

a[2] = 5 < 14,

a[1] = 2 < 14

So, no swap

2 5 13 14 18

Finally,

the sorted list is

2 5 13 14 18

This type of sorting is called Selection Sort as it works by repeatedly sorting elements. It works as follows: first find the smallest in the array and exchange it with the element in the first position, then find the second smallest element and exchange it with the element in the second position, and continue in this way until the entire array is sorted.

Algorithm: Selection-Sort (A) 
fori ← 1 to n-1 do 
   min j ← i; 
   min x ← A[i] 
   for j ←i + 1 to n do 
      if A[j] < min x then 
         min j ← j 
         min x ← A[j] 
   A[min j] ← A [i] 
   A[i] ← min x

Selection sort is among the simplest of sorting techniques and it works very well for small files. It has a quite important application as each item is actually moved at the most once.

Section sort is a method of choice for sorting files with very large objects (records) and small keys. The worst case occurs if the array is already sorted in a descending order and we want to sort them in an ascending order.

Nonetheless, the time required by selection sort algorithm is not very sensitive to the original order of the array to be sorted: the test if A[j] < min x is executed exactly the same number of times in every case.

Selection sort spends most of its time trying to find the minimum element in the unsorted part of the array. It clearly shows the similarity between Selection sort and Bubble sort.

• Bubble sort selects the maximum remaining elements at each stage, but wastes some effort imparting some order to an unsorted part of the array.

• Selection sort is quadratic in both the worst and the average case, and requires no extra memory.

For each i from 1 to n - 1, there is one exchange and n - i comparisons, so there is a total of n - 1 exchanges and

(n − 1) + (n − 2) + ...+ 2 + 1 = n(n − 1)/2 comparisons.

These observations hold, no matter what the input data is.

In the worst case, this could be quadratic, but in the average case, this quantity is O(n log n). It implies that the running time of Selection sort is quite insensitive to the input.

Implementation

Void Selection-Sort(int numbers[], int array_size) { 
   int i, j; 
   int min, temp;  
   for (i = 0; I < array_size-1; i++) { 
      min = i; 
      for (j = i+1; j < array_size; j++) 
         if (numbers[j] < numbers[min]) 
            min = j; 
      temp = numbers[i]; 
      numbers[i] = numbers[min]; 
      numbers[min] = temp; 
   } 
}

Example

Unsorted list:

5 2 1 4 3

1^st iteration:

Smallest = 5

2 < 5, smallest = 2

1 < 2, smallest = 1

4 > 1, smallest = 1

3 > 1, smallest = 1

Swap 5 and 1

1 2 5 4 3

2^nd iteration:

Smallest = 2

2 < 5, smallest = 2

2 < 4, smallest = 2

2 < 3, smallest = 2

No Swap

1 2 5 4 3

3^rd iteration:

Smallest = 5

4 < 5, smallest = 4

3 < 4, smallest = 3

Swap 5 and 3

1 2 3 4 5

4^th iteration:

Smallest = 4

4 < 5, smallest = 4

No Swap

1 2 3 4 5

Finally,

the sorted list is

1 2 3 4 5

It is used on the principle of divide-and-conquer. Quick sort is an algorithm of choice in many situations as it is not difficult to implement. It is a good general purpose sort and it consumes relatively fewer resources during execution.

Advantages

• It is in-place since it uses only a small auxiliary stack.

• It requires only n (log n) time to sort n items.

• It has an extremely short inner loop.

• This algorithm has been subjected to a thorough mathematical analysis, a very precise statement can be made about performance issues.

Disadvantages

• It is recursive. Especially, if recursion is not available, the implementation is extremely complicated.

• It requires quadratic (i.e., n2) time in the worst-case.

• It is fragile, i.e. a simple mistake in the implementation can go unnoticed and cause it to perform badly.

Quick sort works by partitioning a given array A[p ... r] into two non-empty sub array A[p ... q] and A[q+1 ... r] such that every key in A[p ... q] is less than or equal to every key in A[q+1 ... r].

Then, the two sub-arrays are sorted by recursive calls to Quick sort. The exact position of the partition depends on the given array and index q is computed as a part of the partitioning procedure.

Algorithm: Quick-Sort (A, p, r) 
if p < r then 
   q Partition (A, p, r) 
   Quick-Sort (A, p, q) 
   Quick-Sort (A, q + r, r)

Note that to sort the entire array, the initial call should be Quick-Sort (A, 1, length[A])

As a first step, Quick Sort chooses one of the items in the array to be sorted as pivot. Then, the array is partitioned on either side of the pivot. Elements that are less than or equal to pivot will move towards the left, while the elements that are greater than or equal to pivot will move towards the right.

Partitioning the Array

Partitioning procedure rearranges the sub-arrays in-place.

Function: Partition (A, p, r) 
x ← A[p] 
i ← p-1 
j ← r+1 
while TRUE do 
   Repeat j ← j - 1 
   until A[j] ≤ x  
   Repeat i← i+1 
   until A[i] ≥ x  
   if i < j then  
      exchange A[i] ↔ A[j] 
   else  
      return j

Analysis

The worst case complexity of Quick-Sort algorithm is O(n²). However using this technique, in average cases generally we get the output in O(n log n) time.

Radix sort is a small method that many people intuitively use when alphabetizing a large list of names. Specifically, the list of names is first sorted according to the first letter of each name, that is, the names are arranged in 26 classes.

Intuitively, one might want to sort numbers on their most significant digit. However, Radix sort works counter-intuitively by sorting on the least significant digits first. On the first pass, all the numbers are sorted on the least significant digit and combined in an array. Then on the second pass, the entire numbers are sorted again on the second least significant digits and combined in an array and so on.

Algorithm: Radix-Sort (list, n) 
shift = 1 
for loop = 1 to keysize do 
   for entry = 1 to n do 
      bucketnumber = (list[entry].key / shift) mod 10 
      append (bucket[bucketnumber], list[entry]) 
   list = combinebuckets() 
   shift = shift * 10

विश्लेषण

प्रत्येक कुंजी को प्रत्येक अंक के लिए एक बार देखा जाता है (या यदि कुंजी अक्षर हैं तो सबसे लंबी कुंजी)। इसलिए, अगर सबसे लंबी कुंजी हैm अंक और हैं n चाबियाँ, मूलांक क्रम में आदेश हैं O(m.n)।

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

यहां, हम देखते हैं कि कुंजियों का आकार महत्वपूर्ण नहीं है, और यह एल्गोरिथ्म रैखिक जटिलता का है O(n)।

उदाहरण

निम्नलिखित उदाहरण से पता चलता है कि मूलांक सात सात अंकों की संख्या पर कैसे संचालित होता है।

इनपुट	1 सेंट पास	2 एन डी पास	3 rd पास
329	720	720	329
457	355	329	355
657	436	436	436
839	457	839	457
436	657	355	657
720	329	457	720
355	839	657	839

उपरोक्त उदाहरण में, पहला कॉलम इनपुट है। तेजी से महत्वपूर्ण अंकों की स्थिति के बाद शेष कॉलम सूची को क्रमिक रूप से दिखाते हैं। मूलांक सॉर्ट के लिए कोड मानता है कि एक सरणी में प्रत्येक तत्वA का n तत्वों की है d अंक, जहां अंक 1 सबसे कम-क्रम अंक और है d उच्चतम-क्रम अंक है।

कक्षा को समझने के लिए P तथा NP, पहले हमें कम्प्यूटेशनल मॉडल को जानना चाहिए। इसलिए, इस अध्याय में हम दो महत्वपूर्ण कम्प्यूटेशनल मॉडल पर चर्चा करेंगे।

नियतात्मक संगणना और कक्षा पी

नियतात्मक ट्यूरिंग मशीन

इन मॉडलों में से एक नियतात्मक एक-टेप ट्यूरिंग मशीन है। इस मशीन में एक परिमित राज्य नियंत्रण, एक रीड-राइट हेड और अनंत अनुक्रम के साथ एक दो-तरफा टेप होता है।

निम्नलिखित एक नियतात्मक एक-टेप ट्यूरिंग मशीन का योजनाबद्ध आरेख है।

नियतात्मक ट्यूरिंग मशीन के लिए एक कार्यक्रम निम्नलिखित जानकारी निर्दिष्ट करता है -

• टेप प्रतीकों का एक परिमित सेट (इनपुट प्रतीक और एक खाली प्रतीक)
• राज्यों का एक निर्धारित सेट
• एक संक्रमण समारोह

एल्गोरिदमिक विश्लेषण में, यदि कोई समस्या नियतात्मक एक टेप ट्यूरिंग मशीन द्वारा बहुपद समय में हल करने योग्य है, तो समस्या P वर्ग की है।

Nondeterministic कम्प्यूटेशन और क्लास एनपी

नॉनडेर्मिनिस्टिक ट्यूरिंग मशीन

कम्प्यूटेशनल समस्या को हल करने के लिए, एक और मॉडल गैर-नियतात्मक ट्यूरिंग मशीन (एनडीटीएम) है। एनडीटीएम की संरचना डीटीएम के समान है, हालांकि यहां हमारे पास एक अतिरिक्त मॉड्यूल है जिसे अनुमान लगाने वाले मॉड्यूल के रूप में जाना जाता है, जो एक राइट-ओनली हेड के साथ जुड़ा हुआ है।

निम्नलिखित योजनाबद्ध आरेख है।

यदि समस्या गैर-निर्धारक ट्यूरिंग मशीन द्वारा बहुपद समय में हल है, तो समस्या एनपी वर्ग की है।

एक अप्रत्यक्ष ग्राफ में, ए cliqueदिए गए ग्राफ का पूरा उप-ग्राफ है। पूर्ण उप-ग्राफ़ का अर्थ है, इस उप-ग्राफ़ के सभी कोने इस उप-ग्राफ़ के अन्य सभी कोने से जुड़े हुए हैं।

मैक्स-क्लिक समस्या ग्राफ के अधिकतम क्लिक को खोजने की कम्प्यूटेशनल समस्या है। मैक्स क्लिक का उपयोग कई वास्तविक दुनिया की समस्याओं में किया जाता है।

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

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

Algorithm: Max-Clique (G, n, k) 
S := Φ 
for i = 1 to k do 
   t := choice (1…n)  
   if t Є S then 
      return failure 
   S := S ∪ t  
for all pairs (i, j) such that i Є S and j Є S and i ≠ j do 
   if (i, j) is not a edge of the graph then  
      return failure 
return success

विश्लेषण

मैक्स-क्लिक समस्या एक गैर-नियतात्मक एल्गोरिथ्म है। इस एल्गोरिथ्म में, पहले हम एक सेट को निर्धारित करने का प्रयास करते हैंk अलग-अलग कोने और फिर हम यह जांचने की कोशिश करते हैं कि क्या ये कोने एक पूरा ग्राफ बनाते हैं।

इस समस्या को हल करने के लिए कोई बहुपद समय नियतात्मक एल्गोरिथ्म नहीं है। यह समस्या एनपी-पूर्ण है।

उदाहरण

निम्नलिखित ग्राफ पर एक नज़र डालें। यहाँ, उप-ग्राफ जिसमें कोने 2, 3, 4 और 6 हैं, एक पूरा ग्राफ बनाता है। इसलिए, यह उप-ग्राफ एक हैclique। चूंकि यह प्रदान किए गए ग्राफ का अधिकतम पूर्ण उप-ग्राफ है, यह ए है4-Clique।

अप्रत्यक्ष ग्राफ का एक शीर्ष-आवरण G = (V, E) कोने का एक सबसेट है V^' ⊆ V ऐसे कि अगर धार (u, v) की एक बढ़त है G, तो कोई u में V या v में V^' अथवा दोनों।

दिए गए अप्रत्यक्ष ग्राफ में अधिकतम आकार का एक शीर्ष-आवरण प्राप्त करें। यह इष्टतम वर्टेन्कोवर एक एनपी-पूर्ण समस्या का अनुकूलन संस्करण है। हालांकि, यह एक शीर्ष-आवरण को खोजने के लिए बहुत कठिन नहीं है जो इष्टतम के पास है।

APPROX-VERTEX_COVER (G: Graph) c ← { } E' ← E[G] 
while E' is not empty do 
   Let (u, v) be an arbitrary edge of E' c ← c U {u, v} 
   Remove from E' every edge incident on either u or v 
return c

उदाहरण

दिए गए ग्राफ के किनारों का समूह है -

{(1,6),(1,2),(1,4),(2,3),(2,4),(6,7),(4,7),(7,8),(3,8),(3,5),(8,5)}

अब, हम एक मनमाना बढ़त (1,6) का चयन करके शुरू करते हैं। हम सभी किनारों को खत्म कर देते हैं, जो या तो 1 या 6 के शीर्ष पर होते हैं और हम कवर करने के लिए किनारे (1,6) जोड़ते हैं।

अगले चरण में, हमने यादृच्छिक पर एक और बढ़त (2,3) को चुना है

अब हम दूसरे किनारे (4,7) का चयन करते हैं।

हम दूसरे किनारे (8,5) का चयन करते हैं।

इसलिए, इस ग्राफ का शीर्ष कवर {1,2,4,5} है।

विश्लेषण

यह देखना आसान है कि इस एल्गोरिदम का रनिंग टाइम क्या है O(V + E), का प्रतिनिधित्व करने के लिए आसन्न सूची का उपयोग कर E^'।

कंप्यूटर विज्ञान में, कई समस्याएं हल की जाती हैं जहां उद्देश्य कुछ मूल्यों को अधिकतम या कम करना है, जबकि अन्य समस्याओं में हम यह खोजने की कोशिश करते हैं कि कोई समाधान है या नहीं। इसलिए, समस्याओं को निम्नानुसार वर्गीकृत किया जा सकता है -

अनुकूलन समस्या

अनुकूलन समस्याएं वे हैं जिनके लिए उद्देश्य कुछ मूल्यों को अधिकतम या कम करना है। उदाहरण के लिए,

• दिए गए ग्राफ़ को रंग देने के लिए आवश्यक न्यूनतम रंगों की खोज करना।

• एक ग्राफ में दो कोने के बीच सबसे छोटा रास्ता खोजना।

निर्णय की समस्या

ऐसी कई समस्याएं हैं जिनके लिए उत्तर हां या नहीं है। इन प्रकार की समस्याओं के रूप में जाना जाता है decision problems। उदाहरण के लिए,

• क्या किसी दिए गए ग्राफ को केवल 4 रंगों में रंगा जा सकता है।

• ग्राफ में हैमिल्टनियन चक्र खोजना कोई निर्णय समस्या नहीं है, जबकि ग्राफ की जाँच करना हैमिल्टनियन है या नहीं यह निर्णय समस्या है।

भाषा क्या है?

हर निर्णय समस्या के केवल दो उत्तर हो सकते हैं, हाँ या नहीं। इसलिए, एक निर्णय समस्या एक भाषा के लिए हो सकती है यदि यह एक विशिष्ट इनपुट के लिए उत्तर 'हां' प्रदान करती है। एक भाषा आदानों की समग्रता है जिसके लिए उत्तर हां है। पिछले अध्यायों में चर्चा किए गए अधिकांश एल्गोरिदम हैंpolynomial time algorithms।

इनपुट आकार के लिए n, अगर एल्गोरिथम का सबसे खराब समय जटिलता है O(n^k), कहाँ पे k एक निरंतरता है, एल्गोरिथ्म एक बहुपद समय एल्गोरिथ्म है।

मैट्रिक्स चेन मल्टीप्लिमेंटेशन, सिंगल सोर्स शॉर्टेस्ट पाथ, ऑल पेयर शॉर्टेस्ट पाथ, मिनिमम स्पैनिंग ट्री आदि जैसे एल्गोरिदम बहुपद काल में चलते हैं। हालांकि कई समस्याएं हैं, जैसे यात्रा करने वाले विक्रेता, इष्टतम ग्राफ रंग, हैमिल्टनियन चक्र, एक ग्राफ में सबसे लंबा रास्ता खोजना, और एक बूलियन सूत्र को संतुष्ट करना, जिसके लिए कोई बहुपद समय एल्गोरिदम ज्ञात नहीं है। ये समस्याएं समस्याओं के एक दिलचस्प वर्ग से संबंधित हैं, जिन्हें कहा जाता हैNP-Complete समस्याएं, जिनकी स्थिति अज्ञात है।

इस संदर्भ में, हम समस्याओं को निम्नानुसार वर्गीकृत कर सकते हैं -

पी वर्ग

कक्षा P में उन समस्याओं का समावेश होता है जो बहुपद समय में हल करने योग्य होती हैं, अर्थात इन समस्याओं को समय रहते हल किया जा सकता है O(n^k) सबसे खराब स्थिति में, कहाँ k स्थिर है।

इन समस्याओं को कहा जाता है tractable, जबकि दूसरों को बुलाया जाता है intractable or superpolynomial।

औपचारिक रूप से, एक एल्गोरिथ्म बहुपद समय एल्गोरिथ्म है, यदि एक बहुपद मौजूद है p(n) एल्गोरिथ्म आकार के किसी भी उदाहरण को हल कर सकता है n एक समय में O(p(n))।

समस्या की आवश्यकता है Ω(n⁵⁰) हल करने के लिए समय अनिवार्य रूप से बड़े के लिए अव्यावहारिक है n। अधिकांश ज्ञात बहुपद समय एल्गोरिथ्म समय में चलते हैंO(n^k) के काफी कम मूल्य के लिए k।

बहुपद-काल के एल्गोरिदम के वर्ग पर विचार करने में लाभ यह है कि सभी उचित हैं deterministic single processor model of computation एक बहुपत्नी धीमे-धीमे से एक दूसरे पर अनुकरण किया जा सकता है

एनपी क्लास

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

इस वर्ग की हर समस्या का विस्तृत समय पर हल किया जा सकता है।

पी बनाम एनपी

प्रत्येक निर्णय समस्या जो एक नियतात्मक बहुपद समय एल्गोरिथ्म द्वारा हल करने योग्य है, एक बहुपद समय गैर-नियतात्मक एल्गोरिथ्म द्वारा भी हल की जा सकती है।

पी में सभी समस्याओं को बहुपद समय एल्गोरिदम के साथ हल किया जा सकता है, जबकि एनपी - पी में सभी समस्याएं अचूक हैं।

यह ज्ञात नहीं है कि क्या P = NP। हालांकि, एनपी में कई समस्याओं को संपत्ति के साथ जाना जाता है यदि वे पी से संबंधित हैं, तो यह साबित किया जा सकता है कि पी = एनपी।

अगर P ≠ NPएनपी में समस्याएं हैं जो न तो पी में हैं और न ही एनपी-पूर्ण में हैं।

समस्या वर्ग की है Pअगर समस्या का हल खोजना आसान है। समस्या किसकी हैNP, अगर यह एक समाधान की जांच करना आसान है जो खोजने के लिए बहुत थकाऊ हो सकता है।

स्टीफन कुक ने अपने पेपर "प्रमेय साबित करने की प्रक्रिया की जटिलता" में चार प्रमेय प्रस्तुत किए। ये प्रमेय नीचे दिए गए हैं। हम समझते हैं कि इस अध्याय में कई अज्ञात शब्दों का उपयोग किया जा रहा है, लेकिन हमारे पास विस्तार से सब कुछ पर चर्चा करने की कोई गुंजाइश नहीं है।

स्टीफन कुक द्वारा चार प्रमेय निम्नलिखित हैं -

प्रमेय -1

अगर एक सेट S स्ट्रिंग्स को कुछ गैर-नियतात्मक ट्यूरिंग मशीन द्वारा बहुपद समय के भीतर स्वीकार किया जाता है S P-reducible to {DNF tautologies} है।

प्रमेय -2

निम्नलिखित सेट जोड़े में एक दूसरे के लिए पी-रिड्यूसबल हैं (और इसलिए प्रत्येक में एक ही बहुपद की डिग्री है): {tautologies}, {DNF tautologies}, D3, {सब-ग्राफ जोड़े}।

प्रमेय -3

• किसी के लिए T_Q(k) प्रकार का Q, $\mathbf{\frac{T_{Q}(k)}{\frac{\sqrt{k}}{(log\:k)^2}}}$ अबाधित है

• वहां एक है T_Q(k) प्रकार का Q ऐसा है कि $T_{Q}(k)\leqslant 2^{k(log\:k)^2}$

प्रमेय -4

यदि स्ट्रिंग्स के सेट S को समय के भीतर एक गैर-नियतात्मक मशीन द्वारा स्वीकार किया जाता है T(n) = 2ⁿ, और अगर T_Q(k) प्रकार का एक ईमानदार (वास्तविक समय गणना योग्य) कार्य है Q, फिर एक स्थिरांक है K, इसलिए S समय के भीतर एक नियतात्मक मशीन द्वारा पहचाना जा सकता है T_Q(K8ⁿ)।

• सबसे पहले, उन्होंने बहुपद समय पुनर्विकास के महत्व पर जोर दिया। इसका मतलब है कि अगर हमारे पास एक समस्या से एक बहुपद समय में कमी है, तो यह सुनिश्चित करता है कि दूसरी समस्या से किसी भी बहुपद समय एल्गोरिथ्म को पहली समस्या के लिए एक समान बहुपद समय एल्गोरिथ्म में परिवर्तित किया जा सकता है।

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

• तीसरा, उन्होंने साबित किया कि एनपी में एक विशेष समस्या में संपत्ति है कि एनपी में हर दूसरी समस्या को बहुपत्नी रूप से कम किया जा सकता है। यदि बहुपद समय एल्गोरिथ्म के साथ संतोषजनकता समस्या को हल किया जा सकता है, तो एनपी में हर समस्या को बहुपद समय में भी हल किया जा सकता है। अगर एनपी में कोई भी समस्या असाध्य है, तो संतोषजनक समस्या अचूक होनी चाहिए। इस प्रकार, संतुष्टि की समस्या एनपी में सबसे कठिन समस्या है।

• चौथा, कुक ने सुझाव दिया कि एनपी में अन्य समस्याएं संतोष की समस्या के साथ साझा हो सकती हैं जो एनपी के सबसे कठिन सदस्य होने की संपत्ति है।

एक समस्या वर्ग एनपीसी में है अगर यह एनपी में है और जैसा है hardएनपी में किसी भी समस्या के रूप में। एक समस्या हैNP-hard अगर एनपी में सभी समस्याएं बहुपद समय के अनुकूल हैं, भले ही यह एनपी में ही न हो।

यदि इन समस्याओं में से किसी के लिए एक बहुपद समय एल्गोरिथ्म मौजूद है, तो एनपी में सभी समस्याएं बहुपद समय में हल हो जाएंगी। इन समस्याओं को कहा जाता हैNP-complete। एनपी-पूर्णता की घटना सैद्धांतिक और व्यावहारिक दोनों कारणों से महत्वपूर्ण है।

एनपी-पूर्णता की परिभाषा

एक भाषा B है NP-complete अगर यह दो शर्तों को पूरा करता है

• B एनपी में है

• हर एक A एनपी में बहुपद समय है B।

यदि एक भाषा दूसरी संपत्ति को संतुष्ट करती है, लेकिन जरूरी नहीं कि वह पहली भाषा हो B जाना जाता है NP-Hard। अनौपचारिक रूप से, एक खोज समस्याB है NP-Hard अगर कुछ मौजूद है NP-Complete मुसीबत A कि ट्यूरिंग कम हो जाती है B।

एनपी-हार्ड में समस्या को बहुपद समय में हल नहीं किया जा सकता है, जब तक P = NP। यदि कोई समस्या एनपीसी साबित होती है, तो इसके लिए एक कुशल एल्गोरिदम खोजने की कोशिश करने में समय बर्बाद करने की आवश्यकता नहीं है। इसके बजाय, हम डिजाइन सन्निकटन एल्गोरिदम पर ध्यान केंद्रित कर सकते हैं।

एनपी-पूर्ण समस्याएं

निम्नलिखित कुछ एनपी-पूर्ण समस्याएं हैं, जिनके लिए कोई बहुपद समय एल्गोरिथ्म ज्ञात नहीं है।

• यह निर्धारित करना कि क्या ग्राफ में हैमिल्टनियन चक्र है
• यह निर्धारित करना कि क्या बूलियन फॉर्मूला संतोषजनक है, आदि।

एनपी-हार्ड समस्याएं

एनपी-हार्ड निम्नलिखित समस्याएं हैं

• सर्किट-संतोषजनक समस्या
• कवर सेट करें
• वर्टेक्स कवर
• ट्रैवलिंग सेल्समैन की समस्या

इस संदर्भ में, अब हम टीएसपी एनपी-पूर्ण पर चर्चा करेंगे

टीएसपी एनपी-पूर्ण है

यात्रा सेल्समैन समस्या में एक सेल्समैन और शहरों का एक सेट शामिल है। सेल्समैन को एक निश्चित शहर से शुरू होने और उसी शहर में लौटने के लिए हर एक शहर का दौरा करना होगा। समस्या की चुनौती यह है कि यात्रा विक्रेता यात्रा की कुल लंबाई को कम करना चाहता है

प्रमाण

साबित करना TSP is NP-Complete, पहले हमें यह साबित करना होगा TSP belongs to NP। टीएसपी में, हम एक दौरा पाते हैं और जांचते हैं कि दौरे में एक बार प्रत्येक शीर्ष शामिल है। फिर दौरे के किनारों की कुल लागत की गणना की जाती है। अंत में, हम जाँचते हैं कि लागत न्यूनतम है या नहीं। यह बहुपद समय में पूरा किया जा सकता है। इस प्रकारTSP belongs to NP।

दूसरी बात, हमें यह साबित करना होगा TSP is NP-hard। यह साबित करने के लिए, एक तरीका यह दिखाना हैHamiltonian cycle ≤_p TSP (जैसा कि हम जानते हैं कि हैमिल्टन चक्र समस्या NPcomplete है)।

मान लीजिये G = (V, E) हैमिल्टन चक्र का एक उदाहरण है।

इसलिए, टीएसपी का एक उदाहरण निर्मित है। हम पूरा ग्राफ बनाते हैंG^' = (V, E^'), कहाँ पे

$$E^{'}=\lbrace(i, j)\colon i, j \in V \:\:and\:i\neq j$$

इस प्रकार, लागत समारोह निम्नानुसार परिभाषित किया गया है -

$$t(i,j)=\begin{cases}0 & if\: (i, j)\: \in E\\1 & otherwise\end{cases}$$

अब, मान लीजिए कि एक हैमिल्टन चक्र h में मौजूद है G। यह स्पष्ट है कि प्रत्येक किनारे की लागतh है 0 में G^' जैसा कि प्रत्येक किनारे का है E। इसलिए,h की लागत है 0 में G^'। इस प्रकार, यदि ग्राफG हैमिल्टनियन चक्र है, फिर ग्राफ G^' का दौरा है 0 लागत।

इसके विपरीत, हम यह मान लेते हैं G^' दौरा है h^' सबसे अधिक लागत की 0। में किनारों की लागतE^' कर रहे हैं 0 तथा 1परिभाषा से। इसलिए, प्रत्येक किनारे की लागत होनी चाहिए0 की लागत के रूप में h^' है 0। इसलिए हम यह निष्कर्ष निकालते हैंh^' केवल किनारों में है E।

हमने इस प्रकार सिद्ध किया है G हैमिल्टनियन चक्र है, यदि और केवल यदि G^' अधिक से अधिक लागत का दौरा किया है 0। टीएसपी एनपी-पूर्ण है।

पिछले अध्यायों में चर्चा किए गए एल्गोरिदम व्यवस्थित रूप से चलते हैं। लक्ष्य प्राप्त करने के लिए, समाधान की ओर एक या एक से अधिक पहले से खोजे गए रास्ते को इष्टतम समाधान खोजने के लिए संग्रहीत करने की आवश्यकता है।

कई समस्याओं के लिए, लक्ष्य के लिए रास्ता अप्रासंगिक है। उदाहरण के लिए, एन-क्वींस समस्या में, हमें रानियों के अंतिम विन्यास के साथ-साथ रानियों को जोड़ने के आदेश की परवाह करने की आवश्यकता नहीं है।

पहाड़ी की चढ़ाई

हिल क्लाइम्बिंग कुछ अनुकूलन समस्याओं को हल करने की एक तकनीक है। इस तकनीक में, हम एक उप-इष्टतम समाधान के साथ शुरू करते हैं और समाधान को बार-बार सुधारा जाता है जब तक कि किसी स्थिति को अधिकतम नहीं किया जाता है।

उप-इष्टतम समाधान के साथ शुरू करने के विचार की तुलना पहाड़ी के आधार से शुरू करने से की जाती है, समाधान में सुधार करने की तुलना पहाड़ी पर चलने से की जाती है, और अंत में कुछ स्थिति को अधिकतम करने की तुलना पहाड़ी के शीर्ष पर पहुंचने से की जाती है।

इसलिए, पहाड़ी चढ़ाई की तकनीक को निम्नलिखित चरणों के रूप में माना जा सकता है -

• एक उप-इष्टतम समाधान का निर्माण समस्या की बाधाओं का पालन करना
• चरण-दर-चरण समाधान में सुधार
• समाधान में सुधार जब तक कोई और सुधार संभव नहीं है

पहाड़ी चढ़ाई तकनीक का उपयोग मुख्य रूप से कम्प्यूटेशनल रूप से कठिन समस्याओं को हल करने के लिए किया जाता है। यह केवल वर्तमान स्थिति और तत्काल भविष्य की स्थिति को देखता है। इसलिए, यह तकनीक मेमोरी कुशल है क्योंकि यह खोज ट्री को बनाए नहीं रखती है।

Algorithm: Hill Climbing 
Evaluate the initial state. 
Loop until a solution is found or there are no new operators left to be applied: 
   - Select and apply a new operator 
   - Evaluate the new state: 
      goal -→ quit 
      better than current state -→ new current state

Iterative सुधार

पुनरावृत्ति सुधार विधि में, प्रत्येक पुनरावृत्ति में एक इष्टतम समाधान की दिशा में प्रगति करके इष्टतम समाधान प्राप्त किया जाता है। हालांकि, इस तकनीक से स्थानीय मैक्सिमा का सामना किया जा सकता है। इस स्थिति में, बेहतर समाधान के लिए पास की स्थिति नहीं है।

विभिन्न तरीकों से इस समस्या से बचा जा सकता है। इन तरीकों में से एक नकली एनालिंग है।

रैंडम रिस्टार्ट

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

पहाड़ी चढ़ाई तकनीक की समस्याएं

स्थानीय मैक्सिमा

यदि हेविस्टिक उत्तल नहीं है, तो ग्लोबल मैक्सिमा के बजाय हिल क्लाइम्बिंग स्थानीय मैक्सिमा में परिवर्तित हो सकती है।

पुलों और Alleys

यदि लक्ष्य फ़ंक्शन एक संकीर्ण रिज बनाता है, तो पर्वतारोही केवल रिज पर चढ़ सकता है या ज़िग-ज़ैगिंग द्वारा गली से उतर सकता है। इस परिदृश्य में, पर्वतारोही को लक्ष्य तक पहुँचने के लिए और अधिक छोटे कदम उठाने की आवश्यकता होती है।

पठार

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

पहाड़ी चढ़ाई तकनीक की जटिलता

यह तकनीक अंतरिक्ष से संबंधित मुद्दों से ग्रस्त नहीं है, क्योंकि यह केवल वर्तमान स्थिति में दिखता है। पहले खोजे गए पथ संग्रहीत नहीं हैं।

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

हिल क्लाइम्बिंग तकनीक के अनुप्रयोग

हिल क्लाइम्बिंग तकनीक का उपयोग कई समस्याओं को हल करने के लिए किया जा सकता है, जहां वर्तमान स्थिति नेटवर्क-प्रवाह, ट्रैवलिंग सेल्समैन समस्या, 8-क्वींस समस्या, एकीकृत सर्किट डिजाइन, आदि जैसे सटीक मूल्यांकन फ़ंक्शन की अनुमति देती है।

हिल क्लाइम्बिंग का उपयोग आगमनात्मक शिक्षण विधियों में भी किया जाता है। इस तकनीक का उपयोग रोबोटिक्स में एक टीम में कई रोबोटों के बीच समन्वय के लिए किया जाता है। कई अन्य समस्याएं हैं जहां इस तकनीक का उपयोग किया जाता है।

उदाहरण

ट्रैवलिंग सेल्समैन की समस्या को हल करने के लिए इस तकनीक को लागू किया जा सकता है। पहले एक प्रारंभिक समाधान निर्धारित किया जाता है कि सभी शहरों में एक बार ठीक से जाना जाता है। इसलिए, यह प्रारंभिक समाधान अधिकांश मामलों में इष्टतम नहीं है। यहां तक ​​कि यह समाधान बहुत खराब हो सकता है। हिल क्लाइम्बिंग एल्गोरिथ्म इस तरह के एक प्रारंभिक समाधान के साथ शुरू होता है और पुनरावृत्त तरीके से इसमें सुधार करता है। आखिरकार, बहुत कम मार्ग प्राप्त होने की संभावना है।