2012-03-06 26 views
11

में चोटियों को खोजने के लिए एल्गोरिदम मान लें कि मेरे पास जावा int[][] array में 2 डी संचयक सरणी है। सरणी ऐसा दिखाई दे सकता:2 डी सरणी

(एक्स और z अक्ष सरणी में अनुक्रमित प्रतिनिधित्व करते हैं, वाई अक्ष मान का प्रतिनिधित्व करता है - इन ~ 4500 0 से मूल्यों के साथ एक int[56][56] के चित्र हैं) array sample 1

या

array sample 1

मैं क्या करने की जरूरत सरणी में चोटियों लगता है - पहले एक में 2 चोटियों और दूसरी सरणी में 8 चोटियों देखते हैं। ये शिखर हमेशा 'स्पष्ट' होते हैं (चोटियों के बीच हमेशा एक अंतर होता है), लेकिन इन छवियों पर समान होने की आवश्यकता नहीं है, वे कम या ज्यादा यादृच्छिक हो सकते हैं - ये छवियां वास्तविक डेटा पर आधारित नहीं हैं, केवल नमूने । वास्तविक सरणी में 5000x5000 जैसे आकार हजारों से कई सौ हजारों तक चोटी के साथ हो सकते हैं ... एल्गोरिदम सार्वभौमिक होना चाहिए, मुझे नहीं पता कि सरणी या चोटियों कितनी बड़ी हो सकती है, मुझे यह भी नहीं पता कि वहां कितने चोटियों हैं कर रहे हैं। लेकिन मुझे कुछ प्रकार की सीमा पता है - कि चोटियों को किसी दिए गए मूल्य से छोटा नहीं किया जा सकता है।

समस्या यह है कि एक चोटी में पास के कई छोटे चोटियों (पहली छवि) शामिल हो सकते हैं, ऊंचाई काफी यादृच्छिक हो सकती है और आकार एक सरणी के भीतर काफी अलग हो सकता है (आकार - मेरा मतलब है कि इकाइयों की संख्या सरणी में लेता है - एक चोटी 6 इकाइयों और 90 से दूसरे में हो सकती है)। यह भी तेज होना चाहिए (सभी 1 पुनरावृत्ति में किया जाता है), सरणी वास्तव में बड़ी हो सकती है।

किसी भी मदद की सराहना की जाती है - मुझे आपके द्वारा कोड की अपेक्षा नहीं है, सिर्फ सही विचार :) धन्यवाद!


संपादित करें: आप डोमेन के बारे में पूछा - लेकिन यह काफी जटिल है और imho यह समस्या के साथ मदद नहीं कर सकता। यह वास्तव में 3 डी बिंदुओं के साथ ऐरेलिस्ट्स की एक सरणी है, जैसे ArrayList < प्वाइंट 3 डी> [] [] और प्रश्न में मूल्य ArrayList का आकार है। प्रत्येक चोटी में एक क्लस्टर (विमान, इस मामले में) से संबंधित बिंदु होते हैं - यह सरणी एक एल्गोरिदम का परिणाम है, जो पॉइंटक्लाउड को विभाजित करती है। मुझे चोटी में उच्चतम मूल्य खोजने की ज़रूरत है, इसलिए मैं 'सबसे बड़ी' सरणीसूची से एक विमान में बिंदुओं को फिट कर सकता हूं, इसके कुछ पैरामीटर की गणना कर सकता हूं और चोटी से अधिकांश बिंदुओं को ठीक से क्लस्टर कर सकता हूं।

+1

क्या शिखर को परिभाषित करता है? –

+1

चोटियों के बीच निश्चित विभाजक क्या है? यही है, जब दो चोटियों एक साथ होते हैं (जैसा कि पूर्व में 1) और आप कब चाहते हैं कि वे अलग हों (जैसा कि पूर्व में 2)? – DerMike

+0

@JamesMontagne: मैंने कुछ ब्रूटफोर्स एल्गोरिदम की कोशिश की है जो अच्छी तरह से काम नहीं करते हैं, मुझे लगता है कि कुछ प्रकार का चालाक समाधान हो सकता है जो मुझे नहीं दिखाई देता है :) –

उत्तर

7

वह कुछ प्रकार के अनुकूलन हेरिस्टिक का उपयोग करके वैश्विक अधिकतम अनुमान लगाने में रूचि नहीं रखता है - वह सिर्फ अलग-अलग समूहों में से प्रत्येक के भीतर अधिकतम मूल्यों को ढूंढना चाहता है।

इन चोटियों हमेशा 'स्पष्ट' कर रहे हैं

आपकी छवियों के आधार पर, मुझे लगता है तुम्हारा मतलब वहाँ हमेशा है कुछ 0 समूहों को अलग करने -values ​​(वहाँ हमेशा चोटियों के बीच एक अंतर है)? यदि ऐसा है, तो आप क्लस्टर की पहचान करने के लिए एक साधारण flood-fill का उपयोग कर सकते हैं। बाढ़ भरने के दौरान आप प्रत्येक क्लस्टर के अधिकतम ट्रैक का ट्रैक भी रख सकते हैं, ताकि आप दोनों क्लस्टर की पहचान कर सकें और अपने अधिकतम एक साथ मिल सकें।

यह जितनी जल्दी आप (जो गलत जवाब लौट सकता है) heuristics पर निर्भर रहे बिना, प्राप्त कर सकते हैं, क्योंकि प्रत्येक क्लस्टर की अधिकतम संभावित क्लस्टर में किसी भी मूल्य हो सकता है, ताकि आप उन्हें जांच करने के लिए है भी है सब कम से कम एक बार।


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

+1

मुझे जितना कम या कम चाहिए - क्लस्टर की पहचान करें और फिर अधिकतम क्लस्टर के भीतर खोजें। और हाँ, मेरे पास कुछ प्रकार के 0-मूल्य हैं, मुझे लगता है कि मुझे कुछ ट्रेसहोल्ड मिल सकता है जो काम करेगा। मैं आपके द्वारा उल्लिखित विधि की जांच करूंगा, यह दिलचस्प लगता है। –

+0

यदि आप इसे एक छवि-प्रोसेसिंग समस्या के रूप में देखते हैं, तो यह थ्रेसहोल्डिंग (0 की थ्रेसहोल्ड स्थिति के साथ) है, इसके बाद [कनेक्टेड घटक रंग] (http://en.wikipedia.org/wiki/Connected-component_labeling)। वह एल्गोरिदम है, मुझे लगता है, बाढ़ भरने से सरल है। मुझे लगता है कि डिस्जिइंट-सेट संरचना का एक सरल संशोधन आपको सेट में अधिकतम मूल्य को ट्रैक करने देगा; यदि आप अधिकतम की जरूरत है तो आप सेट स्ट्रक्चर के साथ भी डिस्पेंस करने में सक्षम हो सकते हैं। –

+0

@ टॉम: मैं असहमत हूं कि बाढ़ भरने से यह आसान है, लेकिन दोनों काम करेंगे, वे दोनों बेहद सरल हैं, और दोनों एक ही गति के बारे में होंगे। –

2

यह एक इष्टतम समाधान नहीं हो सकता है, लेकिन चूंकि समस्या कुछ तरल पदार्थ भी लगता है, इसलिए मैं इसे लिखूंगा।

  1. आपके न्यूनतम सीमा से अधिक सभी मूल्यों (और निर्देशांक) की एक सूची बनाएं।
  2. इसे ऊंचाई के अवरोही क्रम में क्रमबद्ध करें।
  3. पहला तत्व सबसे बड़ा शिखर होगा, इसे शीर्ष सूची में जोड़ें।
  4. फिर सूची को नीचे उतरें, यदि वर्तमान तत्व सभी मौजूदा चोटियों से न्यूनतम दूरी से आगे है, तो इसे शीर्ष सूची में जोड़ें।

यह एक रैखिक वर्णन है लेकिन सभी चरणों (3 को छोड़कर) को समान रूप से समांतर किया जा सकता है। चरण 4 में आप एक कवरेज मैप का भी उपयोग कर सकते हैं: बूलियन की एक 2 डी सरणी जो दिखाती है कि कौन से निर्देशांक पास के शिखर द्वारा "कवर" किए गए हैं।

(चेतावनी emptor: एक बार जब आप मानदंड परिशोधित करते हैं, तो यह समाधान पूरी तरह से असुरक्षित हो सकता है, लेकिन सामान्य रूप से यह काम करता है।)

+0

इसमें 2 समस्याएं हैं - फ़र्ट्स चरण 4 में 'न्यूनतम दूरी' को परिभाषित करने का तरीका है। पहली छवि में, इसे दूसरी सरणी की तुलना में बहुत बड़ा होना होगा। दूसरा, यह काफी धीमा होगा। –

+0

@ जा-सी हां, यह धीमा है। लेकिन यह कितना धीमा है आपके डेटा और समस्या का सटीक निर्माण पर निर्भर करता है। सैकड़ों हजारों चोटियों को ढूंढना जल्दी नहीं होगा, जिस तरह से आप इसे कर रहे हैं। लेकिन मैं वास्तव में न्यूनतम दूरी की समस्या को समझ नहीं पा रहा हूं। निश्चित रूप से "चोटियों के बीच न्यूनतम दूरी" एक पैरामीटर है जिसे आपको सेट करना है। – biziclop

+0

यह सच है कि कई चोटियों नहीं होंगे, लेकिन वे थ्रेसहोल्ड से अधिक मूल्यों की एक बड़ी संख्या से हो सकते हैं। और मैं बस नहीं जानता, मैं न्यूनतम दूरी कैसे निर्धारित करूंगा। पहली छवि में, एक चोटी में कई स्थानीय maximums हैं, लेकिन उनके बीच की दूरी दूसरे मामले में 3 निकटतम peeks के बीच की दूरी के बराबर है। –

1

Simulated annealing, या hill climbing तुरंत दिमाग में आता है। हालांकि ये एल्गोरिदम गारंटी नहीं देंगे कि सभी चोटियों को पाया जाता है।

हालांकि यदि आपके "चोटियों" को अंतर के रूप में 0 के मानों से अलग किया गया है, तो शायद connected components analysis मदद करेगा। यदि आप 0 से अधिक मानों से जुड़े होते हैं (या यदि आपके पास निश्चित थ्रेसहोल्ड है, लेबल क्षेत्र उस सीमा से जुड़े हुए हैं) के साथ एक क्षेत्र को लेबल किया जाएगा, तो आपके घटकों की संख्या आपकी चोटी की संख्या होगी। आप प्रत्येक घटक के अधिकतम को खोजने के लिए सरणी का एक और पास भी कर सकते हैं।

मुझे ध्यान रखना चाहिए कि जुड़े घटक रैखिक समय में किए जा सकते हैं, और शीर्ष मूल्यों को रैखिक समय में भी किया जा सकता है।

+0

@downvoter समझाने की देखभाल? – NominSim

+0

मैं डाउनवॉटर नहीं हूं, लेकिन मैं पहाड़ी चढ़ाई के लिए -1 दूंगा (क्योंकि मुझे नहीं लगता कि यह आपको सीधे सभी चोटियों की पहचान करने में मदद करता है, बिना उप-चोटियों को भी अनदेखा किया जा सकता है) और कनेक्ट के लिए +1 घटक विश्लेषण। –

+2

@ टॉम एंडरसन हाँ, यही कारण है कि मैंने हिल चढ़ाई के साथ जवाब नहीं दिया, बल्कि यह उल्लेख किया कि इस समस्या के साथ यही बात आती है। – NominSim

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