人工智能实验之采用启发式搜索求解TSP问题_启发式搜索算法实验

实验描述

本实验要求采用启发式搜索算法求解TSP问题的近似解，采用C系列语言编程实现

TSP 问题的一般描述为 : 旅行商从驻地出发 ,经所有要去的城市一次后返回原地 。应如何安排其旅行路线才能使总的旅行距离(或时间、费用等) 最少 。

其数学描述为 : 设有 N 个城市的集合 V ={ v1 , v 2 , …,v N }，每两个城市之间的距离为 d vi ,v j∈ R+ ,其中 , vi,vj ∈ V且i , j =1 ,2 , …, N ; 设对于城市集合V的一个访问顺序为 T ={ t1 , t2 ,…, t k , …, tN },其中tk =vi ,i =1 ,2 , …, N ,且tN+ 1 =t1。问题是求一条距离最短的包含 所有城市的闭合回路，即求满足目标函数的城市序列，其中Q 为这 N个城市不重复排列的所有可能的闭合回路。

算法实现过程描述

如图，本试验采用的启发式算法步骤为：

1. 利用最小生成树算法构造无向图 G 的TSP问题的最小生成树；
2. 然后从最小生成树开始构造闭合回路(N个城市不重复排列序列)；
3. 最后确定从不同顶点生成的最小生成树开始构造的闭合回路中距离最小的一个 ,即最短城市序列 。
   

详细实现过程

最小生成树
这里采用Prim算法（“加点法”）实现，原因在于便于从不同顶点开始生成其最小生成树，本次实验采用的算法代码引用于>>这里（点击查看）

如何从不同的顶点来生成最小生成树？由于采用的Prim算法默认从顶点1进行构造，这里我们用graph[MAX][MAX]数组来表示我们的带权无向图，通过交换顶点1与我们需要开始构造最小生成树的顶点APEX到其他各个顶点之间的距离即可从顶点APEX开始构造最小生成树。

for(APEX = 1; APEX <= m;)
	{
    	printf("以顶点%d构造最小生成树\n",APEX);
		prim(graph, m);//用prim算法从顶点1生成最小生成树 
		
		if(APEX>1)
		{
			for(i = 2; i <= m; i++)
		    {
		    	if(i!=APEX)
		    	{
			    	cost = graph[1][i];
					graph[1][i] = graph[APEX][i];
					graph[i][1] = graph[APEX][i];
			    	graph[APEX][i] = cost;
			    	graph[i][APEX] = cost;
				}
			}
		}	
	    APEX++;
	    for(i = 2; i <= m; i++)
	    {
	    	if(i!=APEX)
	    	{
		    	cost = graph[1][i];
					graph[1][i] = graph[APEX][i];
					graph[i][1] = graph[APEX][i];
			    	graph[APEX][i] = cost;
			    	graph[i][APEX] = cost;
			}
		}
		//重设顶点后需要初始化  
	    for(i = 0; i<=m; i++){
	       	for(j = 0; j<=m; j++){
	  	      	minst[i][j] = 0;  
			    minst[j][i] = 0; 
			    minstdu[i] = 0;
			    minstdu[j] = 0;
			    Connected[i] = 0;
			    Connected[j] = 0;
			}
		}
	    mstcostnum = 0;
	}
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

当生成最小生成树之后，由于闭合回路中每个节点的度都为2 ,因此在构造闭合回路时需要处理最小生成树中度不等于2的节点。

处理时,第一步是通过删除边的方法降低最小生成树中度大于2的节点的度 ,保证每个节点的度都不大2。

删除边时,首先选择与待处理节点(度大于2的节点)相连接的节点中度最大的节点,如果被选择节点的度大于2 ,则删除这两节点之间的边,降低这两节点的度。否则,选择与待处理节点相连接的节点中权值大的节点,删除这两节点之间的边 ,降低这两节点的度 。

for(k = 1; k <= m; k++)//第一步,降低最小生成树中度大于2的节点的度 ,保证每个节点的度都不大2。
		{
			if(minstdu[k]>2)
			{
				maxdu = mstMAXdu(k,m); 
				maxdupoint = mstMAXdupt(k,maxdu,m);
				if(maxdu>2)
				{
					minst[k][maxdupoint] = 0;
					minst[maxdupoint][k] = 0;
					minstdu[k]--;
					minstdu[maxdupoint]--;
					mstcostnum--;
				}
				else
				{
					maxmstcost = mstMAXcost(k,m); 
					maxmstcostpoint = mstMAXcostpt(k,maxmstcost,m);
					minst[k][maxmstcostpoint] = 0;
					minst[maxmstcostpoint][k] = 0;
					minstdu[k]--;
					minstdu[maxmstcostpoint]--;
					mstcostnum--; 
				}
			}
		} 
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

第二步是通过连接的方法 , 连接最小生成树中度小于2 的节点 , 构成闭合回路 。

连接时为了保证所有节点在同一个连通分量中 ,首先标记各连通分量 ,然后选择不同连通分量中度小于 2 的节点并且两点之间权值小的点进行连接 ,从而构成一个大的连通分量 ,最后连接同一个连通分量中仅有的两个度为 1 的节点 , 从而构成一个闭合回路 。

for(;mstcostnum<m;)//第二步是通过连接的方法 , 连接最小生成树中度小于2 的节点
		{
			for(i = 1; i <= m; i++)//标记连通分量 
			{
				if(minstdu[i]==0)
				{
					Connected[i] = i;
				}
				else
				{
					for(j = 1; j <= m; j++)
					{
						if(i!=j&&minst[i][j]!=0)
						{
							if(Connected[i]==0)
							{
								Connected[i] = i;
							}
							Connected[j] = Connected[i];
						}
					}
				}
			}
			for(i = 1; i <= m; i++)
			{
				if(minstdu[i]<2)
				{
					for(j = 1; j <= m; j++)
					{
						if(i!=j && Connected[j]!=Connected[i] && minstdu[j]<2){
							minst[i][j] = graph[i][j];
							minst[j][i] = graph[i][j];
							minstdu[i]++;
							minstdu[j]++;
							mstcostnum++;
							x = Connected[i];
							y = Connected[j];
							for(k = 1; k <= m; k++)
							{
								if(Connected[k]==y)
								{
									Connected[k] = x;
								}
							}
						}
					}
					if(minstdu[i]<2)
					{
						for(j = 1; j <= m; j++)
						{
							if(i!=j && Connected[j]==Connected[i] && minstdu[j]<2)
							{
								minst[i][j] = graph[i][j];
								minst[j][i] = graph[i][j];
								minstdu[i]++;
								minstdu[j]++;
								mstcostnum++;
							}
						}
					}
				}
			}
		}
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

最后通过比较各个顶点的各回路的距离值 ,从而确定最佳闭合回路( 城市序列)。这里的sum[MAX]保存各回路的距离值，例如sum[1]=10表示顶点1的最小生成树生成的回路距离值为10.

for(i = 2, minnum = sum[1]; i<=m; i++)
	{
		if(minnum>sum[i])
		{
			minnum = sum[i];
		}
	} 
	for(i = 1; i<=m; i++){
		if(minnum==sum[i])
		{
			printf("------分析------\n");
			printf("由顶点%d生成的最小生成树求得的路径距离值最小，为%d\n",i,sum[i]);
		}
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

运行测试样例：
//4个顶点，6条权边
4 6
1 2 1
1 4 2
1 3 3
2 3 4
2 4 6
3 4 5
运行结果如下：

--------采用启发式搜索求解TSP问题--------
请输入无向图的顶点的个数与边的个数:
4 6
请输入无向图的每条边的权:
(输入1 2 3表示顶点1与顶点2的边的权为3)
1 2 1
1 4 2
1 3 3
2 3 4
2 4 6
3 4 5
以顶点1构造最小生成树
V1-V2=1
V1-V4=2
V1-V3=3
最小权值之和=6
输出此路径及其距离为：
1->2:1
2->3:4
3->4:5
4->1:2
此路径距离值为：12
以顶点2构造最小生成树
V1-V2=1
V2-V4=2
V2-V3=3
最小权值之和=6
输出此路径及其距离为：
1->2:1
2->4:2
4->3:5
3->1:4
此路径距离值为：12
以顶点3构造最小生成树
V1-V3=3
V3-V2=1
V3-V4=2
最小权值之和=6
输出此路径及其距离为：
1->2:4
2->3:1
3->4:2
4->1:5
此路径距离值为：12
以顶点4构造最小生成树
V1-V4=2
V4-V2=1
V4-V3=3
最小权值之和=6
输出此路径及其距离为：
1->3:5
3->2:4
2->4:1
4->1:2
此路径距离值为：12
------分析------
由顶点1生成的最小生成树求得的路径距离值最小，为12
------分析------
由顶点2生成的最小生成树求得的路径距离值最小，为12
------分析------
由顶点3生成的最小生成树求得的路径距离值最小，为12
------分析------
由顶点4生成的最小生成树求得的路径距离值最小，为12

--------------------------------
Process exited after 36 seconds with return value 0
请按任意键继续. . .

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

附代码及运行文件下载：https://download.csdn.net/download/weixin_44144729/12529074