निम्नलिखित पूर्णांक बैकपैक समस्या को हल करने के लिए एक एल्गोरिथ्म निम्नलिखित है। प्रस्तावित एल्गोरिथ्म को कम कम्प्यूटेशनल संसाधनों की आवश्यकता होती है और संभवतः गतिशील प्रोग्रामिंग एल्गोरिदम (डीपी) की तुलना में कुछ सरल है।

कारण ने लेखक को प्रकाशित करने के लिए प्रेरित किया

एल्गोरिथ्म के वर्णन का पहला संस्करण मेरे द्वारा गणित संस्थान को भेजा गया था। एस एल सोबोलेव, साइबेरियाई शाखा साइबेरियाई शाखा रूसी विज्ञान अकादमी, जहां से जवाब भेजा गया था कि संकेतित एल्गोरिथ्म लंबे समय से जाना जाता है। मैं बोली:

केलर की पुस्तक में उनके पहले संदर्भों में से एक है नेमहॉसर, उलमैन, असतत गतिशील प्रोग्रामिंग और पूंजी आवंटन, प्रबंधन विज्ञान, 15 पी। 494-505, 1969।

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

परिचय

एक आयामी बैकपैक समस्या (0-1 नैकपैक) एक क्लासिक असतत अनुकूलन समस्या है [1], [2]। यह कार्य और इसके वेरिएंट व्यापक रूप से व्यावहारिक समस्याओं की एक बड़ी संख्या को मॉडल करने के लिए उपयोग किए जाते हैं। सामान्य शब्दों में, समस्या को निम्नानुसार तैयार किया जा सकता है: "लागत" और "वजन" गुणों के साथ वस्तुओं के दिए गए सेट से, कुल वजन पर सीमा को देखते हुए अधिकतम कुल लागत प्राप्त करने के लिए इस तरह से वस्तुओं की एक निश्चित संख्या का चयन करना आवश्यक है।

अधिक सटीक रूप से, P (i) > 0 और W (i) > 0 क्रमशः i- th आइटम की लागत और वजन होना चाहिए, जहां I = 1,2,3, ..., N और N आइटमों की संख्या है।

यह आयाम एन के एक बूलियन वेक्टर एक्स को खोजने के लिए आवश्यक है, जहां

X (i) = 1 यदि संख्या जिसके साथ आइटम मैं बैग में रखा गया है;

X (i) = 0 यदि संख्या के साथ आइटम को बैकपैक में नहीं रखा गया है;

ताकि that P (i) X (i) का योग अधिकतम हो

और असमानता (W (i) X (i), C धारण करती है , जहाँ C > 0 बैकपैक की क्षमता है।

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

सटीक एल्गोरिदम में शामिल हैं:

• संपूर्ण खोज
• शाखा और बाध्य विधि
• गतिशील प्रोग्रामिंग (DP)

।

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

बैकपैक समस्या को हल करने के लिए एल्गोरिथ्म के एक प्रकार पर विचार करें, बशर्ते कि आइटम वजन प्राकृतिक संख्याएं हैं और आइटम मूल्य वास्तविक संख्याएं हैं।

छद्म कोड तत्वों के साथ बैकपैक समस्या को हल करने के लिए एल्गोरिथ्म का विवरण

INPUT : // इनपुट

स्रोत डेटा (ID) के एरर्स में पूर्णांक भार W और वास्तविक मान P के ऑब्जेक्ट्स W (1 ... N) > 0 और P (1 ... N) > 0 होते हैं।

जहां N आइटमों की संख्या है और C > 0 बैकपैक की क्षमता है।

OUTPUT: // आउटपुट

एक बूलियन सरणी X (1 ... N) , जहां X (i) = 1 यदि संख्या I के साथ आइटम समाधान में है, और X (i) = 0 यदि संख्या I के साथ आइटम समाधान में नहीं है।



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



स्टेज 1 // सॉर्ट आईडी

वस्तुओं की इकाई लागत कम करने के क्रम में हम आईडी को क्रमबद्ध करते हैं:

P (1) / W (1)> = P (2) / W (2)> = ... = = P (i) / W (i)> = ... = = P (N) / W (N)

जहां P (i) > 0 आइटम का मूल्य i , W (i) > 0 आइटम का वजन i ।

सरणी X (1 ... N) में, सभी तत्व प्रारंभ में = 0 हैं।

एल्गोरिथ्म के लिए स्मृति की आवश्यकता को कम करने के लिए, हम आईडी W_min = min (W) के सेट में न्यूनतम वजन निर्धारित करते हैं



चरण 2 // कामकाजी सरणियों का प्रारंभ

हम वास्तविक संख्या एलपी आयाम की एक सरणी बनाते हैं (W_min ... )

और पूर्णांक LC सरणी का एक आयाम (W_min ... C) । हम सरणी एलपी में डालते हैं और आईडी की सॉर्ट की गई सूची से पहले तत्व का डेटा एलसीआर करते हैं

LP( W(1) ) = P(1) LCr( W(1) ) = 1
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

जहां P (1) लागत है और W (1) ID की क्रमबद्ध सूची में पहले आइटम का वजन है।



चरण 3 // कार्यशील सरणियों को भरना

  FOR i = 2 TO N //     
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

W (i) और P (i) वर्तमान आईडी तत्व का वजन और लागत है।

हम वास्तविक संख्याओं का एक खाली सरणी बनाते हैं आयाम का क्लोन (W_min ... C) ।

क्लोन आईडी में वर्तमान आईडी तत्व की लागत जोड़ें

 Clone( W(i) ) = P(i)
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

।

एलपी सरणी से क्लोन सरणी में गैर-शून्य डेटा कॉपी करें , वर्तमान तत्व के मूल्य पी (i) को जोड़कर और इसके भार डब्ल्यू (i) द्वारा अपने सूचकांक को बढ़ाते हुए, बशर्ते कि क्लोन में सूचकांक बैकपैक सी की क्षमता से अधिक न हो ।

 FOR j = W_min TO ( C - W(i) ) IF LP(j) >0 THEN Clone( j + W(i) ) = LP(j) + P(i) END IF NEXT //   
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

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

  FOR j = W_min TO C IF Clone( j ) >0 AND Clone( j ) > LP( j ) THEN LP( j ) = Clone( j ) LCr( j ) = i END IF NEXT //    LP, LCr NEXT //     
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

चरण 4 // परिणाम का गठन, रिवर्स डीसेंट

LP सरणी में, हम Pmax = MAX (LP) की लागत का अधिकतम मूल्य पाते हैं, यह इष्टतम समाधान की लागत है। सरणी में पाए जाने वाले तत्व का सूचकांक समाधान के भार के बराबर है, हम इसे Wr , अर्थात द्वारा दर्शाते हैं। एलपी (Wr) = Pmax । एक्स में पाया गया पहला तत्व जोड़ें:

  X( LCr( Wr ) ) = 1
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

आगे

 //    UNTIL Wr > 0 //  Wr = 0,   //          Wr = Wr - W( LCr( Wr ) ) // ,        X IF X(LCr( Wr ) = 0 then //   X( LCr( Wr ) ) = 1 //  ELSE // 
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

हम UNTIL चक्र से बाहर निकलते हैं और चरण 2 , 3 , 4 को दोहराते हैं (केवल चरण 2 पर हम एलपी, एलसीआर सरणियों का निर्माण नहीं करते हैं, लेकिन उन्हें शून्य से भरते हैं)। चरण 1 को दोहराएं (आईडी छांटना आवश्यक नहीं है)। यह अनिवार्य रूप से एक पुनरावृत्ति है, लेकिन आईडी की प्रारंभिक छंटाई के कारण, यह गहरा नहीं होगा। कुछ सेट पर, एक पुनरावर्ती आईडी बिल्कुल नहीं हो सकता है। गणनाओं को दोहराते समय, हम केवल उन आईडी पर विचार करते हैं जिनका सूचकांक LCr (Wr) से कम है और प्राप्त वजन Wr के लिए आवश्यक बैकपैक आकार को कम करता है।

  N_NEW = LCr( Wr ) -1 C_NEW = Wr GOTO  2 END IF NEXT //    
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

अंतिम // एल्गोरिथ्म का अंत

पाए गए घोल की लागत Σ P (i) X (i) है , वजन the W (i) X (i) है ।

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

सारांश टिप्पणी

1. प्रस्तुत एल्गोरिथ्म की समग्र जटिलता में आईडी छांटने की जटिलता और एल्गोरिथम के चरण 3 के प्रदर्शन की जटिलता (खाते की संख्या को ध्यान में रखना) शामिल हैं। स्टेज 3 का रनिंग टाइम प्रति बैकपैक क्षमता ( N * C ) की संख्या के अनुपात में है। अग्रिम में पुनरावृत्तियों की संख्या निर्धारित करना काफी मुश्किल है। पुनरावृत्तियों की संख्या समाधान i X (i) में 0 से वस्तुओं की संख्या में भिन्न हो सकती है। चरण 4 में होने वाले प्रत्येक पुनरावृत्ति पर , चरण 2, 3 में गणना की मात्रा घट जाती है। संपूर्ण एल्गोरिथ्म के समय की जटिलता का ऊपरी अनुमान एन * सी * से अधिक नहीं है (पुनरावृत्तियों की संख्या + 1)
2. मेमोरी में एल्गोरिथ्म की आवश्यकता बैकपैक सी की क्षमता के आनुपातिक है और इनपुट डेटा सेट एन में वस्तुओं की संख्या पर निर्भर नहीं करता है, जो इसे डीपी विधि से अलग करता है।
3. चरण 3 के आंतरिक चक्र आसानी से समानांतर में निष्पादित होते हैं।
4. मदों की इकाई लागत में बड़े प्रसार के साथ, अगर एलपी सरणी के शीर्ष पर एल्गोरिथ्म के चरण 3 में परिवर्तन हो रहा है, तो आप चरण 3 को बाधित कर सकते हैं और कम इकाई लागत वाली शेष वस्तुओं पर विचार नहीं कर सकते हैं।
5. यदि बैकपैक C की क्षमता काफी बड़ी है, ताकि आयाम C के सरणियों को तकनीकी कारणों से नहीं बनाया जा सके या वस्तुओं का भार वास्तविक संख्याएं हैं, तो प्रस्तावित एल्गोरिदम को लिंक किए गए सूचियों के साथ सरणियों को प्रतिस्थापित करके आसानी से संशोधित किया जा सकता है।
6. यह एल्गोरिथ्म बहुपद है या नहीं, मैं अनुमान नहीं लगाता।

साहित्य

1. पापादिमित्रिउ एच।, स्टिग्लिट्ज़ के। कॉम्बिनेटरियल ऑप्टिमाइज़ेशन: अल्गोरिथम एंड कॉम्प्लेक्सिटी। एम ।: मीर, 1985।
2. टी। कॉर्मेन, सी। लिसेरसन, आर। रिवेस्ट, सी। स्टीन। एल्गोरिदम: निर्माण और विश्लेषण। एम।: पब्लिशिंग हाउस "विलियम्स", 2005।