सेगमेंटेड कम से कम वर्ग एल्गोरिदम, इस गतिशील प्रोग्रामिंग अवधारणा को सभी

Question

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

पीडीएफ चेतावनी: http://www.cs.uiuc.edu/class/sp08/cs473/Lectures/lec10.pdf

मुझे नहीं लगता कि इसकी एक स्पष्ट रूप से बताया गया है, मुझे यकीन है कि समझ में नहीं आता।

क्या हो रहा है की मेरी समझ यह है:

हम अंक (x1, y1), (x2, y2) .. के का एक सेट है और हम कुछ लाइनों है कि सबसे अच्छा इस डेटा फिट खोजने के लिए चाहते हैं। हमारे पास कई सीधी रेखाएं हो सकती हैं, और ये रेखाएं ए और बी (वाई = कुल्हाड़ी + बी) के लिए दिए गए फ़ोरम से आती हैं।

अब एल्गोरिदम अंत (?) से शुरू होता है और मानता है कि एक बिंदु पी (x_i, y_i) रेखा खंड का हिस्सा है। फिर नोट्स का कहना है कि इष्टतम समाधान 'पी 1, के लिए इष्टतम समाधान है। । । पीआई -1} प्लस (सर्वश्रेष्ठ) लाइन {पीआई, के माध्यम से। । । PN} '। जो मेरा मतलब है, कि हम बिंदु पी (x_i, y_i) पर जाते हैं और पीछे की ओर जाते हैं और शेष बिंदुओं के माध्यम से एक और रेखा खंड पाते हैं। अब इष्टतम समाधान इन पंक्ति खंड दोनों है।

फिर यह एक तार्किक कूद लेता है जिसका मैं पालन नहीं कर सकता, और कहता है "मान लीजिए कि आखिरी बिंदु पीएन एक सेगमेंट का हिस्सा है जो पी_आई से शुरू होता है। यदि ऑप्ट (जे) पहले जे पॉइंट्स और ई की लागत को दर्शाता है (जे, के) बिंदु जे से के माध्यम से सबसे अच्छी लाइन की त्रुटि तो ऑप्ट (एन) = ई (i, n) + सी + ऑप्ट (i - 1) "

फिर एल्गोरिदम के लिए छद्म कोड है , जो मुझे समझ में नहीं आता है। मैं समझता हूं कि हम अंक की सूची के माध्यम से पुन: प्रयास करना चाहते हैं और ओपीटी (एन) फॉर्मूला को कम करने वाले बिंदुओं को ढूंढना चाहते हैं, लेकिन मैं इसका पालन नहीं करता हूं। यह मुझे बेवकूफ महसूस कर रहा है।

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

आपके समय के लिए धन्यवाद और इसे पढ़ने के लिए, मैं इसकी सराहना करता हूं।

Answer 1

गतिशील प्रोग्रामिंग का मूल आधार ऑप्टिमाइज़ करना है (उपरोक्त समस्याओं को संग्रहीत करते समय 'लागत' या इस मामले में, त्रुटि को कम करें) जब आप जाते हैं तो उन्हें पुनः संयोजित नहीं किया जाता है (इसे ज्ञापन कहा जाता है) ।

यह थोड़ी देर हो चुकी है इसलिए मुझे बहुत विस्तृत जानकारी नहीं मिल रही है, लेकिन ऐसा लगता है कि आपके पास मुख्य डीपी के साथ सबसे अधिक समस्या है। 'Segmeneted' गुणवत्ता की वजह से यहां डीपी की आवश्यकता है। जैसा कि आपका पीडीएफ दिखाता है, कम से कम वर्गों द्वारा सर्वोत्तम फिट लाइन ढूंढना सरल है और डीपी की आवश्यकता नहीं है।

ऑप्ट (एन) - ई (मैं, एन) + सी + ऑप्ट (i-1) --- हमारे लागत समारोह जहां
सी एक नई लाइन खंड की लगातार लागत (जो समस्या के बिना तुच्छ है और हम केवल दो बिंदुओं के लिए नए लाइन सेगमेंट बनाएंगे)
ई (i, n) एक सेगमेंट (रिकर्सिव नहीं)
ऑप्ट (i-1) कम से कम बिंदुओं की त्रुटि है I पहला बिंदु से रिकर्सिवली लागत (i-1) के लिए वें

अब एल्गोरिथ्म

अंकों की सूची सुनिश्चित एक्स के अनुसार क्रमबद्ध है महत्व देता
एम [0] = 0 --- आत्म व्याख्यात्मक
सभी जोड़ों को (i, j) के लिए के साथ मैं < j: लगता है ई (i, j) - --- (इसके लिए घोंसला/foreach loops, या एक समझ प्रकार की संरचना की आवश्यकता होगी। 2 डी सरणी में इन मूल्यों को स्टोर)
के लिए (जे = 1..n): एम [जे] = मिनट (! [ऑप्ट (जे) मैं के लिए रेंज में (1, जे)]

तो मूल रूप से, किसी भी दो संभावित बिंदुओं के बीच एक-लाइन लागत पाएं, ई
में स्टोर करें 1 से अधिक के बीच जे के लिए कम से कम लागत पाएं, रास्ते के साथ मूल्य बाद में गणना के साथ मदद करेगा, इसलिए उन्हें स्टोर करें! ध्यान दें कि मैं भी ऑप्टिमाइज़ करने के लिए एक पैरामीटर है। एम [एन] कुल अनुकूलित लागत है।

आपके लिए प्रश्न - आप कैसे निर्धारित कर सकते हैं कि विभाजन कहां होता है? आप इसका उपयोग कैसे कर सकते हैं, और एम, सेट के सेट को निर्धारित करने के लिए लाइन खंड एक बार मैं टीएस खत्म हो गया?

आशा है कि इससे मदद मिलती है!

Answer 2

मुश्किल हिस्सा है, गतिशील प्रोग्रामिंग भाग, अनुभाग

for j = 1 to n 
    M[j] = min_(1=<i=<j) (e(i,j) + C + M[i-1]) 

जहां M[0] = 0 पहले किया है और n डेटा बिंदुओं की कुल संख्या है जाता है। इसके अलावा, अंडरस्कोर का अर्थ है कि बाद में कोष्ठक में अनुभाग को सब्सक्राइब किया जाना चाहिए। प्रोफेसर ने एम के बजाए ओपीटी का इस्तेमाल किया होगा, और यह कुछ अन्य विश्वविद्यालयों के व्याख्यानों में किया जाता है, जो आप वेब पर पा सकते हैं (और जो लगभग समान दिखते हैं)। अब, यदि आप उपरोक्त मेरे कोड ब्लॉक को देखते हैं और व्याख्यान में, आपको एक अंतर दिखाई देगा। मैंने M[i-1] का उपयोग किया और आपके प्रोफेसर ने M[j-1] का उपयोग किया। यह आपके प्रोफेसर के छद्म कोड में एक टाइपो है। आप पहले स्लाइड पर भी देख सकते हैं और देख सकते हैं कि उसे वहां त्रुटि फ़ंक्शन में सही था।

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

इसके अलावा, e(i,i) = 0 के साथ-साथ e(i,i+1) याद रखें क्योंकि किसी बिंदु पर एक पंक्ति को फ़िट करने से कोई त्रुटि नहीं होती है और साथ ही केवल दो बिंदु भी होती है।

Answer 3

बिंदु 1 से शुरू होने से, बिंदु बिंदु तक तक का सबसे अच्छा समाधान, अंतिम लाइन सेगमेंट में नया एंड-पॉइंट जे शामिल होना चाहिए, इसलिए समस्या बन जाती है कि मुझे अंतिम विभाजन को कम करने के लिए अंतिम विभाजन कहाँ रखना है यह अंतिम लाइन सेगमेंट?

सौभाग्य से लागत को उसी समस्या के उपप्रबंधों के संदर्भ में गणना की जाती है, जिसे आप हल करने की कोशिश कर रहे हैं, और सौभाग्य से आप अगली बिंदु जे में स्थानांतरित होने तक इन छोटे उपप्रवाहों को पहले ही हल कर चुके हैं। तो नए बिंदु पर आप एक नया लाइन खंड विभाजित करने के लिए बिंदु 1 और जे के बीच एक इष्टतम बिंदु खोजने की कोशिश कर रहे हैं जिसमें जम्मू शामिल है, और लागत को कम करता है: optimal_cost_up_to (i) + cost_of_split + cost_of_lsq_fit (i + 1 , जे)। अब भ्रमित करने वाला हिस्सा यह है कि किसी भी समय ऐसा लगता है कि आप केवल एक ही विभाजन खोज रहे हैं, लेकिन हकीकत में सभी पिछले विभाजन इष्टतम_cost_up_to (i) द्वारा निर्धारित किए जाते हैं, और चूंकि आपने इन सभी बिंदुओं के लिए पहले से ही इष्टतम लागत की गणना की है जे तक पहुंचने के बाद, आपको केवल उत्तरों को याद करने की आवश्यकता है ताकि प्रत्येक बार जब यह एक बिंदु आगे बढ़ता है तो एल्गोरिदम को इन लागतों को फिर से समझना नहीं पड़ता है।

अजगर में मैं शायद, परिणाम स्टोर करने के लिए हालांकि यह गतिशील प्रोग्रामिंग एल्गोरिथ्म के लिए एक सरणी बेहतर हो सकता है एक शब्दकोश का उपयोग करें ...

वैसे भी

...

def optimalSolution(points,split_cost) 
     solutions = {0:{'cost':0,'splits':[]}} 
     for j in range(1,len(points)): 
      best_split = None 
      best_cost = lsqFitCost(points,0,j) 
      for i in range(0,j): 
       cost = solutions[i]['cost'] + split_cost + lsqFitCost(points,i+1,j) 
       if cost < best_cost: 
        best_cost = cost 
        best_split = i 
      if best_split != None: 
       solution[j] = {'cost':best_cost,'splits':solution[best_split]['splits']+[best_split]} 
      else: 
       solution[j] = {'cost':best_cost,'splits':[]} 
     return solutions 

यह बहुत नहीं है , और मैंने इसे चेक नहीं किया है (ऐसे मामले में कोई त्रुटि हो सकती है जहां कोई स्प्लिट सबसे अच्छी लागत नहीं है), लेकिन उम्मीद है कि यह आपको सही रास्ते पर लाने में मदद करेगा? ध्यान दें कि lsqFitCost को प्रत्येक पुनरावृत्ति पर बहुत अधिक काम करना पड़ता है, लेकिन कम से कम वर्ग रेखा इस तरह फिट होती है, तो आप गणना में उपयोग की जाने वाली रकम को बनाए रखकर इस लागत को बहुत कम कर सकते हैं ... आपको Google को कम से कम लाइन फिटिंग करना चाहिए और जानकारी। यह lsqFitCost स्थिर बना सकता है ताकि समग्र समय ओ (एन^2) होगा।

Answer 4

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

खंडित कम से कम वर्ग समस्या में, हमारे पास दिए गए बिंदुओं को फिट करने के लिए कई सेगमेंट हो सकते हैं और हमें उपयोग किए गए प्रत्येक नए सेगमेंट के लिए लागत का भुगतान करना होगा। यदि एक नया सेगमेंट का उपयोग करने की लागत 0 थी, तो हम प्रत्येक बिंदु के माध्यम से एक अलग लाइन पार करके सभी बिंदुओं को पूरी तरह से फिट कर सकते थे।

अब मान लीजिए कि हम उन खंडों का सेट ढूंढने की कोशिश कर रहे हैं जो एन दिए गए बिंदुओं के लिए सबसे उपयुक्त हैं। अगर हम एन -1 सबप्रोबल्म्स के लिए सबसे अच्छे समाधान जानते थे: पहले बिंदु के लिए सबसे अच्छा फिट, पहले 2 अंक के लिए सबसे अच्छा फिट, ..., पहले एन -1 अंक के लिए सबसे अच्छा फिट, तो हम मूल समस्या के लिए सबसे अच्छा समाधान की गणना कर सकते हैं एन अंक निम्नानुसार हैं:

एनएचटी बिंदु एक सेगमेंट पर स्थित है और यह सेगमेंट कुछ पहले बिंदु पर शुरू होता है, कुछ I = 1, 2, ..., n। हमने पहले से ही सभी छोटे उपप्रकारों को हल कर लिया है, यानी एन अंक से कम होने के कारण हम कम से कम उन बिंदुओं के लिए सर्वश्रेष्ठ फिट पा सकते हैं जो कम से कम एन पॉइंट्स को कम कर सकते हैं:

पहले i-1 अंक (पहले से गणना की गई) के लिए सर्वोत्तम फिट की लागत + एकल की लागत लाइन जो I से n (कम से कम वर्ग समस्या का उपयोग कर) के लिए सबसे उपयुक्त है + एक नए सेगमेंट का उपयोग करने की लागत

उपरोक्त मात्रा को कम करने वाला मेरा मान हमें समाधान देता है: subproblem i- 1 और बिंदु I से n के माध्यम से खंड।

आप और अधिक मदद की ज़रूरत है, मैं एल्गोरिथ्म के एक विवरण लिखा और सी ++ कार्यान्वयन यहाँ प्रदान की है: http://kartikkukreja.wordpress.com/2013/10/21/segmented-least-squares-problem/