中北大学算法贪心算法问题实验：题目1 贪心算法解决TSP问题

1.实验名称

贪心算法问题实验：题目1 贪心算法解决TSP问题

2.实验目的

(1)掌握贪心法的设计思想；
(2)掌握TSP问题的具体实现过程；
(3)熟练掌握二维数组的使用方法；
(4)在掌握的基础上编程实现TSP问题的具体实现过程。

3.实验内容

给出n个城市及任意两城市间的距离，要求旅行家在旅行者个城市时，各个城市经历且仅经历一次然后回到出发城市，使得所走的路径最短。输出结果，输出时要求有文字说明。请任选一种语言编写程序。

4.实验原理

贪心法是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是全局最好或最优的算法策略。贪心法通常用于那些具有贪心选择性质的问题，即局部最优选择可以导致全局最优解的问题。
对于TSP，贪心法可能会在每一步选择最近的下一个城市，但这种方法不能保证最终路径是最短的，因为可能存在更远的路径，但总体上能更快地连接所有城市并返回起点。

5.实验过程

伪代码

在这里插入图片描述

C++代码

#include <iostream>
#include <vector>
#include <climits> // 用于INT_MAX
#include <algorithm> // 用于sortusing namespace std;// 找到最近的未访问城市
int findNearestCity(const vector<vector<int>> &distances, vector<bool> &visited, int current) {int minDistance = INT_MAX;int minCity = -1;for (int i = 0; i < distances.size(); ++i) {if (!visited[i] && distances[current][i] < minDistance) {minDistance = distances[current][i];minCity = i;}}return minCity;
}// 贪心算法解决旅行商问题
vector<int> greedyTravelingSalesman(const vector<vector<int>> &distances) {int n = distances.size();vector<int> path;vector<bool> visited(n, false);int start = 0; // 假设从城市0开始path.push_back(start);visited[start] = true;for (int i = 1; i < n; ++i) {int current = findNearestCity(distances, visited, path[i - 1]);path.push_back(current);visited[current] = true;}// 将起始城市添加到路径末尾，完成循环path.push_back(start);return path;
}int main() {// 4个城市的距离矩阵vector<vector<int>> distances = {{0, 10, 15, 34},{10, 0, 8, 20},{15, 8, 0, 12},{34, 20, 12, 0}};vector<int> path = greedyTravelingSalesman(distances);cout << "贪心算法得到的路径: ";for (int city : path) {cout << city << " ";}cout << endl;return 0;
}

时间复杂度：

findNearestCity函数调用：在每次迭代中，findNearestCity函数都会被调用一次，用于找到最近的未访问城市。这个函数的时间复杂度是O(n)，因为它需要遍历所有未访问的城市。
循环次数：在greedyTravelingSalesman函数中，有一个循环，它执行n次迭代，其中n是城市的数量。
路径构建：在循环中，每次迭代都会将一个城市添加到路径中，并将该城市标记为已访问。这个过程的时间复杂度是O(1)。
综合以上因素，整个算法的时间复杂度是O(n^2)，因为对于n个城市，我们需要执行n次迭代，每次迭代中findNearestCity函数需要O(n)的时间来找到最近的未访问城市。

6.实验结论及心得

代码运行截图