Traveling Salesman Problem In Hindi Using Dynamic Programming With Practical Example
Traveling Salesman Problem In Hindi Using Dynamic Programming With Practical Example
यहाँ Traveling Salesman Problem (TSP) को Dynamic Programming द्वारा हल करने की हिंदी में विस्तृत व्याख्या दी गई है, जिसमें एक प्रैक्टिकल उदाहरण भी शामिल है:
Contents [hide]
Traveling Salesman Problem (TSP) क्या है?
Traveling Salesman Problem (TSP) एक क्लासिकल कंप्यूटर साइंस और ऑप्टिमाइजेशन की समस्या है जिसमें एक सेल्समैन को कई शहरों का दौरा करना होता है। उसे:
-
हर शहर में एक बार जाना है।
-
अंत में शुरुआती शहर पर वापस आना है।
-
कुल दूरी/लागत न्यूनतम होनी चाहिए।
Dynamic Programming द्वारा TSP को हल करना (Held-Karp Algorithm)
Dynamic Programming TSP को O(n² * 2ⁿ) समय में हल करता है, जहाँ n शहरों की संख्या है।
हम एक स्टेट (mask, i) रखते हैं:
-
mask: बाइनरी रिप्रेजेंटेशन बताता है कि कौन-कौन से शहर विज़िट किए जा चुके हैं।
-
i: वर्तमान शहर।
DP Formula:
जहाँ j हर वो शहर है जो mask में पहले से विज़िट किया गया है।
उदाहरण (Practical Example)
मान लीजिए 4 शहर हैं: A, B, C, D
हम उन्हें 0, 1, 2, 3 के रूप में मानते हैं।
Distance Matrix (Cost Table):
| A(0) | B(1) | C(2) | D(3) | |
|---|---|---|---|---|
| A | 0 | 10 | 15 | 20 |
| B | 10 | 0 | 35 | 25 |
| C | 15 | 35 | 0 | 30 |
| D | 20 | 25 | 30 | 0 |
हमें शहर A से शुरू होकर सभी शहरों में जाकर फिर से A लौटना है, और कुल दूरी न्यूनतम होनी चाहिए।
स्टेप-बाय-स्टेप हल (Using DP)
हम एक DP table बनाते हैं:
Output:
समझने के लिए सरल भाषा में व्याख्या:
-
हमने शहर A से शुरुआत की।
-
हर बार एक नया शहर चुनते हैं जो अभी तक विजिट नहीं हुआ।
-
फिर रिकर्सिव तरीके से बाकी शहरों का सबसे छोटा रास्ता ढूंढते हैं।
-
अंत में, सभी शहर विजिट हो जाएँ तो वापस A पर लौटते हैं।
निष्कर्ष:
-
TSP एक कठिन समस्या है लेकिन Dynamic Programming (Held-Karp) द्वारा छोटा इनपुट होने पर इसे कुशलतापूर्वक हल किया जा सकता है।
-
यह रूट ऑप्टिमाइजेशन, लॉजिस्टिक्स, और डिलीवरी सिस्टम में बहुत उपयोगी है।
अगर आप चाहें, तो मैं इसका पायथन कोड का विजुअलाइजेशन, C++ संस्करण, या ग्राफिकल उदाहरण भी तैयार कर सकता हूँ।