कम करने योग: अनुकूलन समस्या

Question

वास्तविक प्रश्न इस प्रकार है:

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

जोड़ों के समन्वय के एक सरणी (एन तत्व) और एक पूर्णांक 'के' को देखते हुए, गोदामों की इष्टतम स्थिति के निर्देशांक देने वाले 'के' तत्वों की एक सरणी लौटाएं।

क्षमा करें, मेरे पास कोई उदाहरण उपलब्ध नहीं है क्योंकि मैं इसे स्मृति से लिख रहा हूं। वैसे भी, एक नमूना हो सकता है:

सरणी = {1,3,4,5,7,7,8,10,11} (n = 9)
k = 1

उत्तर: {7 }

यही वह है जो मैं सोच रहा था: के = 1 के लिए, हम बस सेट के औसत को ढूंढ सकते हैं, जो गोदाम का इष्टतम स्थान प्रदान करेगा। हालांकि, के> 1 के लिए, दिए गए सेट को 'के' सबसेट्स (डिसजॉइंट, और सुपरसेट के संगत तत्वों) में विभाजित किया जाना चाहिए, और प्रत्येक सबसेट के लिए औसत वेयरहाउस स्थान देगा। हालांकि, मुझे समझ में नहीं आता कि किस आधार पर 'के' सबसेट बनना चाहिए। अग्रिम में धन्यवाद।

संपादित करें: इस समस्या में भी बदलाव है: योग/औसत के बजाय, संयुक्त और उसके निकटतम गोदाम के बीच अधिकतम दूरी को कम करें। मुझे यह भी नहीं मिला ..

Answer 1

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

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

मुझे यह गलत काम करने की लागत मिलती है, लेकिन एन जोड़ों और के गोदामों के साथ आपके पास एन कदम उठाने के लिए एन कदम हैं, प्रत्येक एनके पिछले समाधानों से अधिक पर विचार करने के आधार पर, इसलिए मुझे लगता है कि लागत है केएन^2।

Answer 2

यह एक क्लस्टरिंग समस्या नहीं है, यह एक सुविधा स्थान समस्या का एक विशेष मामला है। आप इसे एक सामान्य पूर्णांक/रैखिक प्रोग्रामिंग पैकेज का उपयोग करके हल कर सकते हैं, लेकिन क्योंकि समस्या एक पंक्ति पर है, वहां काम करने वाले अधिक कुशल (और कम महंगी सॉफ़्टवेयर-वार) एल्गोरिदम हो सकते हैं। आप गतिशील प्रोग्रामिंग पर विचार कर सकते हैं क्योंकि शायद उन सुविधाओं का संयोजन हो सकता है जिन्हें जल्दी से हटाया जा सकता है। अधिक जानकारी के लिए P-Median problem पर देखें।