उत्पाद असेंबली/डिस्सेप्टर्स को अनुकूलित करना

Question

मेरे पास एक स्टोर है जिसमें आइटम हैं। प्रत्येक आइटम या तो एक घटक (जो परमाणु है) या एक उत्पाद जिसमें विभिन्न घटकों (लेकिन एक ही घटक के 2 या अधिक नहीं) होते हैं।

• दुकान उत्पाद की आवश्यक संख्या में शामिल हैं:

  अब, जब मैं दुकान के बाहर एक उत्पाद प्राप्त करना चाहते हैं, वहाँ विभिन्न परिदृश्यों हैं।

• स्टोर में ऐसे घटक होते हैं जिनमें से मैं उत्पाद को इकट्ठा कर सकता हूं।
• स्टोर में ऐसे उत्पाद हैं जो आवश्यक उत्पाद के साथ घटक साझा करते हैं। मैं उनको अलग कर सकता हूं और आवश्यक वस्तु को इकट्ठा कर सकता हूं।
• उपर्युक्त का कोई भी संयोजन।

नीचे आप मेरा कोड अब तक देख सकते हैं (getAssemblyPath)। यदि आवश्यक हो तो आवश्यक वस्तु को इकट्ठा करने का एक तरीका मिलता है, लेकिन यह असेंबली पथ को अनुकूलित नहीं करता है।

मैं दो तरह से पथ अनुकूलित करना चाहते हैं:

• पहले, पथ जो विधानसभा/disassembly कार्रवाई की कम से कम संख्या लेता चुनें।
• दूसरा, यदि ऐसे कई पथ हैं, तो उस पथ का चयन करें जो स्टोर में कम से कम अलग-अलग घटकों को छोड़ देता है।

अब, मैं इस अनुकूलन को कैसे प्राप्त कर सकता हूं इस बारे में पूरी तरह से नुकसान हुआ हूं (मुझे यह भी यकीन नहीं है कि यह एसओ या गणित के लिए एक प्रश्न है)।

मैं getAssemblyPath कैसे बदल सकता हूं ताकि यह मेरी अनुकूलन आवश्यकताओं को पूरा कर सके?

मेरे कोड अब तक:

#! /usr/bin/python 

class Component: 
    def __init__ (self, name): self.__name = name 

    def __repr__ (self): return 'Component {}'.format (self.__name) 

class Product: 
    def __init__ (self, name, components): 
     self.__name = name 
     self.__components = components 

    @property 
    def components (self): return self.__components 

    def __repr__ (self): return 'Product {}'.format (self.__name) 

class Store: 
    def __init__ (self): self.__items = {} 

    def __iadd__ (self, item): 
     item, count = item 
     if not item in self.__items: self.__items [item] = 0 
     self.__items [item] += count 
     return self 

    @property 
    def items (self): return (item for item in self.__items.items()) 

    @property 
    def products (self): return ((item, count) for item, count in self.__items.items() if isinstance (item, Product)) 

    @property 
    def components (self): return ((item, count) for item, count in self.__items.items() if isinstance (item, Component)) 

    def getAssemblyPath (self, product, count): 
     if product in self.__items: 
      take = min (count, self.__items [product]) 
      print ('Take {} of {}'.format (take, product)) 
      count -= take 
      if not count: return 
     components = dict ((comp, count) for comp in product.components) 
     for comp, count in self.components: 
      if comp not in components: continue 
      take = min (count, components [comp]) 
      print ('Take {} of {}'.format (take, comp)) 
      components [comp] -= take 
      if not components [comp]: del components [comp] 
      if not components: return 
     for prod, count in self.products: 
      if prod == product: continue 
      shared = set (prod.components) & set (components.keys()) 
      dis = min (max (components [comp] for comp in shared), count) 
      print ('Disassemble {} of {}.'.format (dis, prod)) 
      for comp in shared: 
       print ('Take {} of {}.'.format (dis, comp)) 
       components [comp] -= take 
       if not components [comp]: del components [comp] 
       if not components: return 
     print ('Missing components:') 
     for comp, count in components.items(): 
      print ('{} of {}.'.format (count, comp)) 

c1 = Component ('alpha') 
c2 = Component ('bravo') 
c3 = Component ('charlie') 
c4 = Component ('delta') 

p1 = Product ('A', [c1, c2]) 
p2 = Product ('B', [c1, c2, c3]) 
p3 = Product ('C', [c1, c3, c4]) 

store = Store() 
store += (c2, 100) 
store += (c4, 100) 
store += (p1, 100) 
store += (p2, 100) 
store += (p3, 10) 
store.getAssemblyPath (p3, 20) 

यह आउटपुट:

Take 10 of Product C 
Take 10 of Component delta 
Disassemble 10 of Product A. 
Take 10 of Component alpha. 
Disassemble 10 of Product B. 
Take 10 of Component charlie. 

कौन सा काम करता है, लेकिन यह अनावश्यक रूप से जुदा उत्पाद एक करता है, उत्पाद बी आवश्यक घटक अल्फा और चार्ली के दोनों शामिल है के रूप में ।

-

संपादित करें:

Blckknght की बहुत समझदार प्रश्नों का उत्तर देना:

जब आप कहते हैं कि आप चाहते हैं "विधानसभा/disassembly कार्रवाई की कम से कम संख्या", आप क्या मतलब है वस्तुओं की सबसे छोटी संख्या, या विभिन्न उत्पादों की सबसे छोटी संख्या?

एक "asm/disasm action" एक उत्पाद को इकट्ठा करने या अलग करने की क्रिया है, भले ही कितने घटक शामिल हों। मैं कम से कम छूटे हुए सामानों की तलाश में हूं, इससे कोई फर्क नहीं पड़ता कि वे अलग हैं या नहीं।

क्या उत्पाद ए के 10 को अलग करने और उत्पाद बी के अतिरिक्त 5 को अलग करने के लिए उत्पाद ए के 20 को अलग करना बेहतर है?

उत्तरार्द्ध इष्टतम के करीब है।

आगे, आप कहते हैं कि आप पीछे कई घटकों को छोड़ने से बचना चाहते हैं, लेकिन आपके वर्तमान कोड में सभी अलग-अलग घटक जो अनुरोधित उत्पाद द्वारा उपयोग नहीं किए जाते हैं, खो जाते हैं। क्या वह जानबूझकर है (यानी, क्या आप अन्य घटकों को फेंकना चाहते हैं), या यह एक बग है?

विधि getAssemblyPath केवल आइटम को प्राप्त करने का तरीका निर्धारित करता है। यह वास्तविक स्टोर को छूता नहीं है। किसी भी पल में यह self.__items को असाइन करता है। इसे एक ऐसे कार्य के रूप में सोचें जो दुकान के आदेश को जारी करता है, उसे अपने स्टोर से आवश्यक वस्तु की आवश्यक मात्रा प्राप्त करने के लिए, (मध्यवर्ती) भविष्य में उसे क्या करना चाहिए।

-

संपादित करें 2:

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

उत्पाद ए घटक α, β, γ, δ, ε और ζ शामिल हैं।

उत्पाद बी घटक α, β, η, δ, ε और θ शामिल हैं।

उत्पाद सी घटक α, β, γ, ι, κ और λ शामिल हैं।

उत्पाद डी घटक μ, ν, ξ, δ, ε और ζ शामिल हैं।

हम ए, बी के 100, सी के 100 और डी के 100 की दुकान 0 में है हम अब ए के 10 की आवश्यकता होती है, तो हम उत्पादों एक साथ सबसे अधिक घटकों प्रयोग करती है, के लिए पहले देखो, हम बी मिलेगा हम 10 में से प्रत्येक को α, β, δ और ε प्राप्त करने के 10 को अलग करते हैं। लेकिन फिर हमें 10 सी (γ पाने के लिए) और डी के 10 (ζ प्राप्त करने के लिए) को अलग करने की आवश्यकता है। ये 40 कार्य होंगे (30 अलग-अलग और 10 संयोजन)। लेकिन इष्टतम तरीका डी के 10 और डी के 10 (30 क्रियाएं, 20 अलग-अलग और 10 संयोजन) को अलग करना होगा।

-

संपादित करें 3:

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

Answer 1

मुझे लगता है कि यहां की कुंजी प्रत्येक खरीद मामले की संभावित लागत स्थापित करना है, ताकि खरीद मामलों का उचित संयोजन लागत लागत को कम से कम कम कर सके। (फिर इसके लिए बस एक नेप्सेक समस्या को कम किया)

क्या इस प्रकार शायद इष्टतम नहीं है लेकिन यहाँ मैं क्या मतलब का एक उदाहरण है:

1. किसी भी उत्पाद है कि अंत उत्पाद "लागत" यह वास्तविक लागत (है मुद्रा में)।

2. किसी भी घटक या उत्पाद को अंतिम उत्पाद (अन्य अलग-अलग उत्पादों/घटकों को दिए गए) में इकट्ठा किया जा सकता है लेकिन इसे वास्तविक मूल्य (मुद्रा में) और एक छोटा कर (टीबीडी) खर्च करने की आवश्यकता नहीं होती है।

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

नोट: ये "कर" सभी उप-उत्पादों पर लागू होंगे जो एक ही मामले पर कब्जा करते हैं।

... और इतने पर अन्य संभावित मामलों

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

नोट: हर बार जब आप एक अंतिम उत्पाद "इकट्ठा" करते हैं तो आपको वर्तमान "असेंबली सूची" में प्रत्येक उत्पाद के लिए वैश्विक काउंटर को कम करने की आवश्यकता होगी।

आशा है कि यह सही दिशा में चल रही चर्चा हो। सौभाग्य!

Answer 2

यहां इस समस्या को हल करने का तरीका बताया गया है। मैं इसके लिए कोड लिखना चाहता था लेकिन मुझे नहीं लगता कि मेरे पास समय है।

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

यहां आपके उदाहरण के आधार पर एक विशिष्ट उदाहरण है। हमें उत्पाद 3 (पी 3) के लिए ऑर्डर भरने की जरूरत है जो घटकों सी 1, सी 3 और सी 4 से बना है। हमारा ऑर्डर पी 3 के 20 के लिए है, और हमारे पास स्टॉक में 10 पी 3 है इसलिए हम पी 3 के पहले 10 के लिए ऑर्डर को तीन बार भर देते हैं। अब हमारा ऑर्डर पी 3 में से 10 के लिए है, लेकिन हम इसे सी 1 के 10, सी 3 के 10 और सी 4 के 10 के लिए ऑर्डर के रूप में देख सकते हैं। पहले रिकर्सिव कॉल के लिए हम एक पी 1 को अलग करते हैं, और एक सी 1 के लिए ऑर्डर भरते हैं और स्टोर में अतिरिक्त सी 2 डालते हैं; इसलिए यह रिकर्सिव कॉल स्टोर में अपडेट की गई उपलब्धता के साथ 9 सी 1, सी 3 में से 10 और सी 4 के 10 के लिए है। दूसरे रिकर्सिव कॉल के लिए हम एक पी 2 को अलग करते हैं, और सी 1 और सी 4 के लिए ऑर्डर भरते हैं, और स्टोर में अतिरिक्त सी 2 डालते हैं; इसलिए यह रिकर्सिव कॉल स्टोर में अपडेट की गई उपलब्धता के साथ 9 सी 1, सी 3 के 10 और सी 4 के 9 के लिए है।

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

मुझे यकीन नहीं है, लेकिन आप कॉल को याद करके इसे गति देने में सक्षम हो सकते हैं। पाइथन ने 3.x श्रृंखला, functools.lru_cache() में वास्तव में निफ्टी बनाया है; चूंकि आपने अपना प्रश्न "पायथन 3.2" के रूप में टैग किया है, यह आपके लिए उपलब्ध है।

What is memoization and how can I use it in Python?

Memoization मान्यता है कि समारोह में पहले से ही एक ही तर्क के साथ बुलाया गया है, और बस के रूप में पहले की तरह ही समाधान वापस लौट कर काम करता है। तो यह जवाब के लिए एक कैश मैपिंग तर्क है। यदि तर्कों में गैर-आवश्यक डेटा शामिल है (जैसे स्टोर में से कितने घटक सी 2 हैं) तो ज्ञापन काम करने की संभावना कम है। लेकिन अगर हम कल्पना करते हैं कि हमारे पास उत्पाद पी 1 और पी 9 हैं, और पी 9 में घटक सी 1 और सी 9 शामिल हैं, तो हमारे उद्देश्यों के लिए पी 1 या पी 9 में से एक को बराबर होना चाहिए: उनके पास समान डिस्सेप्लर लागत है, और वे दोनों एक घटक उत्पन्न करते हैं जिसे हमें चाहिए (सी 1) और एक जिसे हमें जरूरत नहीं है (सी 2 या सी 9)। इसलिए यदि हमें रिकर्सिव कॉल तर्क सही मिलते हैं, तो जब हम पी 9 की कोशिश करने के लिए घूमते हैं तो ज्ञापन केवल तत्काल उत्तर लौटा सकता है, और यह बहुत समय बचा सकता है।

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

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

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

मैं अभी समय से बाहर हूं और थोड़ी देर के लिए इस पर काम नहीं करूँगा, क्षमा करें।

#!/usr/bin/python3 

class Component: 
    def __init__ (self, name): self.__name = name 

    #def __repr__ (self): return 'Component {}'.format (self.__name) 
    def __repr__ (self): return 'C_{}'.format (self.__name) 

class Product: 
    def __init__ (self, name, components): 
     self.__name = name 
     self.__components = components 

    @property 
    def components (self): return self.__components 

    #def __repr__ (self): return 'Product {}'.format (self.__name) 
    def __repr__ (self): return 'P_{}'.format (self.__name) 

class Store: 
    def __init__ (self): self.__items = {} 

    def __iadd__ (self, item): 
     item, count = item 
     if not item in self.__items: self.__items [item] = 0 
     self.__items [item] += count 
     return self 

    @property 
    def items (self): return (item for item in self.__items.items()) 

    @property 
    def products (self): return ((item, count) for item, count in self.__items.items() if isinstance (item, Product)) 

    @property 
    def components (self): return ((item, count) for item, count in self.__items.items() if isinstance (item, Component)) 

    def get_assembly_path (self, product, count): 
     store = self.__items.copy() 
     if product in store: 
      take = min (count, store [product]) 
      s_trivial = ('Take {} of {}'.format (take, product)) 
      count -= take 
      if not count: 
       print(s_trivial) 
       return 
      dict_decr(store, product, take) 
      product not in store 

     order = {item:count for item in product.components} 
     cost, solution = solver(order, store) 
     if cost is None: 
      print("No solution.") 
      return 

     print("Solution:") 
     print(s_trivial) 
     for item, count in solution.items(): 
      if isinstance(item, Component): 
       print ('Take {} of {}'.format (count, item)) 
      else: 
       assert isinstance(item, Product) 
       print ('Disassemble {} of {}'.format (count, item)) 

    def getAssemblyPath (self, product, count): 
     if product in self.__items: 
      take = min (count, self.__items [product]) 
      print ('Take {} of {}'.format (take, product)) 
      count -= take 
      if not count: return 
     components = dict ((comp, count) for comp in product.components) 
     for comp, count in self.components: 
      if comp not in components: continue 
      take = min (count, components [comp]) 
      print ('Take {} of {}'.format (take, comp)) 
      components [comp] -= take 
      if not components [comp]: del components [comp] 
      if not components: return 
     for prod, count in self.products: 
      if prod == product: continue 
      shared = set (prod.components) & set (components.keys()) 
      dis = min (max (components [comp] for comp in shared), count) 
      print ('Disassemble {} of {}.'.format (dis, prod)) 
      for comp in shared: 
       print ('Take {} of {}.'.format (dis, comp)) 
       components [comp] -= take 
       if not components [comp]: del components [comp] 
       if not components: return 
     print ('Missing components:') 
     for comp, count in components.items(): 
      print ('{} of {}.'.format (count, comp)) 

def str_d(d): 
    lst = list(d.items()) 
    lst.sort(key=str) 
    return "{" + ", ".join("{}:{}".format(k, v) for (k, v) in lst) + "}" 

def dict_incr(d, key, n): 
    if key not in d: 
     d[key] = n 
    else: 
     d[key] += n 

def dict_decr(d, key, n): 
    assert d[key] >= n 
    d[key] -= n 
    if d[key] == 0: 
     del(d[key]) 

def solver(order, store): 
    """ 
    order is a dict mapping component:count 
    store is a dict mapping item:count 

    returns a tuple: (cost, solution) 
     cost is a cost metric estimating the expense of the solution 
     solution is a dict that maps item:count (how to fill the order) 

    """ 
    print("DEBUG: solver: {} {}".format(str_d(order), str_d(store))) 
    if not order: 
     solution = {} 
     cost = 0 
     return (cost, solution) 

    solutions = [] 
    for item in store: 
     if not isinstance(item, Component): 
      continue 
     print("...considering: {}".format(item)) 
     if not item in order: 
      continue 
     else: 
      o = order.copy() 
      s = store.copy() 
      dict_decr(o, item, 1) 
      dict_decr(s, item, 1) 
      if not o: 
       # we have found a solution! Return it 
       solution = {} 
       solution[item] = 1 
       cost = 1 
       print("BASIS: solver: {} {}/{} {}".format(str_d(order), str_d(store), cost, str_d(solution))) 
       return (cost, solution) 
      else: 
       cost, solution = solver(o, s) 
       if cost is None: 
        continue # this was a dead end 
       dict_incr(solution, item, 1) 
       cost += 1 
       solutions.append((cost, solution)) 

    for item in store: 
     if not isinstance(item, Product): 
      continue 
     print("...Product components: {} {}".format(item, item.components)) 
     assert isinstance(item, Product) 
     if any(c in order for c in item.components): 
      print("...disassembling: {}".format(item)) 
      o = order.copy() 
      s = store.copy() 
      dict_decr(s, item, 1) 
      for c in item.components: 
       dict_incr(s, c, 1) 
      cost, solution = solver(o, s) 
      if cost is None: 
       continue # this was a dead end 
      cost += 1 # cost of disassembly 
      solutions.append((cost, solution)) 
     else: 
      print("DEBUG: ignoring {}".format(item)) 

    if not solutions: 
     print("DEBUG: *dead end*") 
     return (None, None) 
    print("DEBUG: finding min of: {}".format(solutions)) 
    return min(solutions) 



c1 = Component ('alpha') 
c2 = Component ('bravo') 
c3 = Component ('charlie') 
c4 = Component ('delta') 

p1 = Product ('A', [c1, c2]) 
p2 = Product ('B', [c1, c2, c3]) 
p3 = Product ('C', [c1, c3, c4]) 

store = Store() 
store += (c2, 100) 
store += (c4, 100) 
store += (p1, 100) 
store += (p2, 100) 
store += (p3, 10) 
#store.getAssemblyPath (p3, 20) 
store.get_assembly_path(p3, 20) 

Answer 3

1. एन उत्पादों < => एकल उत्पाद के लिए इष्टतम पथ के लिए इष्टतम पथ।

वास्तव में, अगर हम बेहतर उत्पाद एक्स के एन इकट्ठा करने के लिए, हम बेहतर (मौजूदा स्टॉक का उपयोग) के बाद एक उत्पाद को इकट्ठा की जरूरत है, सवाल बेहतर (एन -1) उत्पाद एक्स के शेष स्टॉक का उपयोग कर इकट्ठा करने के लिए हो जाता है।

=> इसलिए, यह एक समय में एक उत्पाद एक्स को बेहतर रूप से एकजुट करने के एल्गोरिदम प्रदान करने के लिए पर्याप्त है।

1. मान लें हम घटकों x1, .. उत्पाद के लिए XN जरूरत

प्रत्येक घटक xk के लिए, सभी उत्पादों इस घटक है कि लगता है (यहाँ हम केवल स्टॉक में घटक के रूप में उपलब्ध नहीं घटक शामिल हैं)। हम प्रत्येक घटक के लिए उत्पादों की एक सूची प्राप्त करेंगे - उत्पाद ए 1 (1), .., ए 1 (i1) में घटक x1 है, उत्पाद ए (1), .., ए (i2) घटक x2 है, और आगे (कुछ उत्पादों को कई सूचियों ए 1, ए 2, .., एक सूचियों में निहित किया जा सकता है)।

यदि कोई भी सूची खाली है - कोई समाधान नहीं है।

हमें उत्पादों के न्यूनतम सेट की आवश्यकता है, जैसे कि उस सेट का एक उत्पाद प्रत्येक सूचियों में निहित है।

A1 के

• लें संघ, .., एक - इसे कहते ए (संघ में केवल अद्वितीय उत्पादों में शामिल हैं): सभी सेट कोशिश करते हैं और कम से कम लेने - सबसे सरल है, लेकिन computationally कुशल नहीं समाधान जानवर बल द्वारा होता है।

एक। एक से एकल उत्पाद ले लो, अगर यह सब A1 में निहित है, .., एक - हम केवल एक disassembly (इस उत्पाद) की जरूरत है। बी। , एक से दो उत्पादों के सभी संयोजनों का प्रयास किसी भी संयोजन (A1, A2) को संतुष्ट करता है, तो शर्त यह है कि या तो A1 या A2 सूचियों A1, .. में से प्रत्येक के, एक में निहित है - यह एक समाधान है। सूचियों A1, .., एक से प्रत्येक से एक घटक -

...

पक्का

, वहाँ गहराई n पर एक समाधान है। अगर हमें पहले कोई समाधान नहीं मिला, तो यह सबसे अच्छा समाधान है।

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

---

संपादित करें:

अधिक सटीक समाधान लंबाई से सूचियों सॉर्ट करने के लिए है। फिर जब समाधान किया जा रहा है के लिए K उत्पादों का समूह जाँच - वहाँ गहराई कश्मीर कि समस्या का हल करने का कोई कम से कम सेट है - पहले कश्मीर सूचियों से प्रत्येक सूची से 1 आइटम का केवल सभी संभव संयोजनों, जांच की जानी अगर कोई समाधान की जरूरत है। उस प्रकार की जांच भी कम्प्यूटेशनल रूप से खराब नहीं होगी - शायद यह काम कर सकती है ????