कवर प्वाइंट मैं हाल ही में एक परीक्षण पर इस समस्या थी: अंक का एक सेट मीटर (x- अक्ष पर सभी) और अंतिम बिंदु [एल, आर] (के साथ एक सेट n लाइनों की फिर से दिया एक्स-अक्ष पर), n का न्यूनतम सबसेट खोजें, जैसे कि सभी बिंदु एक रेखा से ढके हुए हैं। साबित करें कि आपका समाधान हमेशा न्यूनतम सबसेट पाता है।समस्या
एल्गोरिथ्म मैं इसके लिए लिखा था के प्रभाव के लिए कुछ था: (माना लाइनों स्थिति 0 में बाईं endpoint के साथ सरणियों और स्थिति 1 में अधिकार के रूप में जमा हो जाती है)
algorithm coverPoints(set[] m, set[][] n):
chosenLines = []
while m is not empty:
minX = min(m)
bestLine = n[0]
for i=1 to length of n:
if n[i][0] <= minX and n[i][1] > bestLine[1] then
bestLine = n[i]
add bestLine to chosenLines
for i=0 to length of m:
if m[i] <= bestLine[1] then delete m[i] from m
return chosenLines
मैं बस हूँ सुनिश्चित नहीं है कि यह हमेशा न्यूनतम समाधान पाता है। यह एक साधारण लालची एल्गोरिदम है इसलिए मेरा आंत मुझे बताता है कि यह नहीं होगा, लेकिन मेरे दोस्तों में से एक जो मुझ से बहुत बेहतर है, कहता है कि इस समस्या के लिए इस तरह एक लालची एल्गोरिदम हमेशा न्यूनतम समाधान पाता है। साबित करने के लिए मेरा हमेशा कम से कम समाधान मिलता है, मैंने विरोधाभास से बहुत ही भारी प्रमाण प्रस्तुत किया जहां मैंने एक धारणा की कि शायद यह सच नहीं है। मैं ठीक से भूल गया मैंने क्या किया।
यदि यह न्यूनतम समाधान नहीं है, तो क्या यह ओ (एन!) समय जैसी चीज़ों से कम करने का कोई तरीका है?
धन्यवाद
मुझे आपके छद्म कोड के बाद परेशानी हो रही है। 'N [i] [0] <= m' का अर्थ यह होना चाहिए कि' n [i] [0] 'x अक्ष पर एक बिंदु है और 'm' एक सेट है? क्या आप थोड़ा सा स्पष्टीकरण दे सकते हैं और शायद स्वाभाविक रूप से समझा सकते हैं कि आपका विचार क्या है? सेट द्वारा आप एक क्रमबद्ध संग्रह या किसी संग्रह का मतलब है? आप किस मानदंड पर 'एन' ऑर्डर करते हैं? – IVlad
इसके बारे में क्षमा करें, मेरा मतलब <= minX था। संपादित। मुझे शायद इनपुट के लिए सेट के बजाय शब्द सरणी का उपयोग करना चाहिए था। यह आदेश दिया जाता है कि तत्वों को अनुक्रमिक रूप से एक्सेस किया जा सकता है, लेकिन इस अर्थ में नहीं कि अंक आरोही या अवरोही क्रम में हैं। सभी इनपुट यादृच्छिक रूप से आदेश दिए गए हैं, मैंने माना। मेरे एल्गोरिदम का सारांश था: बाएं से काम करना, सबसे लंबे समय तक की रेखा को ढूंढें जो पहले अनदेखा बिंदु को कवर करता है और इसे संग्रह में जोड़ता है। प्रत्येक बिंदु कवर होने तक दोहराएं। – Sean
अंक '1, 100, 101, 102, 103, 104' और रेखाएं' [1, 100] [10, 101] [20, 102] [30, 103] [40, 104] [101, 104] पर विचार करें ] '। यदि मैं आपके एल्गोरिदम को सही ढंग से समझता हूं, तो यह अंतिम दो बिंदुओं को कवर करने के लिए '[1, 100]' '[10, 101]' को चुनने के लिए '[1, 100]' '[10, 101] 'को चुनने के लिए, [40, 104]' तक पहुंच जाएगा। । हम '[1, 100]' और '[101, 104]' या '[1, 100]' और '[40, 104] 'चुनकर बहुत बेहतर कर सकते हैं। अगर मैं आपके एल्गोरिदम को सही ढंग से समझ गया, तो यह सभी मामलों पर काम नहीं करेगा। – IVlad