Mathematica के साथ ट्रैवलिंग सेल्समैन समस्या को हल करना

समस्या

電車でこんな広告を見かけました😁📸 pic.twitter.com/iXEgvtXrpL

— 早稲田大学 早水桃子研究室 (@hayamizu_lab) October 11, 2022

उपाय

1

d=SparseArray[{{1,2}->10,{2,1}->10,{1,5}->15,{5,1}->15,{1,4}->12,{4,1}->12,{1,3}->20,{3,1}->20,{2,5}->10,{5,2}->10,{3,4}->10,{4,3}->10,{3,8}->30,{8,3}->30,{3,7}->20,{7,3}->20,{3,6}->25,{6,3}->25,{4,5}->15,{5,4}->15,{4,8}->20,{8,4}->20,{5,9}->18,{9,5}->18,{5,8}->15,{8,5}->15,{6,7}->5,{7,6}->5,{7,8}->35,{8,7}->35,{8,9}->12,{9,8}->12},{9,9},Infinity];

SparseArray फ़ंक्शन का उपयोग करके एक मैट्रिक्स बनाएं। प्रत्येक तत्व उस तत्व की पंक्ति और कॉलम में शहरों के बीच की दूरी का प्रतिनिधित्व करता है। उदाहरण के लिए, पहले तत्व {1,2}->10 का अर्थ है कि 1 और 2 के बीच की दूरी 10 है। दूसरा-से-अंतिम तत्व {9,9} मैट्रिक्स के आकार को इंगित करता है, और अंतिम तत्व Infinity का अर्थ है कि अनिर्दिष्ट शहरों के बीच पथ की लंबाई अनंत है। दूसरे शब्दों में, इसका मतलब है कि कोई रास्ता नहीं है।

1

{len,tour}=FindShortestTour[{1,2,3,4,5,6,7,8,9},DistanceFunction->(d[[#1,#2]]&)]

FindShortestTour फ़ंक्शन के साथ, आप ट्रैवलिंग सेल्समैन समस्या को आसानी से हल कर सकते हैं। {1,2,3,4,5,6,7,8,9} शहर के नंबरों को दर्शाता है। DistanceFunction->(d[[#1,#2]]&) मैट्रिक्स d पास करता है, जो शहरों के बीच की दूरी को दर्शाता है।

आउटपुट

1

{137, {1, 2, 5, 9, 8, 7, 6, 3, 4}}

आउटपुट सबसे छोटी दूरी और उसके संबंधित मार्ग को दर्शाता है। सबसे छोटी दूरी 137 है, और मार्ग 1→2→5→9→8→7→6→3→4→1 है। ABC वर्णमाला क्रम में बदलने पर, यह A, B, E, I, H, G, F, C, D बन जाता है।