对TSP问题，分别运用全局遍历最优策略和贪心策略，编写C语言应用程序予以实现

Question

对TSP问题，分别运用全局遍历最优策略和贪心策略，编写C语言应用程序予以实现，要求如下。
(1) 分别设计5个城市和10个城市的数据，予以验证(2分)。
(2) 给出数据结构设计(最优化3分，贪心3分)。
(3) 最优化和贪心策略的源程序（程序设计规范，变量名见名知义，以英文单词命名，首字母大写，单词组合以下划线分割，加上程序运行的开始和结束时标，从而计算出程序运行的时间（最优化2分，贪心2分）。
(4）基于10个城市的数据，给出运行结果的屏幕截屏，并对比2种策略的时间性能（3分）。

Answer 1

补充一下题主的问题：
TSP问题（Travelling Salesman Problem）即旅行商问题。假设有一个旅行商人要拜访n个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。从图论的角度来看，该问题实质是给定一个带权完全无向图（顶点表示城市，边表示道路，权重是道路的成本或距离），找一个权值最小的 Hamilton 回路。
数据的话，可以直接在网上下载，

Teaching http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/tsp/

贪心算法，顾名思义就是用每一步的最优解代替整体的最优解（显然，这个不一定成立）。对于TSP问题，就是在当前节点下遍历所有能到达的下一节点，选择距离最近的节点作为下一节点。
代码如下：

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<math.h>
#include<stdlib.h>
#include<time.h>

// 城市数量 N
#define N 10
// 城市距离矩阵
int distance[N][N];


void init()
{
    //城市的 x 和 y 坐标
    int x[N] = { 0 };
    int y[N] = { 0 };
    //从 data.txt 文件读取数据
    FILE* fp;
    if ((fp = fopen("..//att10.txt", "r")) == NULL)
        //if ((fp = fopen("..//kroB100.txt", "r")) == NULL)
    {
        printf("can not open the file!");
        exit(0);
    }
    while (!feof(fp))
    {
        int count;
        fscanf(fp, "%d", &count);
        fscanf(fp, "%d%d", &x[count - 1], &y[count - 1]);
    }
    fclose(fp);
    //计算城市之间距离
    for (int i = 0; i < N - 1; i++)
    {
        distance[i][i] = 0;                // 对角线为0
        for (int j = i + 1; j < N; j++)
        {
            double dis = sqrt((pow((double)x[i] - x[j], 2) / 10 + pow((double)y[i] - y[j], 2) / 10));
            int disInt = (int)dis;
            distance[i][j] = dis == disInt ? disInt : disInt + 1;
            distance[j][i] = distance[i][j];
        }
    }
    distance[N - 1][N - 1] = 0;
}

/***********************************************************************
 * Function   ：TSPGreedyAlgorithm()
 * Description：贪心策略求解 TSP 问题
 * Input      ：void
 * Output     ：TSP 路径和对应的总距离
 * Return     ：void
 ***********************************************************************/
void TSPGreedyAlgorithm()
{
    //总路程
    int totalDistance = 0;        
    //默认从 0 开始遍历
    int current = 0;    
    //标识城市是否被访问,访问过置为 1
    bool visit[N] = { false };
    visit[0] = 1;
    printf("TSP 路径为：%d ->", 1);

    //遍历 N - 1 次
    for (int i = 1; i < N; i++)
    {
        //设置较大的距离初始值用来选取最近邻
        int min_distance = 0x7fffffff;
        //保存当前最近邻城市
        int temp;
        //循环选取城市
        for (int j = 1; j < N; j++)
        {
            if (!visit[j] && distance[current][j] < min_distance)
            {
                min_distance = distance[current][j];
                temp = j;
            }
        }
        visit[temp] = 1;
        current = temp;
        totalDistance += min_distance;
        printf(" %d ->", temp + 1);
    }
    totalDistance += distance[current][0];
    printf(" %d\n", 1);
    printf("TSP 总距离为：%d\n", totalDistance);
}

int main()
{
    init();
    TSPGreedyAlgorithm();
    return 0;
}