基于贪心算法求解TSP问题(C语言实现)

贪心算法

贪心算法是根据已有信息做出选择,不管将来有什么结果,这个选择都不会改变:得到的是局部最优解(Near-Optimal Solution)。

例子:

付款问题的策略就是尽可能的使付出的货币最快地满足支付要求,使付出货币的张数慢慢的增加。

截屏2022-02-12 下午10.10.47

(1)候选集合C(Candidate):问题的可能解-如问题中各种面值的货币

(2)解集合S:解集合不断扩展至到构成一个满足问题的完整解-已付出的货币

(3)解决函数Solution(S):检查解集合S是否已经构成了问题的完整解-如问题中货币金额等于应付款

(4)选择函数Select(C):即贪心策略(贪心算法的核心),它指出哪个候选对象最有希望构成问题的解-如问题中候选集合中选择面值最大的货币。

(5)可行函数Feasible(S,x):检查解集合(S)中加入一个候选对象(来自候选集合C)是否可行-如问题中每一步选择的货币和已付出的货币相加不超过应付款。

用伪代码描述为:

截屏2022-02-12 下午10.28.50

定义1.G=(V,E)

如果G中有生成圈(生成圈:包含所有顶点的一个回路叫做生成圈)则称为G为哈密顿图。

在保证一条边的两个顶点不是一样的颜色的前提下,对图进行染色。

如果能染色(任意一条边的两个顶点都是不一样的颜色),而且染出来的两种颜色的点数不一样,则一定不是哈密顿图。(如下图就不是哈密顿图)

截屏2022-02-21 下午1.27.04

如果不能染色(因为有一条边的两个顶点不能保证不是一样的颜色),可能是哈密顿图也可能不是哈密图。(如下图就一定是哈密顿图)

截屏2022-02-21 下午1.27.31

如果被染色的顶点数一样多(没有形成回路),也不一定是哈密顿图。(如下图就不是哈密顿图)

截屏2022-02-21 下午1.28.56

定理:G=(V,E),S⊆V,w(G-S)<= |S|

(G表示图的最大集合,V表示图中所有顶点的集合,E表示所有边的集合,w表示分支数,S表示图中的部分顶点)

贪心算法来解决TSP问题得到的一定是一个局部最优解,但总路程不一定是最小的

从任意城市出发,每次在没有到过的城市中选择最近的一个,直到经过了所有的城市,最后回到出发城市。

截屏2022-02-12 下午10.42.09

代价矩阵:矩阵中任意元素cij:从第i个城市出发,到第j个城市花费的代价,代价越小,说明城市相隔越近。

中文流程图:

截屏2022-02-21 下午3.06.25
 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问题经过贪心算法后的解的总距离是多少

细化(5)从所有未访问过的城市中查找距离S[I-1]最近的城市j的描述:

截屏2022-02-21 下午3.52.47
 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是外部层循环

程序流程图:

截屏2022-02-21 下午3.54.29

具体代码实现:

  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;
}

参考资料:

https://www.bilibili.com/video/BV1r7411j7Kq?p=133&spm_id_from=pageDriver

https://blog.csdn.net/mahoon411/article/details/105940729