टीएसपी (Travelling Salesman Problem) क्या है? (What is Travelling Salesman Problem?)

Travelling Salesman Problem (TSP) एक प्रसिद्ध संयोजी अनुकूलन समस्या (Combinatorial Optimization Problem) है, जिसमें एक विक्रेता (Salesman) को **कई शहरों की यात्रा करनी होती है और उसे सबसे छोटा मार्ग ढूँढना होता है**, ताकि वह सभी शहरों का दौरा करके **अपने प्रारंभिक शहर पर लौट सके।**

टीएसपी की समस्या का विवरण

टीएसपी को एक ग्राफ़ G = (V, E) द्वारा दर्शाया जाता है, जहाँ:

• V: सभी शहरों (Nodes) का सेट
• E: शहरों के बीच के मार्ग (Edges)
• C(i, j): शहर i से शहर j तक जाने की लागत (Cost)

टीएसपी का उद्देश्य **कुल यात्रा लागत (Total Travel Cost) को न्यूनतम करना** है।

टीएसपी का गणितीय मॉडल

टीएसपी को निम्नलिखित समीकरण द्वारा व्यक्त किया जा सकता है:

लक्ष्य फ़ंक्शन (Objective Function):

Minimize Σ C(i, j) * X(i, j)

शर्तें (Constraints):

• प्रत्येक शहर i में एक बार ही जाना चाहिए।
• यात्रा एक सर्कुलर पथ में होनी चाहिए।
• कुल लागत न्यूनतम होनी चाहिए।

टीएसपी के प्रकार

1. सिमेट्रिक टीएसपी (Symmetric TSP)

• यदि C(i, j) = C(j, i), तो टीएसपी **सिमेट्रिक** होता है।
• यानी, किसी दो शहरों के बीच यात्रा की लागत समान होती है।

2. असीमेट्रिक टीएसपी (Asymmetric TSP)

• यदि C(i, j) ≠ C(j, i), तो टीएसपी **असीमेट्रिक** होता है।
• यानी, शहरों के बीच यात्रा की लागत भिन्न हो सकती है (जैसे, वन-वे ट्रैफिक)।

टीएसपी को हल करने की विधियाँ (Methods to Solve TSP)

1. ब्रूट फोर्स विधि (Brute Force Method)

• सभी संभावित मार्गों (n!) को जाँचकर सबसे छोटा मार्ग चुना जाता है।
• **समस्या:** यह विधि **बहुत धीमी** है और बड़े इनपुट के लिए अप्रभावी होती है।

2. डायनेमिक प्रोग्रामिंग (Dynamic Programming - Held-Karp Algorithm)

• यह **Bellman-Held-Karp एल्गोरिदम** पर आधारित है और समय जटिलता O(n² * 2^n) होती है।
• यह ब्रूट फोर्स से तेज़ है लेकिन अभी भी बड़े इनपुट के लिए धीमी है।

3. ग्रीडी एल्गोरिदम (Greedy Algorithm - Nearest Neighbor Method)

• हमेशा **सबसे नज़दीकी शहर** का चयन करता है और यात्रा जारी रखता है।
• तेज़ होता है लेकिन **सर्वश्रेष्ठ समाधान की गारंटी नहीं देता**।

4. ब्रांच एंड बाउंड (Branch and Bound)

• यह **सभी संभावित मार्गों का आकलन करता है** और अनावश्यक मार्गों को हटा देता है।
• बड़े डेटा के लिए धीमा हो सकता है।

5. जेनेटिक एल्गोरिदम (Genetic Algorithm - GA)

• यह **इवोल्यूशनरी एल्गोरिदम** का उपयोग करता है, जिसमें **चयन (Selection), क्रॉसओवर (Crossover), और म्यूटेशन (Mutation)** शामिल होते हैं।
• यह बड़े डेटा के लिए अधिक उपयुक्त है।

6. एंट कोलॉनी ऑप्टिमाइज़ेशन (Ant Colony Optimization - ACO)

• यह **चींटियों के व्यवहार** पर आधारित एल्गोरिदम है।
• चींटियाँ सबसे छोटा मार्ग खोजने के लिए फेरोमोन का उपयोग करती हैं।

7. न्यूरल नेटवर्क आधारित हल (Neural Network-based Solutions)

• **हॉपफील्ड न्यूरल नेटवर्क (Hopfield Neural Network - HNN)** का उपयोग टीएसपी समाधान के लिए किया जाता है।

टीएसपी के अनुप्रयोग (Applications of TSP)

• लॉजिस्टिक्स और सप्लाई चेन: उत्पादों की डिलीवरी के लिए सबसे छोटा मार्ग ढूँढना।
• रोबोटिक्स: रोबोट द्वारा सबसे कुशल मार्ग अपनाने के लिए।
• नेटवर्क डिज़ाइन: टेलीफोन और इंटरनेट नेटवर्क को ऑप्टिमाइज़ करना।
• जीवन विज्ञान: डीएनए अनुक्रमण (DNA Sequencing) में मार्ग अनुकूलन।
• स्मार्ट सिटीज: ट्रैफिक कंट्रोल और शहरों के लिए कुशल मार्ग योजना।

टीएसपी की जटिलता (Complexity of TSP)

• TSP एक **NP-Hard समस्या** है, जिसका अर्थ है कि इसे **Polynomial Time** में हल करना मुश्किल है।
• इसका सटीक समाधान केवल छोटे इनपुट के लिए संभव होता है।
• बड़े इनपुट के लिए **ह्यूरिस्टिक और एप्रीक्सिमेशन एल्गोरिदम** का उपयोग किया जाता है।

निष्कर्ष

Travelling Salesman Problem (TSP) एक **जटिल संयोजी समस्या** है, जिसका उपयोग **लॉजिस्टिक्स, रोबोटिक्स, नेटवर्क डिज़ाइन, और AI** में किया जाता है। इसे हल करने के लिए **डायनेमिक प्रोग्रामिंग, जेनेटिक एल्गोरिदम, एंट कोलॉनी ऑप्टिमाइज़ेशन और न्यूरल नेटवर्क** जैसी तकनीकों का उपयोग किया जाता है।