devbox
码创造者
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

HNU_算法_实验4（2021级）-经典案例2-分支限界法求解TSP问题_基于分支限界法求解tsp等问题

作者：码创造者 | 2024-07-08 14:11:03

赞

踩

基于分支限界法求解tsp等问题

  一、实验名称

分支限界法求解TSP问题；

        问题描述：某售货员要到若干城市去推销商品，已知各城市之间的路程，他要选定一条从驻地出发，经过每个城市一遍，最后回到住地的路线，使总的路程最短。

二、实验目的

        通过上机实验，要求掌握分支限界法求解TSP问题的问题描述、算法设计思想、程序设计。

三、实验原理

        利用分支限界法求解TSP问题，并计算出程序运行所需要的时间。

四、实验步骤

       算法描述：

        解旅行售货员问题的优先队列式分支限界法用优先队列存储活结点表。

活结点m在优先队列中的优先级定义为：活结点m对应的子树费用下界lcost。

        lcost=cc+rcost，其中，cc为当前结点费用，rcost为当前顶点最小出边费用加上剩余所有顶点的最小出边费用和。

        优先队列中优先级最大的活结点成为下一个扩展结点。

        排列树中叶结点所相应的载重量与其优先级（下界值）相同，即：叶结点所相应的回路的费用(bestc)等于子树费用下界lcost的值。

       

        

五、关键代码

1.排列树的节点定义

  1. struct node
  2. {
  3.     int cl;//当前走过的路径长度
  4.     int id;//处理的第几个城市
  5.     int x[1000];//记录当前路径，下标从1开始
  6.  
  7.     node() {}
  8.     node(int cl_,int id_)
  9.     {
  10.         cl=cl_;
  11.         id=id_;
  12.         memset(x,0,sizeof(x));
  13.     }
  14. };

2.用于构建最小堆（优先队列）

  1. struct cl_cmp {
  2.     //当前路径长度短的优先级高
  3.     bool operator()(node n1, node n2)
  4.     {
  5.         return n1.cl > n2.cl;
  6.     }
  7. };
  8.  
  9. void bfs(int n,int &bestl,vector<int> &bestx,vector<vector<int> > &m)
  10. {
  11.     //选用最小堆
  12.     priority_queue<node,vector<node>,cl_cmp> q;
  13.     //创建一个节点，从该节点开始，因为1是固定位，其实是从1开始探索
  14.     node temp(0,2);
  15.     //初始化解向量
  16.     for(int i=1; i<=n; ++i)
  17.         temp.x[i]=i;
  18.     q.push(temp);
  19.     node cur;//当前节点，也就是活节点
  20.     int t;
  21.     while(!q.empty())
  22.     {
  23.         cur=q.top();
  24.         q.pop();
  25.         t=cur.id;
  26.         if(t==n)
  27.         {
  28.             //满足约束条件，有路径
  29.             //检测图G是否存在一条从顶点x[n-1]到顶点x[n]的边和一条从顶点x[n]到顶点1的边
  30.             if(m[cur.x[t-1]][cur.x[t]]!=INF&&m[cur.x[t]][1]!=INF)
  31.             {
  32.                 if(cur.cl+m[cur.x[t-1]][cur.x[t]]+m[cur.x[t]][1]<bestl)
  33.                 {
  34.                     //更新最优解和最优路径
  35.                     bestl=cur.cl+m[cur.x[t-1]][cur.x[t]]+m[cur.x[t]][1];
  36.                     for(int i=1; i<=n; ++i)
  37.                         bestx[i]=cur.x[i];
  38.                 }
  39.             }continue;
  40.         }
  41.         //大于等于最优路径，没必要继续探索了，从下一个节点开始
  42.         if(cur.cl>=bestl)
  43.             continue;
  44.         //从当前节点开始探索t-1 -> t,t+1,t+2...
  45.         for(int j=t; j<=n; ++j)
  46.         {
  47.             //满足约束条件和限界条件
  48.             if(m[cur.x[t-1]][cur.x[j]]!=INF&&cur.cl+m[cur.x[t-1]][cur.x[j]]<bestl)
  49.             {
  50.                 temp=node(cur.cl+m[cur.x[t-1]][cur.x[j]],t+1);
  51.                 //如果找到了一个下级节点，那么该节点到现在为止和同级的节点路径相同，除了当前这一级的不同
  52.                 for(int k=1; k<=n; ++k)
  53.                     temp.x[k]=cur.x[k];
  54.                 swap(temp.x[t],temp.x[j]);
  55.                 q.push(temp);
  56.             }
  57.         }
  58.     }
  59. }

3.不同规模案例生成

        顶点个数为n，所以可能有n*n个权重。

        但是可能有一些节点之间无可达边，所以下面还设置了一个参数probability，作为矩阵中不可达边的概率，来设置权重矩阵的“稀疏”程度。

        而且由于INF的存在，所以权重并不能无限制的大。而且我们也没有需求将这类值设的很大（不影响复杂度），不妨限制在0-100之间的整数。

  1. // 设置概率值，矩阵中不可达边的概率 
  2.    		 double probability = 0.1;
  3. 		// c数组 不妨设置权重范围为(a,b] 
  4. 		int a=0,b=100;
  5. 		for(int i=1;i<=n;i++){
  6. 			for(int j=1;j<=n;j++) {
  7. 				 // 生成一个介于0到1之间的随机小数
  8.     			double randomValue = static_cast<double>(std::rand()) / RAND_MAX;
  9.     			 if (randomValue < probability) {
  10.         			// 有probability的概率输出INF
  11.        				 out<< INF <<' ';
  12.    				}
  13. 				else {
  14. 			        // 有(1 - probability)的概率输出(a,b]间的整数
  15. 			        out<< (rand() % (b-a))+ a + 1<<' ';
  16.     			}
  17. 			}
  18. 			out<<'\n';
  19. 		}

六、测试结果

时间复杂性：O(n!)

        分支限界法解决TSP，搜索树的节点数取决于图中城市的数量。在每一层，都需要考虑从当前城市到所有其他未访问的城市的分支，因此搜索树的规模呈指数级增长。

        具体来说，TSP问题的时间复杂度可以表示为 O(n!)，其中 n 是城市的数量。这是因为在每个决策点，需要考虑 n 种可能的下一步选择，而搜索树的深度为 n。

        然而，通过一些优化策略，如减枝和启发式方法，来尽量减少搜索树的规模，以提高算法的效率。在实践中，TSP问题的解决往往依赖于问题的具体实例和算法的实现方式。

n从10-500，每次递增10的测试结果：

自定义输入n的数值的测试结果：

七、实验心得

        通过这次实验，我更为掌握了分支限界法求解TSP问题，并且自己生成案例并测试运行时间的过程中，熟悉了随机化算法和运行时间的计算。

​         实验可改进的地方：随机化过程的加入可能使得不同规模的测试数据与理论值有偏差，可以通过每个输入规模多次测试来减小误差。

八、完整代码

  1. #include <iostream>
  2. #include <cstring>
  3. #include <queue>
  4. #include <fstream>
  5. #include <vector>
  6. #include <windows.h>
  7. #include <time.h>
  8. #define INF 1e7
  9. using namespace std;
  10.  
  11.  
  12.  
  13. //排列树的节点定义
  14. struct node
  15. {
  16.     int cl;//当前走过的路径长度
  17.     int id;//处理的第几个城市
  18.     int x[501];//记录当前路径，下标从1开始
  19.  
  20.     node() {}
  21.     node(int cl_,int id_)
  22.     {
  23.         cl=cl_;
  24.         id=id_;
  25.         memset(x,0,sizeof(x));
  26.     }
  27. };
  28.  
  29.  
  30.  
  31. //用于构建最小堆
  32. struct cl_cmp {
  33.     //当前路径长度短的优先级高
  34.     bool operator()(node n1, node n2)
  35.     {
  36.         return n1.cl > n2.cl;
  37.     }
  38. };
  39.  
  40. void bfs(int n,int &bestl,vector<int> &bestx,vector<vector<int> > &m)
  41. {
  42.     //选用最小堆
  43.     priority_queue<node,vector<node>,cl_cmp> q;
  44.     //创建一个节点，从该节点开始，因为1是固定位，其实是从1开始探索
  45.     node temp(0,2);
  46.     //初始化解向量
  47.     for(int i=1; i<=n; ++i)
  48.         temp.x[i]=i;
  49.     q.push(temp);
  50.     node cur;//当前节点，也就是活节点
  51.     int t;
  52.     while(!q.empty())
  53.     {
  54.         cur=q.top();
  55.         q.pop();
  56.         t=cur.id;
  57.         if(t==n)
  58.         {
  59.             //满足约束条件，有路径
  60.             //检测图G是否存在一条从顶点x[n-1]到顶点x[n]的边和一条从顶点x[n]到顶点1的边
  61.             if(m[cur.x[t-1]][cur.x[t]]!=INF&&m[cur.x[t]][1]!=INF)
  62.             {
  63.                 if(cur.cl+m[cur.x[t-1]][cur.x[t]]+m[cur.x[t]][1]<bestl)
  64.                 {
  65.                     //更新最优解和最优路径
  66.                     bestl=cur.cl+m[cur.x[t-1]][cur.x[t]]+m[cur.x[t]][1];
  67.                     for(int i=1; i<=n; ++i)
  68.                         bestx[i]=cur.x[i];
  69.                 }
  70.             }continue;
  71.         }
  72.         //大于等于最优路径，没必要继续探索了，从下一个节点开始
  73.         if(cur.cl>=bestl)
  74.             continue;
  75.         //从当前节点开始探索t-1 -> t,t+1,t+2...
  76.         for(int j=t; j<=n; ++j)
  77.         {
  78.             //满足约束条件和限界条件
  79.             if(m[cur.x[t-1]][cur.x[j]]!=INF&&cur.cl+m[cur.x[t-1]][cur.x[j]]<bestl)
  80.             {
  81.                 temp=node(cur.cl+m[cur.x[t-1]][cur.x[j]],t+1);
  82.                 //如果找到了一个下级节点，那么该节点到现在为止和同级的节点路径相同，除了当前这一级的不同
  83.                 for(int k=1; k<=n; ++k)
  84.                     temp.x[k]=cur.x[k];
  85.                 swap(temp.x[t],temp.x[j]);
  86.                 q.push(temp);
  87.             }
  88.         }
  89.     }
  90. }
  91.  
  92. int main(){
  93. 	ofstream out1("output.txt");
  94. 	int n=500;
  95. 	while(n-=10){
  96. //		//生成规模为n的随机数 
  97. //		cout<<"请输入顶点个数n："<<endl; 
  98. //		int n;
  99. //		cin>>n;
  100. 		ofstream out("input1.txt");
  101. 		out<<n<<'\n';
  102. 		srand((unsigned)time(NULL));
  103. 		
  104.  
  105.     	// 设置概率值，矩阵中不可达边的概率 
  106.    		 double probability = 0.1;
  107.  
  108. 		// c数组 不妨设置权重范围为(a,b] 
  109. 		int a=0,b=100;
  110. 		int i,maxi,mini;
  111. 		LARGE_INTEGER nFreq,nBegin,nEnd;
  112. 		double time; 
  113. 		QueryPerformanceFrequency(&nFreq);	
  114. 		QueryPerformanceCounter(&nBegin);
  115. 		for(int i=1;i<=n;i++){
  116. 			for(int j=1;j<=n;j++) {
  117. 				 // 生成一个介于0到1之间的随机小数
  118.     			double randomValue = static_cast<double>(std::rand()) / RAND_MAX;
  119.     			 if (randomValue < probability) {
  120.         			// 有probability的概率输出INF
  121.        				 out<< INF <<' ';
  122.    				}
  123. 				else {
  124. 			        // 有(1 - probability)的概率输出(a,b]间的整数
  125. 			        out<< (rand() % (b-a))+ a + 1<<' ';
  126.     			}
  127. 			}
  128. 			out<<'\n';
  129. 		}
  130. 		QueryPerformanceCounter(&nEnd);
  131. 		time=(double)(nEnd.QuadPart-nBegin.QuadPart)/(double)nFreq.QuadPart; 
  132. 		
  133. 		cout<<"生成时间:"<<time<<endl;
  134. 		out.close();
  135. 	
  136.  
  137. 		
  138. 		ifstream in("input1.txt");
  139. 		
  140. 		in>>n;
  141. //		cout<<"n= "<<n<<endl; 
  142.  
  143.     	
  144. 		vector<vector<int> > m(n+1, vector<int>(n+1));
  145. 		vector<int> bestx(n+1);
  146. 		int bestl=INF;//最优解长度
  147. 		for(i=1;i<=n;i++){
  148. 			for(int j=1;j<=n;j++){
  149. 				in>>m[i][j];
  150. //			cout<<m[i][j]<<" ";
  151. 			}
  152. //			cout<<endl;
  153. 		}
  154.  
  155. 		QueryPerformanceFrequency(&nFreq);	
  156. 		QueryPerformanceCounter(&nBegin);
  157. 		bfs(n, bestl, bestx, m);    	
  158. 		QueryPerformanceCounter(&nEnd);
  159. 		time=(double)(nEnd.QuadPart-nBegin.QuadPart)/(double)nFreq.QuadPart; 
  160. 		cout<<"最优值为："<<bestl<<endl;
  161.     	cout<<"最优解为：";
  162.     	for(int i=1; i<=n; ++i)
  163.         	cout<<bestx[i]<<" ";
  164.    		cout<<bestx[1]<<endl;		
  165. 		cout<<"查询时间:"<<time<<endl<<endl;
  166. 		out1<<n<<' '<<time<<endl;
  167. 		in.close();		
  168. 	}
  169. 	out1.close();
  170. 	return 0;
  171. }

九、绘图代码

  1. import matplotlib.pyplot as plt
  2.  
  3. def read_file(filename):
  4.     data = []
  5.     with open(filename, 'r') as file:
  6.         for line in file:
  7.             x, y = map(float, line.split())
  8.             data.append((x, y))
  9.     return data
  10.  
  11. # 读取文件的数据
  12. file3_data = read_file('F:\\3-CourseMaterials\\3-1\\3-算法设计与分析\实验\lab4\\1-code\\2-分支限界法求解TSP问题\\output.txt')
  13.  
  14. # 分别提取 x 和 y 的值
  15. file3_x, file3_y = zip(*file3_data)
  16. print(file3_x)
  17. print(file3_y)
  18.  
  19. # 绘制图形，指定不同颜色
  20. # plt.plot(file1_x, file1_y, label='Solution 1', color='red')
  21. # plt.plot(file2_x, file2_y, label='Solution 2', color='green')
  22. plt.plot(file3_x, file3_y, label='Solution 1', color='red')
  23.  
  24. # 添加图例、标签等
  25. plt.legend()
  26. plt.title('Data from Three Files')
  27. plt.xlabel('X-axis')
  28. plt.ylabel('Y-axis')
  29.  
  30. # 显示图形
  31. plt.show()


                      

声明：本文内容由网友自发贡献，转载请注明出处：【wpsshop】
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号