यात्रा बिंदु पर वापस जाने पर विचार किए बिना यात्रा विक्रेता समस्या (टीएसपी) के लिए समस्या का नाम क्या है?

Question

मैं जानना चाहता हूं कि शुरुआती बिंदु पर वापस जाने के तरीके पर विचार करने के लिए टीएसपी w/o के लिए समस्या का नाम क्या है और इसे हल करने के लिए एल्गोरिदम क्या है।

मैंने सबसे छोटी पथ समस्या में देखा लेकिन यह वह नहीं है जिसे मैं ढूंढ रहा हूं, समस्या केवल 2 निर्दिष्ट बिंदुओं से सबसे कम पथ पाती है। लेकिन जो मैं खोज रहा हूं वह वह समस्या है जिसे हम एन अंक देते हैं और केवल 1 प्रारंभिक बिंदु इनपुट करते हैं। फिर, एक बार सभी बिंदुओं पर यात्रा करने का सबसे छोटा रास्ता पाएं। (अंत बिंदु कोई बिंदु हो सकता है।)

मैंने हैमिल्टनियन पथ की समस्या में भी देखा लेकिन ऐसा लगता है कि मेरी परिभाषित समस्या को हल नहीं करना है बल्कि यह पता लगाएं कि हैमिल्टनियन पथ है या नहीं।

कृपया मुझे सुझाव दें, धन्यवाद!

Answer 1

मुझे this book में मेरे प्रश्न का उत्तर मिला है। यह कम्प्यूटर तारों की समस्या के साथ समान है जो कंप्यूटर और अन्य डिजिटल सिस्टम के डिजाइन में बार-बार होता है। उद्देश्य कुल तार लंबाई को कम करना है। तो, यह वास्तव में न्यूनतम लंबाई हैमिल्टनियन पथ है।

पुस्तक का सुझाव है कि एक डमी प्वाइंट बनाने के लिए जिसका हर दूसरे बिंदुओं की दूरी 0 है। इसलिए, समस्या एक (एन + 1) -सिटी सममित टीएसपी बन जाती है। हल करने के बाद, बस डमी पॉइंट हटाएं और फिर न्यूनतम लंबाई हैमिल्टनियन पथ हल हो गया है और हम प्रारंभ बिंदु को वापस किए बिना टीएसपी पथ प्राप्त कर सकते हैं।

Answer 2

यदि मैं सही ढंग से समझता हूं, तो आप सबसे छोटा रास्ता (जो कुछ चरम से शुरू होता है) खोजना चाहते हैं और ग्राफ में सभी नोड्स को दो बार एक ही नोड पर जाकर बिना चला जाता है। एक आसान समस्या हैमिल्टनियन पथ समस्या है। यह पूछता है, जैसा कि आपने कहा था, मौसम ऐसे पथ मौजूद है या नहीं। चूंकि यह समस्या एनपी-हार्ड है, और यह आपकी समस्या से आसान है, आपकी समस्या को हल करना कम से कम एनपी-हार्ड है। खैर, यह सच नहीं है क्योंकि आपकी समस्या निर्णय समस्या नहीं है। लेकिन यह क्या कहता है कि हम लगभग सुनिश्चित कर सकते हैं कि आपकी समस्या के लिए कोई बहुपद एल्गोरिदम नहीं है।

आप अनुमान लगा सकते हैं। मेट्रिक टीएसपी के लिए यहां एक बहुत अच्छा अनुमान है: http://en.wikipedia.org/wiki/Travelling_salesman_problem#Metric_TSP।