घुमंतू सेल्समैन समस्या: Python, C++ कलन विधि

ट्रैवलिंग सेल्समैन समस्या (टीएसपी) क्या है?

ट्रैवलिंग सेल्समैन समस्या (TSP) सैद्धांतिक कंप्यूटर विज्ञान की एक क्लासिक कॉम्बिनेटरिक्स समस्या है। इस समस्या में ग्राफ में सबसे छोटा रास्ता खोजने के लिए कहा जाता है, जिसमें सभी नोड्स पर केवल एक बार जाने और मूल शहर में वापस लौटने की शर्त होती है।

समस्या विवरण में शहरों की सूची तथा प्रत्येक शहर के बीच की दूरी दी गई है।

उद्देश्य: मूल शहर से शुरू करने के लिए, अन्य शहरों में केवल एक बार जाएँ, और फिर मूल शहर में वापस आएँ। हमारा लक्ष्य राउंड-ट्रिप मार्ग को पूरा करने के लिए सबसे छोटा संभव रास्ता खोजना है।

टीएसपी का उदाहरण

यहां एक ग्राफ दिया गया है जहां 1, 2, 3 और 4 शहरों को दर्शाते हैं, और प्रत्येक किनारे से जुड़ा भार उन शहरों के बीच की दूरी को दर्शाता है।

लक्ष्य यात्रा के लिए सबसे छोटा संभव मार्ग ढूंढना है जो मूल शहर से शुरू हो, ग्राफ को पार करते हुए अन्य शहरों या नोड्स पर केवल एक बार जाए, तथा मूल शहर में वापस आ जाए।

उपरोक्त ग्राफ के लिए, इष्टतम मार्ग न्यूनतम लागत पथ का अनुसरण करना है: 1-2-4-3-1. और इस सबसे छोटे मार्ग की लागत 10+25+30+15 =80 होगी

ट्रैवलिंग सेल्समैन समस्या के विभिन्न समाधान

ट्रैवलिंग सेल्समैन समस्या (TSP) को NP-हार्ड समस्या के रूप में वर्गीकृत किया गया है क्योंकि इसमें कोई बहुपद समय एल्गोरिथ्म नहीं है। शहरों की संख्या बढ़ने से जटिलता तेजी से बढ़ती है।

ट्रैवलिंग सेल्समैन समस्या (टीएसपी) को हल करने के कई तरीके हैं। कुछ लोकप्रिय समाधान इस प्रकार हैं:

बल प्रयोग का तरीका भोला-भाला तरीका है ट्रैवलिंग सेल्समैन समस्याओं को हल करने के लिए। इस दृष्टिकोण में, हम पहले सभी संभावित पथों की गणना करते हैं और फिर उनकी तुलना करते हैं। n शहरों से युक्त ग्राफ में पथों की संख्या है n! इस बलपूर्वक पद्धति में ट्रैवलिंग सेल्समैन समस्या का समाधान करना कम्प्यूटेशनल दृष्टि से बहुत महंगा है।

शाखा-और-बाध्य विधि: इस दृष्टिकोण में समस्या को उप-समस्याओं में विभाजित किया जाता है। उन व्यक्तिगत उप-समस्याओं का समाधान एक इष्टतम समाधान प्रदान करेगा।

यह ट्यूटोरियल ट्रैवलिंग सेल्समैन समस्या को हल करने के लिए एक गतिशील प्रोग्रामिंग दृष्टिकोण, इस शाखा-और-सीमा विधि के पुनरावर्ती संस्करण को प्रदर्शित करेगा।

गतिशील प्रोग्रामिंग सभी संभावित मार्गों का विश्लेषण करके इष्टतम समाधान खोजने की एक ऐसी विधि है। यह सटीक समाधान विधियों में से एक है जो यात्रा करने वाले सेल्समैन की समस्याओं को अपेक्षाकृत अधिक लागत के माध्यम से हल करती है लालची तरीके जो लगभग इष्टतम समाधान प्रदान करते हैं।

इस दृष्टिकोण की गणनात्मक जटिलता है ओ(एन^2 * 2^एन) जिसकी चर्चा इस लेख में आगे की गई है।

निकटतम पड़ोसी विधि यह एक अनुमान-आधारित लालची दृष्टिकोण है जहाँ हम निकटतम पड़ोसी नोड चुनते हैं। यह दृष्टिकोण गतिशील दृष्टिकोण की तुलना में कम्प्यूटेशनल रूप से कम खर्चीला है। लेकिन यह इष्टतम समाधान की गारंटी नहीं देता है। इस पद्धति का उपयोग निकट-इष्टतम समाधानों के लिए किया जाता है।

ट्रैवलिंग सेल्समैन समस्या के लिए एल्गोरिदम

हम ट्रैवलिंग सेल्समैन समस्या (टीएसपी) को हल करने के लिए डायनेमिक प्रोग्रामिंग दृष्टिकोण का उपयोग करेंगे।

एल्गोरिथ्म शुरू करने से पहले, आइए कुछ शब्दावलियों से परिचित हो जाएं:

एक ग्राफ G=(V, E), जो शीर्षों और किनारों का एक समूह है।
V शीर्षों का समूह है।
E किनारों का समूह है।
शीर्षों को किनारों के माध्यम से जोड़ा जाता है।
Dist(i,j) दो शीर्षों i और j के बीच की गैर-ऋणात्मक दूरी को दर्शाता है।

मान लें कि S शहरों का उपसमूह है और {1, 2, 3, …, n} से संबंधित है, जहाँ 1, 2, 3…n शहर हैं और i, j उस उपसमूह में दो शहर हैं। अब लागत (i, S, j) को इस तरह से परिभाषित किया जाता है कि S में नोड पर जाने वाले सबसे छोटे रास्ते की लंबाई, जो कि एक बार क्रमशः i और j के रूप में आरंभिक और अंतिम बिंदु है।

उदाहरण के लिए, लागत (1, {2, 3, 4}, 1) सबसे छोटे रास्ते की लंबाई को दर्शाती है जहाँ:

प्रारंभिक शहर 1 है
शहर 2, 3 और 4 का दौरा केवल एक बार किया जाता है
अंतिम बिंदु 1 है

गतिशील प्रोग्रामिंग एल्गोरिथ्म होगा:

लागत (i, , i) = 0 निर्धारित करें, जिसका अर्थ है कि हम i से शुरू और समाप्त करते हैं, तथा लागत 0 है।
जब |S| > 1, तो हम cost(i, S, 1) = ∝ परिभाषित करते हैं जहाँ i !=1 है। क्योंकि शुरू में, हमें अन्य शहरों से होते हुए शहर i से शहर 1 तक पहुँचने की सटीक लागत का पता नहीं होता है।
अब हमें 1 से शुरू करके टूर पूरा करना है। हमें अगला शहर इस तरह से चुनना है-

लागत(i, S, j)=न्यूनतम लागत (i, S−{i}, j)+dist(i,j) जहाँ i∈S और i≠j

दी गई आकृति के लिए, आसन्नता मैट्रिक्स निम्नलिखित होगा:

डिस्ट(i,j)	1	2	3	4
1	0	10	15	20
2	10	0	35	25
3	15	35	0	30
4	20	25	30	0

आइये देखें कि हमारा एल्गोरिदम कैसे काम करता है:

चरण 1) हम अपनी यात्रा शहर 1 से शुरू करने, अन्य शहरों का एक बार दौरा करने और शहर 1 पर वापस लौटने पर विचार कर रहे हैं।

चरण 2) S शहरों का उपसमूह है। हमारे एल्गोरिथ्म के अनुसार, सभी |S| > 1 के लिए, हम दूरी लागत (i, S, 1) = ∝ निर्धारित करेंगे। यहाँ लागत (i, S, j) का अर्थ है कि हम शहर i से शुरू कर रहे हैं, एक बार S के शहरों का दौरा कर रहे हैं, और अब हम शहर j पर हैं। हमने इस पथ लागत को अनंत के रूप में सेट किया है क्योंकि हमें अभी तक दूरी का पता नहीं है। इसलिए मान निम्नलिखित होंगे:

लागत (2, {3, 4}, 1) = ∝; यह संकेत दर्शाता है कि हम शहर 2 से शुरू कर रहे हैं, शहर 3, 4 से गुज़र रहे हैं, और 1 पर पहुँच रहे हैं। और पथ लागत अनंत है। इसी तरह-

लागत(3, {2, 4}, 1) = ∝

लागत(4, {2, 3}, 1) = ∝

चरण 3) अब, S के सभी उपसमुच्चयों के लिए, हमें निम्नलिखित ज्ञात करना होगा:

लागत(i, S, j)=न्यूनतम लागत (i, S−{i}, j)+dist(i,j), जहाँ j∈S और i≠j

इसका मतलब है कि i से शुरू होकर, एक बार शहरों के सबसेट से गुज़रने और शहर j पर वापस लौटने के लिए न्यूनतम लागत पथ। यह मानते हुए कि यात्रा शहर 1 से शुरू होती है, इष्टतम पथ लागत = लागत (1, {अन्य शहर}, 1) होगी।

आइये जानें कि हम इसे कैसे हासिल कर सकते हैं:

अब S = {1, 2, 3, 4}. यहाँ चार तत्व हैं. इसलिए उपसमुच्चयों की संख्या 2^4 या 16 होगी. वे उपसमुच्चय हैं-

1) |S| = शून्य:

{Φ}

2) |एस| = 1:

{{1}, {2}, {3}, {4}}

3) |एस| = 2:

{{1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {3, 4}}

4) |एस| = 3:

{{1, 2, 3}, {1, 2, 4}, {2, 3, 4}, {1, 3, 4}}

5) |एस| = 4:

चूंकि हम 1 से शुरू कर रहे हैं, इसलिए हम शहर 1 वाले उपसमुच्चयों को त्याग सकते हैं।

एल्गोरिथ्म गणना:

१) |एस| = Φ:

लागत (2, Φ, 1) = दूरी (2, 1) = 10

लागत (3, Φ, 1) = दूरी (3, 1) = 15

लागत (4, Φ, 1) = दूरी (4, 1) = 20

2) |एस| = 1:

लागत (2, {3}, 1) = dist(2, 3) + लागत (3, Φ, 1) = 35+15 = 50

लागत (2, {4}, 1) = dist(2, 4) + लागत (4, Φ, 1) = 25+20 = 45

लागत (3, {2}, 1) = dist(3, 2) + लागत (2, Φ, 1) = 35+10 = 45

लागत (3, {4}, 1) = dist(3, 4) + लागत (4, Φ, 1) = 30+20 = 50

लागत (4, {2}, 1) = dist(4, 2) + लागत (2, Φ, 1) = 25+10 = 35

लागत (4, {3}, 1) = dist(4, 3) + लागत (3, Φ, 1) = 30+15 = 45

3) |एस| = 2:

लागत (2, {3, 4}, 1) = न्यूनतम [दूरी[2,3]+लागत(3,{4},1) = 35+50 = 85,

dist[2,4]+Cost(4,{3},1) = 25+45 = 70 ] = 70

लागत (3, {2, 4}, 1) = न्यूनतम [दूरी[3,2]+लागत(2,{4},1) = 35+45 = 80,

dist[3,4]+Cost(4,{2},1) = 30+35 = 65 ] = 65

लागत (4, {2, 3}, 1) = न्यूनतम [दूरी[4,2]+लागत(2,{3},1) = 25+50 = 75

dist[4,3]+Cost(3,{2},1) = 30+45 = 75 ] = 75

4) |एस| = 3:

लागत (1, {2, 3, 4}, 1) = न्यूनतम [दूरी[1,2]+लागत(2,{3,4},1) = 10+70 = 80

dist[1,3]+Cost(3,{2,4},1) = 15+65 = 80

dist[1,4]+Cost(4,{2,3},1) = 20+75 = 95 ] = 80

तो इष्टतम समाधान होगा 1-2-4-3-1

छद्म कोड

Algorithm: Traveling-Salesman-Problem 
Cost (1, {}, 1) = 0 
for s = 2 to n do 
   for all subsets S belongs to {1, 2, 3, … , n} of size s 
      Cost (s, S, 1) = Infinity
   for all i Є S and i ≠ 1 
      Cost (i, S, j) = min {Cost (i, S – {i}, j) + dist(i, j) for j Є S and i ≠ j} 
Return min(i) Cost (i, {1, 2, 3, …, n}, j) + d(j, i)

सी/ में कार्यान्वयनC++

इसका कार्यान्वयन इस प्रकार है C++:

#include <bits/stdc++.h>
using namespace std;
#define V 4
#define MAX 1000000
int tsp(int graph[][V], int s)
{
    vector<int> vertex;
    for (int i = 0; i < V; i++)
        if (i != s)
            vertex.push_back(i);
    int min_cost = MAX;
    while(next_permutation(vertex.begin(), vertex.end()))
     {
        int current_cost = 0;
        int j = s;
        for (int i = 0; i < vertex.size(); i++) {
            current_cost += graph[j][vertex[i]];
            j = vertex[i];
        }
        current_cost += graph[j][s];
        min_cost = min(min_cost, current_cost);
        return min_cost;
	}
}
int main()
{
    int graph[][V] = { { 0, 10, 15, 20 },{ 10, 0, 35, 25 },{ 15, 35, 0, 30 },{ 20, 25, 30, 0 } };                      
    int s = 0;
    cout << tsp(graph, s) << endl;
    return 0;
}

आउटपुट:

कार्यान्वयन Python

from sys import maxsize
from itertools, import permutations
V = 4
def tsp(graph, s):
	vertex = []
	for i in range(V):
		if i != s:
			vertex.append(i)
    min_cost = maxsize
	next_permutation=permutations(vertex)
	for i in next_permutation:
		current_cost = 0
		k = s
		for j in i:
			current_cost += graph[k][j]
			k = j
		current_cost += graph[k][s]
		min_cost = min(min_cost, current_cost)
		return min_cost
graph = [[0, 10, 15, 20], [10, 0, 35, 25], [15, 35, 0, 30], [20, 25, 30, 0]]
		s = 0
print(tsp(graph, s))

आउटपुट:

टीएसपी के लिए शैक्षणिक समाधान

कंप्यूटर वैज्ञानिकों ने ट्रैवलिंग सेल्समैन समस्या के लिए एक बेहतर बहुपद समय एल्गोरिथ्म की खोज में वर्षों बिताए हैं। अब तक, यह समस्या अभी भी NP-कठिन है।

यद्यपि हाल के वर्षों में निम्नलिखित कुछ समाधान प्रकाशित हुए हैं जिनसे जटिलता कुछ हद तक कम हो गई है:

शास्त्रीय सममित टीएसपी को शून्य प्रत्यय विधि द्वारा हल किया जाता है।
बायोजियोग्राफी-आधारित अनुकूलन एल्गोरिथ्म अनुकूलन समस्याओं को हल करने के लिए माइग्रेशन रणनीति पर आधारित है जिसे टीएसपी के रूप में योजनाबद्ध किया जा सकता है।
बहुउद्देश्यीय विकासवादी एल्गोरिथ्म को NSGA-II पर आधारित कई TSP को हल करने के लिए डिज़ाइन किया गया है।
मल्टी-एजेंट सिस्टम निश्चित संसाधनों वाले N शहरों की TSP समस्या का समाधान करता है।

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

ट्रैवलिंग सेल्समैन समस्या (TSP) को वास्तविक दुनिया में इसके शुद्धतम और संशोधित दोनों रूपों में लागू किया जाता है। उनमें से कुछ इस प्रकार हैं:

योजना, रसद और माइक्रोचिप्स का निर्माणमाइक्रोचिप उद्योग में चिप डालने की समस्याएँ स्वाभाविक रूप से उत्पन्न होती हैं। उन समस्याओं को ट्रैवलिंग सेल्समैन की समस्याओं के रूप में योजनाबद्ध किया जा सकता है।
डीएनए श्रृंखला बनाना: ट्रैवलिंग सेल्समैन समस्या का थोड़ा सा संशोधन डीएनए अनुक्रमण में इस्तेमाल किया जा सकता है। यहाँ, शहर डीएनए टुकड़ों का प्रतिनिधित्व करते हैं, और दूरी दो डीएनए टुकड़ों के बीच समानता माप का प्रतिनिधित्व करती है।
खगोलट्रैवलिंग सेल्समैन समस्या का प्रयोग खगोलविदों द्वारा विभिन्न स्रोतों के अवलोकन में लगने वाले समय को कम करने के लिए किया जाता है।
इष्टतम नियंत्रण समस्या: ट्रैवलिंग सेल्समैन समस्या निर्माण को इष्टतम नियंत्रण समस्याओं में लागू किया जा सकता है। इसमें कई अन्य बाधाएँ भी जोड़ी जा सकती हैं।

टीएसपी का जटिलता विश्लेषण

समय जटिलता: कुल 2 हैं^Nप्रत्येक नोड के लिए उपसमस्याएँ। इसलिए उपसमस्याओं की कुल संख्या N*2 होगी^Nप्रत्येक उप-समस्या को हल करने के लिए रैखिक समय की आवश्यकता होती है। यदि मूल नोड निर्दिष्ट नहीं है, तो हमें N नोड्स के लिए लूप चलाना होगा।
इसलिए एक इष्टतम समाधान के लिए कुल समय जटिलता नोड्स की संख्या * उप-समस्याओं की संख्या * प्रत्येक उप-समस्या को हल करने में लगने वाला समय होगी। समय जटिलता को O(N) के रूप में परिभाषित किया जा सकता है² * 2^एन).
अंतरिक्ष जटिलता: डायनेमिक प्रोग्रामिंग दृष्टिकोण C(S, i) को संग्रहीत करने के लिए मेमोरी का उपयोग करता है, जहाँ S शीर्ष सेट का एक उपसमूह है। कुल 2 हैं^Nप्रत्येक नोड के लिए उपसमूह। इसलिए, स्पेस जटिलता O(2^N) है।

आगे, आप इसके बारे में जानेंगे एराटोस्थनीज की छलनी एल्गोरिथ्म