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

TSP问题是一种著名的NP问题，贪心算法可以求解TSP问题的近似解。具体来说，可以采用以下贪心策略：

1. 选择一个起点，例如城市1。

2. 从未访问的城市中选择距离当前城市最近的城市，加入到路径中。

3. 重复步骤2，直到所有城市都被访问过。

4. 最后把最后一个城市与起点城市相连，形成一条回路。

这个贪心策略的正确性可以通过矛盾法证明。假设存在一条更优的回路，那么必然存在一对相邻的城市，其距离比这条路径中的另一对相邻城市更短，否则将这对城市交换位置可以得到更优解。那么我们可以通过交换这对城市的位置，得到一个更优的回路，与假设矛盾，因此原假设不成立，贪心策略是正确的。

不过需要注意的是，这个贪心算法并不一定能够得到最优解，只能得到一个近似解。其复杂度为O(n^2)，其中n为城市数。