C++ 实现旅行商问题：最短路线算法

#include #include #include #include

using namespace std;

const int INF = 1e9;

vector<vector> dist; // 两点之间的距离 vector path; // 记录路径 vector visited; // 记录节点是否被访问

int n = 3; // 节点个数

// 计算两点之间的距离 int getDistance(int x1, int y1, int x2, int y2) { return round(sqrt(pow(x1-x2, 2) + pow(y1-y2, 2))); }

// 初始化距离矩阵 void initDist() { dist.resize(n); for (int i = 0; i < n; i++) { dist[i].resize(n); for (int j = 0; j < n; j++) { if (i == j) { dist[i][j] = 0; } else { int x1, y1, x2, y2; switch (i) { case 0: x1 = 1; y1 = 1; break; case 1: x1 = 2; y1 = 2; break; case 2: x1 = 3; y1 = 3; break; } switch (j) { case 0: x2 = 1; y2 = 1; break; case 1: x2 = 2; y2 = 2; break; case 2: x2 = 3; y2 = 3; break; } dist[i][j] = getDistance(x1, y1, x2, y2); } } } }

// 贪心算法求解TSP int TSP() { int res = 0; path.resize(n); visited.resize(n, false); visited[0] = true; // 从第一个节点开始 path[0] = 0; for (int i = 1; i < n; i++) { int minDist = INF, nextNode = -1; for (int j = 0; j < n; j++) { if (!visited[j] && dist[path[i-1]][j] < minDist) { minDist = dist[path[i-1]][j]; nextNode = j; } } res += minDist; visited[nextNode] = true; path[i] = nextNode; } res += dist[path[n-1]][0]; // 回到起点 return res; }

int main() { initDist(); int res = TSP(); cout << '最短路程为：' << res << endl; cout << '路径为：'; for (int i = 0; i < n; i++) { cout << path[i] << ' '; } cout << endl; return 0;