52
कम से कम मैं निम्नलिखित समस्या को हल करने के लिए एक बेहतर एल्गोरिथ्म खोजने के लिए करना चाहते हैं:को न काटने रेखा खंड जबकि संचयी लंबाई
वहाँ एन प्रारंभिक बिंदु (बैंगनी) और एन लक्ष्य अंक (हरा) कर रहे हैं 2 डी में मैं एक एल्गोरिदम चाहता हूं जो शुरुआती बिंदुओं को एक रेखा सेगमेंट (ब्राउन) द्वारा लक्षित बिंदुओं से जोड़ता है, इनमें से किसी भी सेगमेंट को बिना छेड़छाड़ (लाल) और सभी सेगमेंट की संचयी लंबाई को कम करने के दौरान।
सी ++ में मेरा पहला प्रयास सभी संभावित राज्यों को अनुमति दे रहा था, छेड़छाड़ मुक्त राज्य ढूंढ सकता था, और उन राज्यों में न्यूनतम कुल सेगमेंट लंबाई ओ (एन!) था। लेकिन मुझे लगता है कि एक बेहतर तरीका होना चाहिए।
किसी भी विचार? या खोज के लिए अच्छे कीवर्ड?
शायद कुछ प्रकार के स्थलीय प्रकार? –
मुझे जवाब भी नहीं पता है, लेकिन मैं कोई समाधान (संघर्षों को अनदेखा कर दूंगा) और फिर अलग-अलग संघर्ष को हल करूंगा: जब दो पंक्तियां संघर्ष करती हैं, ऐसा लगता है कि अंत बिंदुओं की एक जोड़ी को स्विच करना संघर्ष को हल करता है। मुझे यकीन नहीं है कि प्रगति की गारंटी कैसे दी जाए, हालांकि। –
@ डाइटमारकुहल: एंडपॉइंट्स को स्विच करने से एक अलग संघर्ष दिखाई दे सकता है। –