एल्गोरिदम अनुकूलन - एकाधिक बिंदुओं के बीच सबसे छोटा मार्ग

Question

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

पूर्व: मैं छुट्टी पर हूं और मैं एक विशिष्ट शहर में रह रहा हूं। मैं किसी भी चार शहरों को देखने के लिए एक रास्ता यात्रा कर रहा हूं और मैं कम से कम दूरी की यात्रा करना चाहता हूं। मैं एक ही शहर में एक से अधिक बार नहीं जा सकता।

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

सबसे कम मार्ग खोजने के लिए बेहतर तरीका क्या है?

Answer 1

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

---

भविष्य answerers के लिए: Floyd-Warshall algorithm और सभी फ्लोयड की तरह विविधताओं यहाँ अयोग्य हैं।

Answer 2

यह ट्रैवलिंग सेल्समैन-एस्क्यू लगता है? एक समाधान एक अनुकूलन तकनीक का उपयोग करना है जैसे विकासवादी एल्गोरिदम। वर्तमान में आप एक संपूर्ण खोज कर रहे हैं, जो बहुत जल्दी धीमा हो जाएगा। लेकिन मुझे लगता है कि यह एक यात्रा विक्रेता की समस्या है और सदियों से कई दशकों तक इसका सामना नहीं किया गया है, और इस तरह हमले के कई संभावित तरीके हैं। Google आपका मित्र है।

Answer 3

में आम तौर पर आप सख्त बुरा वेरिएंट करने चाहिए ... मुझे लगता है कि आप Branch_and_bound विधि के कुछ रूपों का उपयोग करना चाहिए http://en.wikipedia.org/wiki/Branch_and_bound

Answer 4

या तो norheim.se रूप bredth पहले खोज कहा या Dijkstra's algorithm मेरे सुझाव के रूप में अच्छी तरह से किया जाएगा।

Answer 5

ऐसा प्रतीत होता है कि आपके ग्राफ़ के किनारे द्विपक्षीय हैं। इस मामले में, आप जिस एल्गोरिदम की तलाश में हैं वह Dijkstra's algorithm है।

Answer 6

शायद मूल पोस्टर का अर्थ यह है कि "प्रत्येक संभावना के माध्यम से मैन्युअल रूप से पुन: प्रयास करना और सबसे छोटा रास्ता संग्रह करना", लेकिन मैंने सोचा कि मैं स्पष्ट करना चाहता हूं कि आधारभूत समाधान क्या प्रतीत होता है।

मान लें कि आपके पास पहले से ही दो-बिंदु सबसे छोटा पथ एल्गोरिदम है - इसमें विभिन्न प्रकार के ग्राफ के लिए शास्त्रीय समाधान हैं। मान लें कि सभी दूरी nonnegative हैं और डी (ए-> बी-> सी) = डी (ए-> बी) + डी (बी-> सी)।

उदहारण के लिए:

अनिवार्य है कि पथ मध्यवर्ती शहरों "एबीसीडी" में से एक के माध्यम से हो जाता है एस पर शुरू होता है और ई के साथ समाप्त होता हैं SabcdE, SacbdE, आदि ...

केवल 4 मध्यवर्ती शहरों के साथ, आप सभी 24 क्रमपरिवर्तनों का आकलन करते हैं। प्रत्येक क्रमपरिवर्तन के लिए सिर से पूंछ के पथ की गणना करने के लिए अपने सबसे छोटे दो-बिंदु एल्गोरिदम का उपयोग करें, और इसकी कुल दूरी।

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

यह स्पष्ट रूप से मध्यवर्ती शहरों की बढ़ती संख्या के साथ खराब पैमाने पर स्केल करता है। यह मुझे स्पष्ट नहीं है कि यह तब तक बेहतर हो सकता है जब तक कि आप ग्राफ संरचना पर अधिक प्रतिबंध लगाते हैं (क्या यह भौतिक यूक्लिडेन अंतरिक्ष में है? त्रिकोण असमानता?)।

मेरा विचार उदाहरण: मान लीजिए कि शहरों के बीच सभी मध्यवर्ती दूरी ओ (1) हैं। ग्राफ पर कोई प्रतिबंध नहीं होने पर, एस से किसी भी मध्यवर्ती शहर की दूरी 1000 हो सकती है, एक को छोड़कर 1. पूंछ के लिए समान। तो आप कुछ भी होने के लिए पहले शहर को जाने के लिए मजबूर कर सकते हैं। अब, एक परत नीचे जाएं, पहला शहर "प्रारंभ बिंदु" के रूप में लें। एक ही तर्क लागू करें: आप ग्राफ़ में दूरी को जोड़कर निम्न में से किसी भी शहर में सबसे अच्छा मार्ग जा सकते हैं।

तो ऐसा लगता है कि जटिलता को अतिरिक्त धारणाओं के बिना सहायता नहीं दी जा सकती है।

Answer 7

यह बहुत आम और वास्तविक समय की स्थिति है जो कोई भी गिर सकता है। Google मानचित्र उपयोगकर्ता इंटरफ़ेस आपको उसी क्रम में पथ देता है, आप गंतव्य सूची में जोड़ते हैं। यह आपको इष्टतम पथ नहीं देता है हालांकि उनके स्वयं के Google मानचित्र API समाधान प्रदान करते हैं।

Google मानचित्र API इसके लिए समाधान प्रदान करता है। पथ को खोजने के अनुरोध में आपको ध्वज 'ऑप्टिमाइज़वेपॉइंट्स: सत्य' प्रदान करना होगा। अनुरोध इस तरह दिखेगा।

var request = { 
      origin: start, 
      destination: end, 
      waypoints: waypts, 
      optimizeWaypoints: true, 
      travelMode: google.maps.TravelMode.DRIVING 
     }; 

और आप पूरा उपयोगिता के रूप में स्रोत देखें में उपयोगिता के पूरे कोड देख सकते हैं जावास्क्रिप्ट और HTML में बना है।

मुझे आशा है कि इससे मदद मिलेगी।