मैं यह पता लगाने की कोशिश कर रहा हूं कि एल्गोरिदम कैसे डिज़ाइन किया जाए जो ओ ((एन + एस) लॉग एन) जटिलता के साथ इस कार्य को पूरा कर सके। चौराहे की मात्रा होने के नाते। मैंने इंटरनेट पर खोज करने की कोशिश की है, फिर भी वास्तव में कुछ नहीं मिल सका।ओ ((एन + एस) लॉग एन में कंप्यूटिंग सर्कल चौराहे)
वैसे भी, मुझे एहसास है कि एक अच्छी डेटा संरचना यहां महत्वपूर्ण है। मैं जावा में एक लाल ब्लैक ट्री कार्यान्वयन का उपयोग कर रहा हूं: TreeMap। मैं अपनी समस्या से निपटने में मदद करने के लिए प्रसिद्ध (?) स्वीप-लाइन एल्गोरिदम का भी उपयोग करता हूं।
मुझे पहले अपना सेटअप समझाएं।
मेरे पास शेड्यूलर है। यह प्राथमिकता है क्योंकि मेरी मंडलियों ने अपने सबसे बाएं समन्वय के आधार पर आदेश दिया (आरोही)। scheduler.next() मूल रूप से प्राथमिकता क्यूयू का चुनाव करता है, जो अगले सबसे बाएं सर्कल को लौटता है।
public Circle next()
{ return this.pq.poll(); }
मेरे यहां 4 एन ईवेंट पॉइंट्स के साथ एक सरणी भी है। प्रत्येक सर्कल को अनुदान में 2 इवेंट पॉइंट होते हैं: अधिकांश बाएं एक्स और सबसे दाएं एक्स। अगली घटना बिंदु प्राप्त करने के लिए शेड्यूलर में एक विधि स्वीपलाइन() है।
public Double sweepline()
{ return this.schedule[pointer++]; }
मेरे पास भी एक स्थिति है। स्वीप-लाइन स्थिति अधिक सटीक होने के लिए। सिद्धांत के अनुसार, स्थिति में वे मंडल शामिल हैं जो एक-दूसरे से तुलना करने योग्य हैं। इस पूरी कहानी में स्वीप लाइन होने का मुद्दा यह है कि आप कई उम्मीदवारों से इंकार कर सकते हैं क्योंकि वे बस मौजूदा सर्कल के त्रिज्या के भीतर नहीं हैं।
मैंने स्थिति को TreeMap<Double, Circle> के साथ लागू किया। circle.getMostLeftCoord().
यह वृक्ष मानचित्र डालने/निकालने/खोजने के लिए ओ (लॉग एन) की गारंटी देता है।
एल्गोरिथ्म ही इसलिए की तरह कार्यान्वित किया जाता है:
Double sweepLine = scheduler.sweepline();
Circle c = null;
while (notDone){
while((!scheduler.isEmpty()) && (c = scheduler.next()).getMostLeftCoord() >= sweepLine)
status.add(c);
/*
* Delete the oldest circles that the sweepline has left behind
*/
while(status.oldestCircle().getMostRightCoord() < sweepLine)
status.deleteOldest();
Circle otherCircle;
for(Map.Entry<Double, Circle> entry: status.keys()){
otherCircle = entry.getValue();
if(!c.equals(otherCircle)){
Intersection[] is = Solver.findIntersection(c, otherCircle);
if(is != null)
for(Intersection intersection: is)
intersections.add(intersection);
}
}
sweepLine = scheduler.sweepline();
}
संपादित करें: Solver.findIntersection(c, otherCircle); रिटर्न अधिकतम 2 चौराहे अंक। ओवरलैपिंग सर्कल को कोई चौराहे नहीं माना जाता है।
SweepLineStatus
public class BetterSweepLineStatus {
TreeMap<Double, Circle> status = new TreeMap<Double, Circle>();
public void add(Circle c)
{ this.status.put(c.getMostLeftCoord(), c); }
public void deleteOldest()
{ this.status.remove(status.firstKey()); }
public TreeMap<Double, Circle> circles()
{ return this.status; }
public Set<Entry<Double, Circle>> keys()
{ return this.status.entrySet(); }
public Circle oldestCircle()
{ return this.status.get(this.status.firstKey()); }
मैं अपने कार्यक्रम का परीक्षण किया की कोड, और मैं स्पष्ट रूप से हे था (एन^2) जटिलता। मुझे यहां क्या याद आ रही है? कोई भी इनपुट जो आप लोग प्रदान करने में सक्षम हो सकते हैं, स्वागत से अधिक है।
अग्रिम धन्यवाद!
"और मुझे स्पष्ट रूप से ओ (एन^2) जटिलता थी" - प्रोग्राम चलाने से बताना असंभव है, क्योंकि अन्यथा आप रोक समस्या को हल कर सकते हैं। –
आप ओ ओ (एन लॉग एन) 'समय में विमान में' एन' सर्कल के सभी चौराहे बिंदु चाहते हैं, है ना? सर्कल पर कोई बाधा नहीं है? –
यह सबूत नहीं है। यह सिर्फ प्रयोगात्मक डेटा है। –