DAA - ट्रैवलिंग सेल्समैन समस्या

समस्या का विवरण

एक यात्री को एक सूची से सभी शहरों का दौरा करने की आवश्यकता है, जहां सभी शहरों के बीच की दूरी ज्ञात है और प्रत्येक शहर को बस एक बार जाना चाहिए। वह सबसे छोटा संभव मार्ग क्या है जो वह प्रत्येक शहर में एक बार आता है और मूल शहर में लौटता है?

समाधान

ट्रैवलिंग सेल्समैन समस्या सबसे कुख्यात कम्प्यूटेशनल समस्या है। हम प्रत्येक संभावित दौरे का मूल्यांकन करने और सर्वश्रेष्ठ का चयन करने के लिए जानवर-बल दृष्टिकोण का उपयोग कर सकते हैं। के लियेn एक ग्राफ में कोने की संख्या, वहाँ हैं (n - 1)! संभावनाओं की संख्या।

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

आइए हम एक ग्राफ पर विचार करें G = (V, E), कहाँ पे V शहरों का एक सेट है और Eभारित किनारों का एक सेट है। एक किनारेe(u, v) उस कोने का प्रतिनिधित्व करता है u तथा vजुड़े हुए हैं। वर्टेक्स के बीच की दूरीu तथा v है d(u, v), जो गैर-नकारात्मक होना चाहिए।

मान लीजिए हमने शहर में शुरुआत की है 1 और कुछ शहरों का दौरा करने के बाद अब हम शहर में हैं j। इसलिए, यह एक आंशिक दौरा है। हमें निश्चित रूप से जानने की जरूरत हैj, क्योंकि यह निर्धारित करेगा कि कौन से शहर अगले यात्रा के लिए सबसे सुविधाजनक हैं। हमें अब तक गए सभी शहरों को भी जानना होगा, ताकि हम उनमें से किसी को भी न दोहराएं। इसलिए, यह एक उपयुक्त उप-समस्या है।

शहरों के सबसेट के लिए S Є {1, 2, 3, ... , n} जिसमें शामिल है 1, तथा j Є S, जाने दो C(S, j) प्रत्येक नोड में आने वाले सबसे छोटे पथ की लंबाई हो S बिल्कुल एक बार, शुरू करने पर 1 और अंत में j।

कब |S| > 1, हम परिभाषित करते हैंC(S, 1) = = चूंकि पथ शुरू नहीं हो सकता है और समाप्त नहीं हो सकता है 1।

अब, व्यक्त करते हैं C(S, j)छोटी उप-समस्याओं के संदर्भ में। हम पर शुरू करने की जरूरत है1 और अंत में j। हमें इस तरह से अगले शहर का चयन करना चाहिए

$ $ C (S, j) = min \: C (S - \ lbrace j \ rbrace, i) + d (i, j) \: जहां \: i \ _ S \: और \: i \ neq jc ( S, j) = minC (s- \ lbrace j \ rbrace, i) + d (i, j) \: जहां \: i \ _ S \: और \: i \ neq j $$

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

विश्लेषण

सबसे अधिक $ 2 ^ एनएन $ उप-समस्याएं हैं और प्रत्येक को हल करने के लिए रैखिक समय लगता है। इसलिए, कुल चलने का समय $ O (2 ^ nn ^ 2) $ है।

उदाहरण

निम्नलिखित उदाहरण में, हम यात्रा विक्रेता समस्या को हल करने के लिए चरणों का वर्णन करेंगे।

उपरोक्त ग्राफ से, निम्न तालिका तैयार की जाती है।

	1	2	3	4
1	0	10	15	20
2	5	0	9	10
3	6	13	0	12
4	8	8	9	0

स = Φ

$ $ \ _ छोटी लागत (2, \ Phi, 1) = d (2,1) = 5 \ _ छोटी लागत (2, \ Phi, 1) = d (2,1) = 5 $ $

$ $ \ _ छोटी लागत (3, \ Phi, 1) = d (3,1) = 6 \ _ छोटी लागत (3, \ Phi, 1) = d (3,1) = 6 $ $

$ $ \ _ छोटी लागत (4, \ Phi, 1) = d (4,1) = 8 \ _ छोटी लागत (4, \ Phi, 1) = d (4,1) = 8 $ $

एस = 1

$ $ \ _ छोटी लागत (i, s) = न्यूनतम \ lbrace लागत (j, s - (j)) + d [i, j] \ rbrace \ 'छोटी लागत (i, s) = मिनट \ lbrace लागत (j, s) ) - (j)) + d [i, j] \ rbrace $ $

$ $ \ _ छोटी लागत (2, \ lbrace 3 \ rbrace, 1) = d [2,3] + लागत (3, \ Phi, 1) = 9 + 6 = 15cost (2, \ lbrace3 \ rbrace, 1) = d [2,3] + लागत (3, \ Phi, 1) = 9 + 6 = 15 $ $

$ $ \ _ छोटी लागत (2, \ lbrace 4 \ rbrace, 1) = d [2,4] + लागत (4, \ Phi, 1) = 10 + 8 = 18cost (2, \ lbrace4 \ rbrace, 1) = डी [2,4] लागत (4, \ फी, 1) = 10 + 8 = 18 $$

$ $ \ _ छोटी लागत (3, \ lbrace 2 \ rbrace, 1) = d [3,2] + लागत (2, \ Phi, 1) = 13 + 5 = 18cost (3, \ lbrace2 \ rbrace, 1) = डी [3,2] लागत (2, \ फी, 1) = 13 + 5 = 18 $$

$ $ \ _ छोटी लागत (3, \ lbrace 4 \ rbrace, 1) = d [3,4] + लागत (4, \ Phi, 1) = 12 + 8 = 20cost (3, \ lbrace4 \ rbrace, 1) = डी [3,4] लागत (4, \ फी, 1) = 12 + 8 = 20 $$

$ $ \ _ छोटी लागत (4, \ lbrace 3 \ rbrace, 1) = d [4,3] + लागत (3, \ Phi, 1) = 9 + 6 = 15cost (4, \ lbrace3 \ rbrace, 1) = डी [4,3] लागत (3, \ फी, 1) = 9 + 6 = 15 $$

$ $ \ _ छोटी लागत (4, \ lbrace 2 \ rbrace, 1) = d [4,2] + लागत (2, \ Phi, 1) = 8 + 5 = 13cost (4, \ lbrace2 \ rbrace, 1) = डी [4,2] लागत (2, \ फी, 1) = 8 + 5 = 13 $$

एस = 2

$ $ \ _ छोटी लागत (2, \ lbrace 3, 4 \ rbrace, 1) = \ start {मामलों} d [2, 3] + लागत (3, \ lbrace 4 \ rbrace, 1) = 9 + 20 + 29 \ " \ d [2, 4] + लागत (4, \ lbrace 3 \ rbrace, 1) = 10 + 15 = 25 = 25 \ _ छोटी लागत (2, \ lbrace 3,4 \ rbrace, 1) \\\ lbrace d [ 2,3] + \ _ छोटी लागत (3, \ lbrace4 \ rbrace, 1) = 9 + 20 = 29d [2,4] + \ _ छोटी लागत (4, \ lbrace 3 \ rbrace, 1) = 10 + 15 + 25 \ अंत {मामलों} = 25 $ $

$ $ \ _ छोटी लागत (3, \ lbrace 2, 4 \ rbrace, 1) = \ start {मामलों} d [3, 2] + लागत (2, \ lbrace 4 \ rbrace, 1) = 13 + 18 = 31 \ _ \ d [3, 4] + लागत (4, \ lbrace 2 \ rbrace, 1) = 12 + 13 = 25 = 25 \ _ छोटी लागत (3, \ lbrace 2,4 \ rbrace, 1) \\\ lbrace d [ 3,2] + \ _ छोटी लागत (2, \ lbrace4 \ rbrace, 1) = 13 + 18 = 31d [3,4] + \ _ छोटी लागत (4, \ lbrace 2 \ rbrace, 1) = 12 + 13 + 25 \ अंत {मामलों} = 25 $ $

$ $ \ _ छोटी लागत (4, \ lbrace 2, 3 \ rbrace, 1) = \ start {मामलों} d [4, 2] + लागत (2, \ lbrace 3 \ rbrace, 1) = 8 + 15 = 23 \ _ \ d [4, 3] + लागत (3, \ lbrace 2 \ rbrace, 1) = 9 + 18 = 27 = 23 \ _ छोटी लागत (4, \ lbrace 2,3 \ rbrace, 1) \\\ lbrace d [ 4,2] + \ _ छोटी लागत (2, \ lbrace3 \ rbrace, 1) = 8 + 15 = 23d [4,3] + \ _ छोटी लागत (3, \ lbrace 2 \ rbrace, 1) = 9 + 18 + 27 \ अंत {मामलों} = 23 $ $

एस = ३

$ $ \ _ छोटी लागत (1, \ lbrace 2, 3, 4 \ rbrace, 1) = \ start {मामलों} d [1, 2] + लागत (2, \ lbrace 3, 4 \ rbrace, 1) 10 + + 25 = 35 \\ d [1, 3] + लागत (3, \ lbrace 2, 4 \ rbrace, 1) = 15 + 25 = 40 \\ d [1, 4] + लागत (4, \ lbrace 2, 3) \ rbrace, 1) = 20 + 23 = 43 = 35 लागत (1, \ lbrace 2,3,4 \ rbrace), 1) \\ d [1,2] + लागत (2, \ lbrace 3,4 \ rbrace) , 1) = 10 + 25 = 35 \\ d [1,3] + लागत (3, \ lbrace 2,4 \ rbrace, 1) = 15 + 25 = 40 \\ d [1,4] + लागत (4) , \ lbrace 2,3 \ rbrace, 1) = 20 + 23 = 43 = 35 \ अंत {केस} $ $

न्यूनतम लागत पथ 35 है।

लागत से शुरू करें {1, {2, 3, 4}, 1}, हम के लिए न्यूनतम मूल्य मिलता है d [1, 2]। कबs = 3, 1 से 2 तक का मार्ग चुनें (लागत 10 है) फिर पीछे की ओर जाएं। कबs = 2, हम के लिए न्यूनतम मूल्य मिलता है d [4, 2]। 2 से 4 तक पथ का चयन करें (लागत 10 है) फिर पीछे की ओर जाएं।

कब s = 1, हम के लिए न्यूनतम मूल्य मिलता है d [4, 3]। पथ 4 से 3 का चयन करना (लागत 9 है), फिर हम तब तक जाएंगेs = Φकदम। हमें न्यूनतम मूल्य मिलता हैd [3, 1] (लागत 6 है)।