Question

Give 10 cities located within 1,000 miles (left to right) by 1,000 miles (bottom to top) region, calculate the shortest traveling path from the traveling salesman problem. The 10 cities are A, B, C, D, E, F, G, H, I, and J. Locations of 10 cities are

A (X: 100, Y: 300)

B (X: 200, Y: 130)

C (X: 300, Y: 500)

D (X: 500, Y: 390)

E (X: 700, Y: 300)

F (X: 900, Y: 600)

G (X: 800, Y: 950)

H (X: 600, Y: 560)

I (X: 350, Y: 550)

1. The text file contains the shortest path value and the sequence order of 10 cities visited.
2. Not asking for code but the text file to get an idea please.
3. for C++

Answer 1

Answer:--                                                             Date:--01/04/2019

#include <iostream>
#include <map>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;

map<char, pair<int, int> > val;

double calculateDistance(pair<int, int> first, pair<int, int> second) {
int x1 = first.first;
int y1 = first.second;

int x2 = second.first;
int y2 = second.second;

return sqrt((x1-x2)*(x1-x2) + (y1-y2)*(y1-y2));
}

pair< double, vector<char> > tsp(vector<char> v) {
vector<char> path;
pair< double, vector<char> > answerPair;
pair<int, int> p = val[v[0]];
v.erase(v.begin());

double shortestDistance = 1<<30;
int size = v.size();

do {
double weight = 0;

weight += calculateDistance(p, val[v[0]]);
for(int i=1; i<=size; i++) {
weight += calculateDistance(val[v[i-1]], val[v[i]]);
}
weight += calculateDistance(val[v[size]], p); if(weight < shortestDistance) {
shortestDistance = weight;
path.clear();
path.push_back('A');
for(vector<char>::iterator it = v.begin(); it != v.end(); it++) {
path.push_back(*it);
}
}
} while(next_permutation(v.begin(), v.end()));answerPair.first = shortestDistance;
answerPair.second = path;
return answerPair;
}

int main() {
val['A'] = make_pair(100, 300);
val['B'] = make_pair(200, 130);
val['C'] = make_pair(300, 500);
val['D'] = make_pair(500, 390);
val['E'] = make_pair(700, 300);
val['F'] = make_pair(900, 600);
val['G'] = make_pair(800, 950);
val['H'] = make_pair(600, 560);
val['I'] = make_pair(350, 550);
val['J'] = make_pair(270, 350);

vector<char> v;
for(char ch = 'A'; ch <= 'J'; ch++) {
v.push_back(ch);
}
pair< double, vector<char> > p = tsp(v);
cout << "Shortest distance value: " << p.first << " miles" << endl;
cout << "Sequence order of 10 cities: ";
for(vector<char>::iterator it = p.second.begin(); it != p.second.end(); it++) {
cout << *it << " -> ";
}
cout << 'A';
}

output:--