रूबी में यात्रा करने वाले विक्रेता समस्या को हल करना (50+ स्थान)

Question

मैं एक वितरण कंपनी में काम कर रहा हूं। वर्तमान में हम "हाथ" द्वारा 50+ स्थानों के मार्गों को हल करते हैं।

मैं इस समस्या को हल करने के लिए Google मानचित्र API का उपयोग करने के बारे में सोच रहा हूं, लेकिन मैंने पढ़ा है कि 24 अंक सीमा है।

वर्तमान में हम अपने सर्वर में रेल का उपयोग कर रहे हैं, इसलिए मैं एक रूबी स्क्रिप्ट का उपयोग करने के बारे में सोच रहा हूं जो 50+ स्थानों के निर्देशांक प्राप्त करेगा और एक उचित समाधान आउटपुट करेगा।

इस समस्या से निपटने के लिए आप किस एल्गोरिदम का उपयोग करेंगे?

क्या रूबी इस प्रकार की समस्या को हल करने के लिए एक अच्छी प्रोग्रामिंग भाषा है?

क्या आप किसी भी मौजूदा रूबी स्क्रिप्ट के बारे में जानते हैं?

Answer 1

यह हो सकता है आप के लिए क्या देख रहे:

चेतावनी:

इस साइट का दौरा साइट के रूप में फ़ायरफ़ॉक्स द्वारा चिह्नित किया जाता है - लेकिन मैं होने के लिए प्रकट नहीं होता। वास्तव में मैं इसे पहले प्रयोग किया जाता है एक समस्या के बिना

[URL के लिए संशोधन इतिहास की जाँच करें]

rubyquiz बंद हो गया है (एक बिट के लिए नीचे दिया गया है) लेकिन आप अभी भी करने के लिए वेबैक मशीन और archive.org की जांच कर सकते उस पृष्ठ देखें:
1: http://web.archive.org/web/20100105132957/http://rubyquiz.com/quiz142.html

Answer 2

अनुकूलित समाधान में से एक गतिशील प्रोग्रामिंग का उपयोग कर रहा है लेकिन अभी भी बहुत महंगा ओ (2 ** एन) है, जो बहुत व्यवहार्य नहीं है, जब तक कि आप कुछ क्लस्टरिंग और कंप्यूटिंग, रूबी या एकल सर्वर वितरित नहीं करते हैं, बहुत उपयोगी नहीं होंगे तुम्हारे लिए।

मैं आपको डीपी या ब्रूट फोर्स का उपयोग करने के बजाय लालची मानदंड के साथ आने की सलाह दूंगा जो लागू करना आसान होगा।

एक बार आपका प्रोग्राम समाप्त हो जाने पर आप कुछ यादें कर सकते हैं, और परिणामों को बाद में लुकअप के लिए कहीं स्टोर कर सकते हैं, जो आपको कुछ चक्र भी बचा सकता है। कोड के संदर्भ में

, आपको वजन वाले किनारों, किनारों को लागू करने की आवश्यकता होगी।

यानी: वर्टेक्स वर्ग जिसमें वजन, किनारों के साथ किनारों हैं। एक ग्राफ वर्ग की तुलना में जो डेटा को पॉप्युलेट करेगा।

Answer 3

यहाँ चाल के एक जोड़े हैं गांठ स्थानों है कि अपेक्षाकृत करीब एक ग्राफ में हैं, और आपके मुख्य ग्राफ में एक भी नोड में उन स्थानों बदल जाते हैं। यह आपको बहुत अधिक काम किए बिना लालची बनने देता है।
2: अनुमानित एल्गोरिदम का उपयोग करें।
2 ए: मेरा पसंदीदा बिटनिक टूर है। वे हैक करने के लिए बहुत आसान हैं।
देखें अद्यतन

Here's a py lib with a bitonic tour और here's another
मुझे एक गहरे लाल रंग का एक देखने चलते हैं। मुझे केवल RGL से अधिक खोजने में परेशानी हो रही है, जिसमें दक्षता समस्याएं हैं ....

अद्यतन
आपके मामले में, कम से कम फैले पेड़ हमले प्रभावी होना चाहिए। मैं ऐसे मामले के बारे में नहीं सोच सकता जहां आपके शहर त्रिभुज असमानता को पूरा नहीं करेंगे। इसका मतलब है कि लगभग अपेक्षाकृत तरह के सभ्य अनुमान के अपेक्षाकृत प्रकार का होना चाहिए। विशेष रूप से अगर दूरी euclidean है, जो मुझे लगता है, फिर, यह होना चाहिए।

Answer 4

यहां तक ​​कि किसी अन्य उत्तर में उल्लिखित डीपी समाधान के साथ, ओ (10^15) संचालन की आवश्यकता होगी। तो आपको अनुमानित समाधानों को देखना होगा, जो शायद स्वीकार्य हैं कि आप वर्तमान में उन्हें हाथ से करते हैं। http://en.wikipedia.org/wiki/Travelling_salesman_problem#Heuristic_and_approximation_algorithms

Answer 5

यदि आप चाहते हैं कि एल्गोरिदम द्वारा उत्पादित समाधान की लागत इष्टतम के 3/2 के भीतर है तो आप क्रिस्टोफाइड एल्गोरिदम चाहते हैं। एसीओ और जीए की गारंटीकृत लागत नहीं है।

Answer 6

मैं Bays29 (29-शहर) समस्या के लिए हल करने के लिए इस तरह के TSP समस्याओं चींटी कॉलोनी Optimazation के रूप में मेटा-heurestic एल्गोरिदम का उपयोग करने पर काम किया, और यह मुझे बहुत ही कम समय में इष्टतम समाधान के करीब दे दी है। आप संभावित रूप से इसका उपयोग कर सकते हैं।

मैं जावा में लिखा था, हालांकि, मैं इसे यहाँ वैसे भी रूबी के लिए लिंक करेगा, क्योंकि मैं वर्तमान में एक बंदरगाह पर काम कर रहा हूँ: जावा: https://github.com/mohammedri/ant_colony_java_TSP रूबी: https://github.com/mohammedri/aco-ruby (अधूरा) यह डेटासेट इसके लिए हल करती है: https://github.com/jorik041/osmsharp/blob/master/Core/OsmSharp.Tools/Benchmark/TSPLIB/Problems/TSP/bays29.tsp

ध्यान रखें कि मैं प्रत्येक शहर यानी सीधी रेखा दूरी के बीच यूक्लिडियन दूरी का उपयोग कर रहा हूं, मुझे नहीं लगता कि सड़कों और शहर के मानचित्र आदि पर विचार करने वाले वास्तविक जीवन की स्थिति में आदर्श है लेकिन यह एक अच्छी शुरुआत हो सकती है बिंदु :)