Find the shortest tour through the following cities (TSP). Provided is the x-coo

Question

Find the shortest tour through the following cities (TSP). Provided is the x-coordinates of the cities and the y coordinates of the cities. This is a "one-way" TSP, meaning that the start end cities will be different. The coordinates are x = (214 18 188 242 94 270 25 11 139 248 56 167 216 108 54 45 41 28 259 156 136 71 148 149 56 and 48) and y = (229 115 152 78 27 14 4 214 31 245 46 125 234 206 271 43 260 43 105 200 43 247 160 156 234 158). Provide the length of the shortest tour. As an example, the first city will have coordinates (214, 229).

Explanation / Answer

C++ Code

#include<iostream.h>
#include<math.h>
double calcdistance(int x1,int y1,int x2,int y2);

double calcdistance(int x1,int y1,int x2,int y2)//function computes distance between two points
{
double d=0.0;
d=sqrt(pow((x2-x1),2)+pow((y2-y1),2)); //coordinate geometry formula to calculate the distance between two coordinates
return d;
}
int main()
{
//initialised two arrays x and y with the given elements
int x[26]={214,18,188,242,94,270,25,11,139,248,56,167,216,108,54,45,41,28,259,156,136,71,148,149,56,48};
int y[26]={229,115,152,78,27,14,4,214,31,245,46,125,234,206,271,43,260,43,105,200,43,247,160,156,234,158};
int pos,i=0;
double mindistance=1000.0,dist=0.0;
for(i=1;i<26;i++)
{
dist=calcdistance(x[i-1],y[i-1],x[i],y[i]); //calling the method calcdistance by passing arguments x1,y1,x2,y2
if(dist<mindistance)
{
mindistance=dist; //stores the minimum distance
pos=i;//stores the minimum distance index(position)
}
cout<<"city "<<i+1<<" distance:"<<dist<<endl; //priting the city # and their distance from previous tour city
}
cout<<" Shortest Tour Length :"<<mindistance; //printing the minimum distance
cout<<" City #"<<pos<<" X="<<x[pos-1]<<" Y="<<y[pos-1]<<endl;
cout<<" City #"<<pos+1<<" X="<<x[pos]<<" Y="<<y[pos]<<endl;
return(0);
}

Output:

city 2   distance:226.742144
city 3   distance:173.979884
city 4   distance:91.60786
city 5   distance:156.54073
city 6   distance:176.479461
city 7   distance:245.203997
city 8   distance:210.466149
city 9   distance:223.322637
city 10   distance:240.160363
city 11   distance:276.523055
city 12   distance:136.242431
city 13   distance:119.507322
city 14   distance:111.570605
city 15   distance:84.504438
city 16   distance:228.177562
city 17   distance:217.036863
city 18   distance:217.389052
city 19   distance:239.175668
city 20   distance:140.121376
city 21   distance:158.268759
city 22   distance:214.105114
city 23   distance:116.180893
city 24   distance:4.123106
city 25   distance:121.37957
city 26   distance:76.419893

Shortest Tour Length :4.123106
City #23 X=148 Y=160

City #24 X=149 Y=156

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.