मैं किसी को यह सत्यापित करने के लिए चाहूंगा कि निम्न समस्या एनपी-पूर्ण है या यदि सरल ब्रूट-फोर्स संयोजन जांच से वास्तव में बेहतर/आसान समाधान है।संभावित एनपी-पूर्ण समस्या?
हमारे पास हमारे सॉफ़्टवेयर में संसाधन आवंटन समस्या का एक प्रकार है, और मैं इसे एक उदाहरण के साथ समझाऊंगा।
मान लें कि हमें दिन-शिफ्ट के दौरान काम करने के लिए 4 लोगों की आवश्यकता है। यह संख्या, और तथ्य यह है कि यह एक "दिन-शिफ्ट" है हमारे डेटाबेस में दर्ज किया गया है।
हालांकि, हमें किसी भी व्यक्ति को उन स्थानों को भरने की आवश्यकता नहीं है, बिल को फिट करने के लिए कुछ आवश्यकताएं भरने की आवश्यकता है।
उन 4 में से, मान लें कि उनमें से 2 को नर्स होना है, और उनमें से 1 डॉक्टर होना चाहिए।
डॉक्टरों में से एक को भी एक विशेष टीम के हिस्से के रूप में काम करना पड़ता है।
डे-शिफ्ट: 4
1 डॉक्टर
1 डॉक्टर, टीम एक
1 में काम करने की जरूरततो हम जानकारी के इस सेट है नर्स
उपर्युक्त समस्या नहीं है। समस्या तब आती है जब हम दिन-शिफ्ट करने के लिए लोगों को चुनना शुरू करते हैं और यह पता लगाने की कोशिश करते हैं कि क्या हमने अभी तक उठाए गए लोगों को मानदंड भर सकते हैं।
उदाहरण के लिए, मान लें कि हम जेम्स, जॉन, उर्सुला और मैरी को काम करने के लिए चुनते हैं, जहां जेम्स और उर्सुला डॉक्टर हैं, जॉन और मैरी नर्स हैं।
उर्सुला भी
टीम ए में काम करता है अब, क्रम हम बिल को फिट करने की कोशिश पर निर्भर करता है, हम बात का अनुमान लगाना हम सही लोगों, या नहीं है, जब तक कि हम विभिन्न संयोजनों की कोशिश कर रहा शुरू खत्म हो सकता है।
उदाहरण के लिए, यदि सूची में जाएं और पहले उर्सुला चुनें, तो हम उसे "1 डॉक्टर" मानदंड से मिलान कर सकते हैं। फिर हम जेम्स जाते हैं, और हम देखते हैं कि चूंकि वह टीम ए में काम नहीं करता है, इसलिए "1 डॉक्टर," टीम ए में काम करने की ज़रूरत है "के बारे में अन्य मानदंड उसके साथ नहीं भरे जा सकते हैं। चूंकि अन्य दो लोग नर्स हैं, इसलिए वे उस मानदंड को फिट नहीं करेंगे।
तो हम बैकट्रैक और पहले जेम्स को आजमाएं, और वह भी पहले मानदंडों को फिट कर सकता है, और फिर उर्सुला उन मानदंडों को फिट कर सकता है जिन्हें उस टीम की आवश्यकता है।
तो समस्या हमें देखती है क्योंकि हमें अलग-अलग संयोजनों को आजमाने की ज़रूरत है जब तक कि हमने उन सभी को आजमाया नहीं है, इस मामले में हमारे पास कुछ मानदंड हैं जो अभी तक भरे नहीं हैं, भले ही सिर की कुल संख्या काम कर रही हो आवश्यक सिर की कुल संख्या के समान, या हमें एक संयोजन मिला है जो काम करता है।
क्या यह एकमात्र समाधान है, क्या कोई बेहतर व्यक्ति के बारे में सोच सकता है?
संपादित: कुछ स्पष्टीकरण।
इस प्रश्न के लिए टिप्पणियां उल्लेख करती हैं कि इन कुछ लोगों के साथ, हमें क्रूर बल के साथ जाना चाहिए, और मैं मानता हूं कि शायद हम क्या कर सकते हैं, और हम ऐसा भी कर सकते हैं, उसी लेन में कि कुछ प्रकार के अनुकूलन दिखते हैं डेटा के आकार पर और डेटा आकार छोटा होने पर कम प्रारंभिक ओवरहेड के साथ अलग-अलग प्रकार के एल्गोरिदम चुनता है।
समस्या यह है कि यह एक रोस्टर योजना प्रणाली का हिस्सा है, जिसमें आपके पास बहुत से लोगों को शामिल किया जा सकता है, दोनों "हमें दिन में शिफ्ट की जरूरत है" और साथ ही "हमारे पास यह है वाई लोगों का पूल जो यह कर रहा है ", साथ ही साथ बड़े पैमाने पर संभावित" हमारे पास उन एक्स लोगों के लिए जेड मानदंडों की यह सूची है जिन्हें किसी भी तरह से इन लोगों के साथ मिलना होगा ", और फिर आप इस तथ्य को जोड़ते हैं कि वास्तविक समय में, वही गणना करने के लिए हमारे पास कई दिन होंगे, क्योंकि नेता रोस्टर को समायोजित करता है, और फिर एक त्वरित समाधान की आवश्यकता आ गई है।
असल में, नेता स्क्रीन पर एक लाइव योग जानकारी देखेंगे जो कहता है कि पूरे दिन दिन में बदलाव के साथ-साथ कितने लोग विभिन्न मानदंडों को फिट कर रहे हैं, और कैसे हमारे पास वास्तव में बहुत से लोग हैं जो हमारे पास हैं। इस डिस्प्ले को सेमी-लाइव अपडेट करना होगा, जबकि नेता रोस्टर को समायोजित करेगा "क्या होगा अगर जेम्स उर्सुला के बजाय दिन-शिफ्ट लेता है, और उर्सुला रात-शिफ्ट लेता है"।
लेकिन अब तक इसका उत्तर देने वाले लोगों के लिए बहुत धन्यवाद, बाधा संतुष्टि समस्या हमें जिस तरह से जाना है, वैसे ही लगता है, लेकिन हम निश्चित रूप से यहां सभी लिंक और एल्गोरिदम नामों पर कड़ी मेहनत करेंगे।
यही कारण है कि मैं StackOverflow :) प्यार
4 और 2 जैसी संख्याओं के साथ, मुझे नहीं लगता कि क्यों * नहीं * सबसे आसान संभव ब्रूट-फोर्स खोज का उपयोग करना है। – ShreevatsaR
मैं मानता हूं कि अगर आप हमेशा छोटे होंगे तो आपको केवल बलपूर्वक बल देना चाहिए। यदि नहीं, तो आपको एक ह्युरिस्टिक का उपयोग करने की आवश्यकता है। मेरा अनुमान है कि यह Knapsack समस्या का एक बदलाव है। मुझे नहीं पता कि इस सवाल से यह जवाब क्यों हटा दिया गया था। –
मैं मानता हूं, मैं सवाल संपादित करूंगा, लेकिन मुझे लगता है कि पहले दिए गए उत्तरों से हमें इस पर एक प्रमुख शुरुआत करने का कोई तरीका मिलेगा। –