1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

（1）S[1]=1  //我们从1号城市出发进行访问 S[1]=1表示城市1现在被访问过了
（2）Sum=0   //目前我们还没有对除一号城市以外对其他城市进行访问 所有走过的总路程为0
（3）初始化距离数组D //将各各城市之间的距离写为对称矩阵的形式 后续我们将用tcplib中的数据进行代替
（4）I=2     //I表示第I次访问想要访问的城市 I=2表示第二次访问的城市
（5）从所有未访问过的城市中查找距离S[I-1]最近的城市j //因为I次访问是我们即将访问下一个城市 S[I-1]表示我们目前位于哪个城市（具体描述见下一个图）
（6）S[I]=j //找到距离我们目前城市最近的城市j后，我们将旅行到城市j，此时j也变成了我们已经第I次访问过的城市并记录在S[I]中
（7）I = I+1 //我们将对接下来的一个城市I进行访问
（8）Sum = Sum+Dtemp //Dtemp中存储了（5）中的S[I-1]到j这两个城市之间的距离，因为此时我们经过（6）已经对j城市进行了访问，所以要将Dtemp加到Sum中
（9）如果I<=N,转步骤（5），否则转步骤（10）//如果我们还没有对最后一个城市进行访问 那么我们就应该回到（5）对最后一个城市进行访问 否则说明目前我们站在了最后一个城市 为了形成哈密顿回路，我们要将最后一个城市和第一个城市之间的距离加到Sum，以完成TSP访问。
（10）Sum = Sum+D[1,j]  
（11）逐个输出S[N]中的全部元素 //相当于查看当前的访问路径
（12）输出Sum //查看TSP问题经过贪心算法后的解的总距离是多少

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

关于（5）的具体过程描述
从所有未访问过的城市中查找距离S[I-1]最近的城市j //目前我们站在S[I-1]的地方去寻找下一个离我们最近的未访问过的城市
（5.1）K=2 //因为我们不知道哪个城市被访问过 哪个城市没有被访问过 所以我们从第2个城市到第N个城市（最后一个城市）进行遍历
（5.2）将Dtemp设置为一个大数（比所有两个城市之间的距离都要打）//因为我们此时一定可以找到一个城市j到城市S[I-1]的距离比这个大数小
（5.3）L=1 
（5.4）如果S[L]==k,转步骤5.8 //我们目前站在城市S[I-1]，如果从S[0]到S[I-1]中都出现了K这个城市 那此时的K城市一个不是我们要找的城市 所以通过5.8让K+1
（5.5）L=L+1 //为了实现5.4中从S[1]到S[I-1]到遍历
（5.6）如果L<I，转5.4 //从S[1]到S[I-1]的循环遍历还未完成 要继续遍历 如果遍历完成都发现K城市没在S[1]到S[I-1]中，那么就对比此时K城市到当前城市S[I-1]的距离 如果K到S[I-1]的距离小于Dtemp，就将该距离通过Dtemp记录下来
（5.7）如果D[K,S[I-1]]<Dtemp,则j=K；Dtemp=D[K,S[I-1]] //
（5.8）K=K+1 //这条是为了实现从2到N的遍历
（5.9）如果K<=N，转步骤5.3 //这条也是为了实现从2到N的遍历

注：5.5 5.6 5.8 5.9都是在写循环遍历的时候用 5.3到5.6是内部层循环 5.1到5.9是外部层循环

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116

#include <stdio.h>

/**
 *打印访问顺序
 * @param S  已经访问过的城市数组
 * @param n  城市个数
 */
void InfoPrint(int S[],int n)
{
    int i;
    printf("城市%d",S[1]);
    for (i = 2; i <=n; i++) {
        printf("----->城市%d",S[i]);
    }
    printf("----->城市%d\n",S[1]);
}

/**
 *从所有未访问过的城市中查找距离S[I-1]最近的城市j
 * @param I 访问次数 0-I-1次表示已经访问过 S[I-1]表示目前所在位置 S[I]表示将要访问的地方
 * @param S S数组表示已经访问过的地方
 * @param n 表示地点个数
 * @param D 表示两地点间的距离
 * @param Dtemp 表示两城市间的最短距离
 * @return
 */
int FindCity(int I, const int *S, int n,int D[][n],int *Dtemp)
{
    //用来存储 K城市到当前城市S[I-1]的距离 初始化为一个大数
    *Dtemp=1000;
    //从第2个城市到第N个城市（最后一个城市）进行遍历 寻找未被访问过的最近城市
    int K =2;
    //用来存储第I次访问的城市代号
    int j;
    //从2到n个城市中查找一个没有被访问过且距离当前城市S[I-1]最近到城市
    do {
        //当我们拿到一个城市K的时候，我们不知道这个城市是否被访问过，所以通过下面这个循环来判断该城市是否被访问过
        //使用L从第1个城市到到第I-1个城市进行遍历（目前走过的城市） 看城市K是否被访问过
        int L =1;
        do
        {
            //如果城市K已经是被访问过的城市 那就跳出循环，看K+1这个城市是否被访问过
            if(S[L] == K)
            {
                break;
            }
            //如果K城市没被访问过 那就从S[L+1]中找K 一直找到L==I-1
            L+=1;
        } while (L<I);
        //有两种情况为出循环
        //如果是自然退出循环(即城市K没有被访问过） 那L==I
        if(L==I)
        {
            //此时就要对城市K到S[I-1]进行记录
            if((D[K-1][S[I-1]-1]) < *Dtemp)
            {
                j = K;
                *Dtemp = D[K-1][S[I-1]-1];
            }
        }
        K+=1;
    } while (K<=n);
    return j;
}
/**
 * 贪婪算法主体
 * @param n 城市个数
 * @param D 城市之间的距离
 * @return
 */
int Tsp(int n,int D[][n])
{
    int S[n];//已经访问过的城市数组
    int Sum;
    int I;      //已经进行了I-1次访问 目前正在进行第I次访问
    int Dtemp;
    int j; //用来存储第I次访问的城市代号

    //初始化
    //初始化最终的访问距离为0
    Sum = 0;
    //表示城市1现在被访问过了
    S[1]=1;

    //开始进行访问
    //表示进行第二次访问的城市
    I = 2;
    //如果第I次访问小于等于N 那么说明访问未完成
    do {
        j = FindCity(I,S,n,D,&Dtemp);

        //找到距离我们目前城市最近的城市j后 旅行到城市j
        S[I] = j;
        //接下来对下一个城市进行访问
        I+=1;
        //将之前城市到j的距离加入sum中
        Sum+=Dtemp;
    } while (I<=n);
    //如果走到来最后一个城市 那么就回到出发城市
    Sum=Sum+D[1][j];
    InfoPrint(S,n);
    return Sum;
}

int main() {
    int D[5][5];
    //初始化各各城市之间的距离
    D[0][1] = 3; D[0][2] = 3; D[0][3] = 2; D[0][4] = 6;
    D[1][0] = 3; D[1][2] = 7;D[1][3] = 3;D[1][4] = 2;
    D[2][0] = 3; D[2][1] = 7; D[2][3] = 2; D[2][4] = 5;
    D[3][0] = 2;D[3][1] =3; D[3][2] =2;D[3][4] = 3;
    D[4][0] = 6;D[4][1] =2;D[4][2] = 5;D[4][3] = 3;
    printf("最终访问距离为:%d\n",Tsp(5,D));
    return 0;
}