2014-05-14 11 views
5

मेरे पास सीधे रेखा खंडों द्वारा परिभाषित एक आकार है।अनुकूलन के साथ आकार एल्गोरिदम

मैं आकृति को सीधे लाइनों के साथ सरल बनाना चाहता हूं लेकिन केवल ढलानों के सीमित सेट के साथ।

मैं पहले से और बाद में आकार में क्षेत्र में अंतर को कम करने और कम से कम खंडों को कम करना चाहता हूं।

मैं एक साथ परिभाषित वजन के साथ इन दो चीजों को एक साथ कम करना चाहता हूं, एक दूसरे से कम को कम करने पर जोर देना।

minimize { J = w1(number of segments/length) + w2(difference area/length) } 

कहाँ w1 और w2 दोनों वजन रहे हैं और लंबाई नया खंड की लंबाई है। मुझे एक एल्गोरिदम चाहिए जो यह करता है। कोई विचार?

नीचे मैं कुछ तस्वीरें दिखाता हूं कि मैं इसे कैसे काम करना चाहता हूं। क्या साहित्य में कुछ भी है जो एल्गोरिदम लिखने में मदद कर सकता है। धन्यवाद!

enter image description here

उत्तर

0

यह एक बहुत ही कठिन समस्या की तरह लगता है!

  1. diffArea(fig, target)
  2. decomp(fig, p1, p2, s1, s2) दो आंकड़े इस बात का एक जोड़ी के साथ p1 और p2 के बीच सभी सेगमेंट की जगह द्वारा बनाया जा सकता गणना करता fig और target के बीच का अंतर क्षेत्र की गणना करता: मैं पहले दो दिनचर्या को परिभाषित करते हुए यह दृष्टिकोण होगा आकार s1 और s2 के खंड। उदाहरण के लिए, और p2 के बीच fig में 0 सेगमेंट के बीच चार सेगमेंट थे, तो decomp(fig, p1, p2, s1, s2) उन चार खंडों को दोहराता है जो s1 और s2 के उचित पैमाने पर स्केल किए गए संस्करणों के साथ उन चार खंडों को प्रतिस्थापित करके उत्पन्न होते हैं। और s2 को p1 और p2 (क्योंकि हम 2-डी स्पेस में हैं) के बीच स्थान भरने के लिए केवल एक ही तरीका है, और दोनों आंकड़े उन्हें s1 -> s2 या s2 -> s1 ऑर्डर करने से आते हैं।

इन दो दिनचर्या को देखते हुए, मुझे लगता है कि एक पुनरावृत्त स्थानीय खोज प्रक्रिया अच्छी तरह से काम कर सकती है। आप नीचे दिए गए चरण होते हैं:

  1. एक बड़ी सीमांकन आकार के चारों ओर target
  2. करने के लिए fig सेट कोने fig में (p1, p2) के प्रत्येक जोड़ी के लिए (के बीच 1 खंड, तो, के बीच 2 खंड के साथ जोड़े के साथ शुरू ...) और आकार की प्रत्येक जोड़ी के (s1, s2) के लिए:
    • कंप्यूट fig1 और fig2 का उपयोग कर decomp(fig, p1, p2, s1, s2)
    • चलो e_figfig1 में किनारों की संख्या से fig में किनारों की संख्या और e_new हो सकता है और fig2
    • w1 * e_new + w2 * diffArea(fig1, target) < w1 * e_fig + w2 * diffArea(fig, target) हैं, fig की जगह fig1
    • यदि w1 * e_new + w2 * diffArea(fig2, target) < w1 * e_fig + w2 * diffArea(fig, target), figfig2
    • के साथ बदलें

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

-1

वैसे, इस मामले Pareto efficiency में एक समाधान का एक अच्छा वजन हो रहा है। पहली नज़र में ऐसा लगता है कि एक अलग अनुकूलन का उपयोग करना अनुचित होगा। किसी विशेष एल्गोरिदम का चयन आंकड़ों की जटिलता पर निर्भर करता है। बड़े और जटिल आंकड़ों के लिए मैं अनुवांशिक एल्गोरिदम का उपयोग करने का सुझाव दूंगा।

संबंधित मुद्दे