Traveling Salesman Problem in Hindi | ट्रैवलिंग सेल्समैन समस्या क्या है?


ट्रैवलिंग सेल्समैन समस्या क्या है? (Traveling Salesman Problem in Hindi)

ट्रैवलिंग सेल्समैन समस्या (TSP) एक क्लासिकल ऑप्टिमाइज़ेशन समस्या है, जिसमें एक सेल्समैन को कई शहरों की यात्रा करनी होती है और अंत में उसे वापस अपने प्रारंभिक शहर में लौटना होता है। लक्ष्य यह है कि सभी शहरों को केवल एक बार विजिट करते हुए न्यूनतम दूरी (Shortest Path) तय की जाए।

ट्रैवलिंग सेल्समैन समस्या के नियम (Rules of TSP)

  • सेल्समैन को हर शहर में केवल एक बार जाना होगा।
  • यात्रा को न्यूनतम लागत (Minimum Cost) या न्यूनतम दूरी (Minimum Distance) में पूरा करना होगा।
  • यात्रा का समापन उसी प्रारंभिक शहर पर होना चाहिए जहाँ से यात्रा शुरू हुई थी।

ट्रैवलिंग सेल्समैन समस्या को हल करने के एल्गोरिदम (Algorithms to Solve TSP)

एल्गोरिदम विवरण समय जटिलता
ब्रूट फोर्स (Brute Force) सभी संभावित मार्गों को जाँचता है और न्यूनतम दूरी वाला मार्ग चुनता है। O(N!)
डायनामिक प्रोग्रामिंग (Held-Karp Algorithm) मेमोइज़ेशन तकनीक का उपयोग करके समाधान खोजता है। O(N² × 2^N)
ब्रांच एंड बाउंड (Branch and Bound) बेहतर समाधान खोजने के लिए बाउंडिंग तकनीक का उपयोग करता है। O(N²)
ग्रीडी एल्गोरिदम (Greedy Algorithm) हर स्टेप पर सबसे छोटा उपलब्ध मार्ग चुनता है। O(N²)
जेनेटिक एल्गोरिदम (Genetic Algorithm) विकासवादी दृष्टिकोण (Evolutionary Approach) का उपयोग करता है। O(k × N²)

ट्रैवलिंग सेल्समैन समस्या का छद्मकोड (Pseudocode of TSP)

function TSP(graph, current, visited)
    if all cities visited:
        return distance to start city
    min_cost = ∞
    for each unvisited city:
        cost = distance[current][city] + TSP(graph, city, visited + city)
        min_cost = min(min_cost, cost)
    return min_cost

ट्रैवलिंग सेल्समैन समस्या का उदाहरण (Example of TSP)

मान लीजिए कि हमारे पास निम्नलिखित चार शहरों का एक ग्राफ है:

शहर A B C D
A 0 10 15 20
B 10 0 35 25
C 15 35 0 30
D 20 25 30 0

संभावित न्यूनतम मार्ग: A → B → D → C → A

इस मार्ग की कुल दूरी = 10 + 25 + 30 + 15 = 80

ट्रैवलिंग सेल्समैन समस्या बनाम हैमिल्टोनियन साइकिल (TSP vs Hamiltonian Cycle)

विशेषता ट्रैवलिंग सेल्समैन समस्या हैमिल्टोनियन साइकिल
लक्ष्य न्यूनतम लागत वाला मार्ग खोजना सभी वर्टिस को एक बार विजिट करना
समय जटिलता O(N!) NP-Complete
अनुप्रयोग लॉजिस्टिक्स, नेटवर्किंग, ऑप्टिमाइज़ेशन ग्राफ थ्योरी, कंप्यूटर नेटवर्क्स

ट्रैवलिंग सेल्समैन समस्या के अनुप्रयोग (Applications of TSP)

  • लॉजिस्टिक्स और सप्लाई चेन ऑप्टिमाइज़ेशन (Logistics & Supply Chain Optimization)
  • रोबोटिक्स और पाथ प्लानिंग (Robotics & Path Planning)
  • सर्किट डिज़ाइन (VLSI Circuit Design)
  • डीएनए सीक्वेंसिंग (DNA Sequencing)
  • नेटवर्क रूटिंग (Network Routing)

ट्रैवलिंग सेल्समैन समस्या की समय जटिलता (Time Complexity of TSP)

  • ब्रूट फोर्स: O(N!)
  • डायनामिक प्रोग्रामिंग: O(N² × 2^N)
  • ग्रेसी एल्गोरिदम: O(N²)

निष्कर्ष

ट्रैवलिंग सेल्समैन समस्या एक महत्वपूर्ण कॉम्बिनेटोरियल ऑप्टिमाइज़ेशन समस्या है, जिसका उपयोग नेटवर्किंग, लॉजिस्टिक्स, और सर्किट डिज़ाइन में किया जाता है। इसे विभिन्न एल्गोरिदम जैसे कि डायनामिक प्रोग्रामिंग, ब्रांच एंड बाउंड और ग्रीडी एल्गोरिदम के माध्यम से हल किया जाता है।

Related Post

Comments

Comments