एक आकार

Question

के अंदर लाइनों को वितरित करने के लिए अनुकूलन एल्गोरिदम का विकल्प सुदृढीकरण सलाखों और छेद के साथ एक ठोस स्लैब तत्व के अनुवर्ती प्रतिनिधित्व पर विचार करें।

मैं एक एल्गोरिथ्म कि स्वचालित रूप से अलग छेद के साथ एक मनमाना आकार से अधिक लाइनों वितरित करता है की जरूरत है।

मुख्य बाधाओं हैं:

1. लाइन्स क्षेत्र के बाहर या एक छेद के अंदर नहीं किया जा सकता
2. दो पक्ष-साथ लाइनों के बीच की दूरी एक चर D
3. लाइन्स के लिए है अधिक नहीं हो सकता एक निश्चित अंतराल I, यानी y mod I = 0 पर स्थित हो, जहां y रेखा का वाई समन्वय है।
4. आकृति के अंदर प्रत्येक उपलब्ध बिंदु से D/2

मैं लाइनों एन की कुल संख्या कम करके समाधान अनुकूलित करना चाहते हैं एक लाइन से आगे नहीं हो सकता। इस समस्या के अनुरूप किस तरह का अनुकूलन एल्गोरिदम होगा?

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

मैंने पहले ही सी # में एक एल्गोरिदम लागू किया है जो नौकरी करता है, लेकिन बहुत अनुकूल नहीं है।

1. ज्यामिति
2. का एक सरलीकृत रेखापुंज बनाएं एक जटिल सूत्र उस खाते में संभव लाइन की लंबाई और अन्य छड़ और बाधाओं के लिए दूरी लेता है का उपयोग कर प्रत्येक कक्ष के लिए एक स्कोर गणना: यह यह कैसे काम करता है।
3. तय करें कि कौन सुदृढीकरण की जरूरत है (जहां y दिशा>डी में नि: शुल्क कोशिकाओं की संख्या)
4. उच्चतम स्कोर कि सुदृढीकरण की जरूरत के साथ सेल उठाओ, और जहाँ तक -x में संभव इसे मजबूत और + x दिशाओं
5. दोहराएँ

जटिल सूत्र के आधार पर यह बहुत अच्छी तरह से काम करता है लेकिन, जब पिछले कुछ लाइनों डाल अवांछित परिणाम दे रही है, क्योंकि यह एक पहले से ही डाल लाइन को स्थानांतरित नहीं कर सकते हैं शुरू होता है। क्या कोई अन्य अनुकूलन तकनीक है जिसे मुझे देखना चाहिए?

Answer 1

मुझे यकीन नहीं है कि आप जो चाहते हैं वह है - मुझे यकीन है कि यह आपके मन में नहीं था - लेकिन यदि यह उचित लगता है तो आप इसे आजमा सकते हैं।

क्योंकि दूरी सबसेd पर बस है, और उस से कम कुछ भी हो सकता है, यह पहली बार लाल पर लगता है कि एक लालची एल्गोरिथ्म यहाँ काम करना चाहिए।हमेशा अगली पंक्ति (ओं) रखें ताकि (1) जितना संभव हो उतना कम हो और (2) वे मौजूदा लाइनों से जितना संभव हो उतने दूर हैं।

मान लें कि इस समस्या के लिए आपके पास इष्टतम एल्गोरिदम है, और यह अंतिम पंक्ति से a <= d पर अगली पंक्ति (ओं) रखता है। कहें कि यह b लाइनें रखता है। हमारा लालची एल्गोरिदम निश्चित रूप से b लाइनों से अधिक नहीं रखेगा (क्योंकि पहला मानदंड जितना संभव हो उतना कम जगह है), और यदि यह b लाइनों को रखता है तो यह उन्हें ca <= c <= d के साथ दूरी पर रखेगा, क्योंकि यह तब तक लाइनों को रखता है मुमकिन।

लालची एल्गोरिथ्म क्या इष्टतम एल्गोरिथ्म किया भी नहीं किया है, तो निम्न तरीकों में से एक में मतभेद:

1. यह दूर ही या इससे कम लाइनों रखा। मान लीजिए कि इष्टतम एल्गोरिदम b' लाइनों को अगले चरण में a' पर दूरी पर चला गया था। फिर ये लाइनें a+a' पर होगी और कुल में b+b' लाइनें होंगी। लेकिन लालची एल्गोरिदम c' = (a+a') - c चुनकर विस्थापन a+a' पर b' लाइनों को रखकर इस मामले में इष्टतम एल्गोरिदम की नकल कर सकता है। चूंकि c > a और a' < d, c' < d और यह एक कानूनी प्लेसमेंट है।

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

तो लालची एल्गोरिदम 2 मामले में काम नहीं करता है। हालांकि, यह अन्य मामलों में करता है। विशेष रूप से, पहले मामले में हमारा अवलोकन बहुत उपयोगी है: किसी भी दो प्लेसमेंट (distance, lines) और (distance', lines') के लिए, distance >= distance' और lines <= lines', पहले प्लेसमेंट को हमेशा प्राथमिकता दी जानी चाहिए।

PlaceLines(start, stop) 

    // if we are close enough to the other edge, 
    // don't place any more lines. 
    if start + d >= stop then return ([], 0) 

    // see how many lines we can place at distance 
    // d from the last placed lines. no need to 
    // ever place more lines than this 
    nmax = min_lines_at_distance(start + d) 

    // see how that selection pans out by recursively 
    // seeing how line placement works after choosing 
    // nmax lines at distance d from the last lines. 
    optimal = PlaceLines(start + d, stop) 
    optimal[0] = [d] . optimal[0] 
    optimal[1] = nmax + optimal[1] 

    // we only need to try fewer lines, never more 
    for n = 1 to nmax do 

     // find the max displacement a from the last placed 
     // lines where we can place n lines. 
     a = max_distance_for_lines(start, stop, n) 

     if a is undefined then continue 

     // see how that choice pans out by placing 
     // the rest of the lines 
     candidate = PlaceLines(start + a, stop) 
     candidate[0] = [a] . candidate[0] 
     candidate[1] = n + candidate[1] 

     // replace the last best placement with the 
     // one we just tried, if it turned out to be 
     // better than the last 
     if candidate[1] < optimal[1] then 
      optimal = candidate 

    // return the best placement we found 
    return optimal 

यह एक कैश (start, stop) द्वारा अनुक्रमित में परिणाम (seq, lines) डालकर Memoization द्वारा सुधार किया जा सकता: यह निम्नलिखित कलन विधि पता चलता है। इस तरह, हम पहचान सकते हैं कि जब हम असाइनमेंट की गणना करने की कोशिश कर रहे हैं जिसका पहले से मूल्यांकन किया जा सकता है। मैं उम्मीद करता हूं कि इस मामले में बहुत कुछ होगा, भले ही आप समस्या उदाहरणों के लिए मोटे या ठीक विघटन का उपयोग करें।

मुझे इस बारे में विवरण नहीं मिलता है कि max_lines_at_distance और max_distance_for_lines फ़ंक्शन कैसे काम कर सकते हैं, लेकिन शायद इन पर एक शब्द हो सकता है।

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

दूसरा आपको बताता है कि लाइनों के दिए गए उम्मीदवार संख्या के लिए, वर्तमान स्थिति से अधिकतम दूरी जिस पर लाइनों की संख्या रखी जा सकती है। आप इसे अधिकतम दूरी बताकर इसे बेहतर बना सकते हैं जिस पर लाइनों की संख्या, या कम रखा जा सकता है।आप इस सुधार का उपयोग करते हैं, तो आप जिस दिशा में आप n और पुनरावृत्ति कर रहे हैं रिवर्स सकता है:

1. अगर f(start, stop, x) = a और y < x, आप केवल, a, नहीं stop अप करने के लिए खोज करने के लिए तब से की जरूरत है;
2. यदि f(start, stop, x) अपरिभाषित है और y < x है, तो आपको और अधिक खोजने की आवश्यकता नहीं है।

नोट यदि यह असंभव है कहीं भी start और stop के बीच n या इससे कम लाइनों जगह इस समारोह अपरिभाषित जा सकता है।

ध्यान दें कि आप बार-बार लुकअप को सहेजने के लिए इन कार्यों के लिए अलग से याद कर सकते हैं। आप प्रत्येक पंक्ति के लिए max_lines_at_distance प्रीकंपूट कर सकते हैं और इसे बाद में कैश में स्टोर कर सकते हैं। फिर, max_distance_for_lines एक लूप हो सकता है जो कैश को दो सीमाओं के अंदर सामने की जांच करता है।