DIZNR INTERNATIONAL

Traveling Salesman Problem In Hindi Using Dynamic Programming With Practical Example

Ali Seron Jason Ali Seron Jason

Traveling Salesman Problem In Hindi Using Dynamic Programming With Practical Example

https://www.gyanodhan.com/video/7B1.%20GATE%20CSEIT/Algorith%20Analysis%20and%20Design/615.%20AAD-%20Traveling%20Salesman%20Problem%20In%20Hindi%20%20%20Using%20Dynamic%20Programming%20%20%20With%20Practical%20Example%2045%20HD.mp4

यहाँ Traveling Salesman Problem (TSP) को Dynamic Programming द्वारा हल करने की हिंदी में विस्तृत व्याख्या दी गई है, जिसमें एक प्रैक्टिकल उदाहरण भी शामिल है:

Traveling Salesman Problem (TSP) क्या है?

Traveling Salesman Problem (TSP) एक क्लासिकल कंप्यूटर साइंस और ऑप्टिमाइजेशन की समस्या है जिसमें एक सेल्समैन को कई शहरों का दौरा करना होता है। उसे:

  1. हर शहर में एक बार जाना है।

  2. अंत में शुरुआती शहर पर वापस आना है।

  3. कुल दूरी/लागत न्यूनतम होनी चाहिए।

Dynamic Programming द्वारा TSP को हल करना (Held-Karp Algorithm)

Dynamic Programming TSP को O(n² * 2ⁿ) समय में हल करता है, जहाँ n शहरों की संख्या है।

हम एक स्टेट (mask, i) रखते हैं:

DP Formula:

bash
dp[mask][i] = min(dp[mask ^ (1 << i)][j] + cost[j][i])

जहाँ 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 बनाते हैं:

python
from functools import lru_cache

# दूरी मैट्रिक्स
cost = [
[0, 10, 15, 20],
[10, 0, 35, 25],
[15, 35, 0, 30],
[20, 25, 30, 0]
]

N = 4 # शहरों की संख्या
ALL_VISITED = (1 << N) - 1 # सभी शहर विजिट किए गए (1111 in binary)

@lru_cache(None)
def tsp(mask, pos):
if mask == ALL_VISITED:
return cost[pos][0] # वापस A पर लौटें

ans = float('inf')
for city in range(N):
if (mask & (1 << city)) == 0:
newAns = cost[pos][city] + tsp(mask | (1 << city), city)
ans = min(ans, newAns)
return ans

# शुरूआत A (0) से
print("Minimum cost:", tsp(1, 0))

Output:

yaml
Minimum cost: 80

समझने के लिए सरल भाषा में व्याख्या:

निष्कर्ष:

अगर आप चाहें, तो मैं इसका पायथन कोड का विजुअलाइजेशन, C++ संस्करण, या ग्राफिकल उदाहरण भी तैयार कर सकता हूँ।