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> // 用于sort
using 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.实验结论及心得
代码运行截图
心得
1.问题规模的影响：问题规模对算法性能有显著影响。在小规模问题上，贪心算法可能表现得相当不错，但在大规模问题上，可能需要更复杂的算法来获得更好的结果。
2.算法的适用性：每种算法都有其适用的场景。贪心算法在某些问题上可能非常有效，但在其他问题上可能不适用。了解算法的适用性可以帮助我们更好地选择和应用算法。