के साथ ट्रैवलिंग सेल्समैन उदाहरण मैंने traveling salesman problem के लिए पायथन में एक मेमेटिक एल्गोरिदम बनाया। हालांकि, सभी टेस्ट डेटा (शहरों के बीच की दूरी की सूची) में मुझे सबसे अच्छा समाधान की जानकारी नहीं है, इसलिए मुझे नहीं पता कि ग्लोबल इष्टतम मेरे एल्गोरिदम के करीब कितना करीब है।ज्ञात वैश्विक इष्टतम
क्या किसी को पता है कि मुझे कुछ टीएसपी परीक्षण डेटा (अधिमानतः मैट्रिक्स रूप में, लेकिन कुछ भी अच्छा है) ज्ञात सर्वोत्तम समाधान के साथ कहां मिल सकता है?
क्या आपने Google किया था?
http://www.tsp.gatech.edu/data/index.html
कि पेज कई परीक्षण मामलों जिनमें से 16 एक इष्टतम समाधान है प्रदान करता है।
हां, लेकिन किसी कारण से सबसे स्पष्ट बात नहीं है। धन्यवाद। – checker
+1। बहुत अच्छी साइट। –
यह वास्तव में Google पर वास्तव में पहला परिणाम है :) –
शायद आप अपना खुद का टेस्ट डेटा जेनरेट कर सकते हैं?
यह निश्चित रूप से व्यापक परीक्षण नहीं होगा, लेकिन इससे मदद मिल सकती है। नोट: नीचे हैमिल्टनियन पथ के बारे में है, और यदि आप चक्र की तलाश में हैं, तो कुछ ऐसा ही काम करेगा।
आप निम्न कर सकते हैं:
कहो तुम n नोड्स के साथ एक अनिर्दिष्ट ग्राफ जी दिया जाता है।
अब आप जी में 1 के किनारों के वजन को सेट करके और जी में नहीं किनारों को जोड़कर, और उन्हें यादृच्छिक वजन> 1, यानी जी 'के साथ एक पूर्ण ग्राफ है, जिसमें आप एक भारित ग्राफ जी बनाते हैं। वजन अपने सभी किनारों को सौंपा गया।
अब यदि आप जी पर एक वैध टीएसपी एल्गोरिदम चलाते हैं और यह आकार n-1 का पथ उत्पन्न करता है, तो जी में हैमिल्टनियन पथ होता है। अन्यथा जी में हैमिल्टनियन पथ नहीं है।
तो अब आप रेखांकन का उपयोग कर सकते जैसा कि आप जानते है/Hamiltonian पथ की जरूरत नहीं है (उदाहरण के लिए: Hypercube Hamiltonian पथ है) और अपने TSP एल्गोरिथ्म के लिए परीक्षण डेटा उत्पन्न करते हैं। http://www-math.cudenver.edu/~wcherowi/courses/m4408/gtln12.html
मुझे लगता है कि आप एक कठिन समय Hamiltonian पथ के बिना साथ/रेखांकन पर डेटा खोजने के लिए नहीं होगा:
इस पृष्ठ में कुछ पर्याप्त परिस्थितियों के रेखांकन जो Hamiltonian पथ है पैदा करने में उपयोगी साबित हो सकता है।
उम्मीद है कि यह मदद करता है। सौभाग्य!
टीएसपीआईएलबी विभिन्न स्रोतों और विभिन्न प्रकारों से टीएसपी (और संबंधित समस्याओं) के लिए नमूना उदाहरणों की एक पुस्तकालय है।
वहाँ हमेशा ईबे, जो जाहिरा तौर पर हे (1) है पर बेच रहा है। :-P http://xkcd.com/399/ –