算法设计与分析

发布时间：2024-11-22 11:04

学习基本的统计分析方法，如假设检验和回归分析 #生活技巧# #工作学习技巧# #数字技能学习#

旅行商问题，即TSP问题(Travelling Salesman Problem)又译为旅行推销员问题、货郎担问题，是数学领域中著名问题之一。假设有一个旅行商人要拜访n个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。

一、贪心算法

贪心法求解TSP问题有两种贪心策略。

1）最近邻点策略：从任意城市出发，每次在没有到过的城市中选择最近的一个，直到经过了所有的城市，最后回到出发城市。

给定初始的城市a，寻找与其邻接的最短距离的城市b，记录二者之间的路径并增加总路径长度；下一次从城市b开始，寻找与b邻接的最短距离的城市,循环查找，直到找到n-1条路径（n为城市个数），最后加上终点回到起点的边即可。

2）最短链接策略：每次在整个图的范围内选择最短边加入到解集合中，但是，要保证加入解集合中的边最终形成一个哈密顿回路。

首先按照城市之间距离远近进行排列，从距离最近的两个城市开始，如果这两个城市不在一个联通分量中并且度数均小于等于2，那么记录二者之间的路径，将它们划分到一个联通分量并将度数增加1；然后从距离第二小的两个城市开始，重复上述操作直到记录的路径有n-1条，最后找到度数为1的两个城市，作为最后一条路径。

3）“便宜算法”：寻找近似算法求解，需采用近似算法往往需要增加一些限制,以便能够提高计算速度和近似程度:对图中任意的三点构成的三角形，其中任何两边之和大于第三边。

给v1一个自环，得到第一个回路。以后反复执行以下过程:寻找与已得回路距离最近的点，将之插入到回路中;回路以外无结点时终止。
插入办法:设待插入点为j,有两种选择:(1)加入(j,t1)和（j,t)、删除(t,t1）; (2) 加入(j,t2)
和(j,t)、删除(t,t2).
选使回路长度增加量小的那种办法作插入。

（下面采取最近邻点策略）
代码：

#include<stdio.h> #include<iostream> #include<malloc.h> using namespace std; void TSP(int **A,int N,int x) {//从x出发int *flag=(int *)malloc(N*sizeof(int));//标记是否城市走过，初始值设为0，走过设为1int sum=0;int i,j,k,u,v,min;u=x;for(i=0;i<N;i++)//设置flag的初值{flag[i]=0;}u=x;//u是当前城市的位置，现在是设置的x城市flag[u]=1;for(i=0;i<N-1;i++)//走N步回到起点{min=1000;for(j=0;j<N;j++)//比较当前城市距离其他每个城市的距离{if(flag[j]!=1 && A[u][j]<min)//flag查看城市是否已经走过，利用min依次比较{min=A[u][j];v=j;}}sum+=min;flag[v]=1;cout<<u+1<<"-->"<<v+1<<endl;u=v;}sum+=A[v][x];cout<<v+1<<"-->"<<x+1<<endl;cout<<"最短路径长度：";cout<<"sum="<<sum<<endl; } void print(int **A,int N) {for(int i=0;i<N;i++){for(int k=0;k<N;k++)cout<<A[i][k];cout<<endl;} } int main() {cout<<"输入城市个数:"<<endl;int N;cin>>N;int **A=(int **)malloc(N*sizeof(int));if(A==NULL)return 0;cout<<"输入城市之间的距离(0表示城市间不通):"<<endl;for(int i=0;i<N;i++){A[i]=(int*)malloc(N*sizeof(int));for(int k=0;k<N;k++){cin>>A[i][k];}}TSP(A,N,0); }

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869

结果：
在这里插入图片描述
算法复杂度是O(n^2)

（以下采用最短链接策略）
代码：

#include<stdio.h> #include<iostream> #include<malloc.h> using namespace std; pair<int,int> Search(int **A,int N,int *flag,int **AF) { //查找最小边 int min=10e5,a=0,b=0; for(int i=0; i<N; i++) { for(int j=0; j<i; j++) { if(!AF[i][j]&&flag[i]<2&&flag[j]<2&& A[i][j]<min) {//如果这条边没有走过，两边的城市没有同时有两个被走过的边 a=i; b=j; min=A[i][j];//依次比较 } } } flag[a]++; flag[b]++; AF[a][b]=1; return pair<int,int>(a,b); } int TSP(int **A,int N,int *flag,int **AF) { int tsp=0,i,j,k; for(k=0; k<N; k++) {//选择N次最短边 pair<int,int> a=Search(A,N,flag,AF); tsp+=A[a.first][a.second];//每次加入最增的最短边 } return tsp; } int main() {int N;cout<<"输入城市个数:"<<endl;cin>>N;int **A=(int **)malloc(N*sizeof(int));if(A==NULL)return 0;cout<<"输入城市之间的距离(0表示城市间不通):"<<endl;for(int i=0;i<N;i++){A[i]=(int*)malloc(N*sizeof(int));for(int k=0;k<N;k++){cin>>A[i][k];}}int **AF=(int **)malloc(N*sizeof(int));//记是否边走过，初始值设为0，走过设为1if(AF==NULL)return 0;for(int i=0;i<N;i++){AF[i]=(int*)malloc(N*sizeof(int));for(int k=0;k<N;k++){AF[i][k]=0;}}int *flag=(int *)malloc(N*sizeof(int));//标记是否城市走过，初始值设为0，走进去又走出来成为2 for(int i=0;i<N;i++)//设置flag的初值{flag[i]=0;}cout<<"最短路径长度：";cout<<TSP(A,N,flag,AF); }

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566

结果：
在这里插入图片描述
算法复杂度是O(n^2)

二、蛮力法

蛮力法实现TSP问题需要实现所有路径枚举，
计算方法：n个城市，固定1个作为起终点，需要（n-1）!个枚举

三、动态规划法

假设从顶点i出发，令d(i, V’)表示从顶点i出发经过V’中各个顶点一次且仅一次，最后回到出发点i的最短路径长度，开始时，V’＝V－{i}，于是，TSP问题的动态规划函数为：
d(i,V’)=min{cik+d(k,V－{k})}(k∈V’)
d(k,{})=cki(k≠i)

代码：

#include<iostream> #include<iomanip> #include<cmath> using namespace std; #define MAX_IN 10 class Tsp {private:int city_number; //城市个数int **distance;//城市距离矩阵int **process;//求最短路径的过程矩阵public:Tsp(int city_number);//构造函数void correct();//矫正输入的城市代价矩阵void getShoretstDistance();//动态规划法求最短路径 }; //构造函数 Tsp::Tsp(int city_num) {int i=0,j=0;city_number=city_num;//初始化城市距离矩阵distance=new int*[city_number];for(i=0;i<city_number;i++){distance[i]=new int[city_number];for(j=0;j<city_number;j++)cin>>distance[i][j];}//生成过程矩阵process=new int*[city_number];for(i=0;i<city_number;i++){process[i]=new int[1<<(city_number-1)];} } //纠正用户输入的城市代价矩阵 void Tsp::correct() {int i;for(i=0;i<city_number;i++){distance[i][i]=0;} } //动态规划法求最短路径 void Tsp::getShoretstDistance() {int i,j,k;//初始化第一列for(i=0;i<city_number;i++){process[i][0]=distance[i][0];}//初始化剩余列for(j=1;j<(1<<(city_number-1));j++){for(i=0;i<city_number;i++){process[i][j]=0x7ffff;//设0x7ffff为无穷大//对于数字x，要看它的第i位是不是1，通过判断布尔表达式 (((x >> (i - 1) ) & 1) == 1的真值来实现if(((j>>(i-1))&1)==1){continue;}for(k=1;k<city_number;k++){//不能达到k城市if(((j>>(k-1))&1)==0){continue;}if(process[i][j]>distance[i][k]+process[k][j ^ (1 << (k - 1))]){process[i][j]=distance[i][k]+process[k][j ^ (1 << (k - 1))];//cout<<i<<"行"<<j<<"列为："<<process[i][j]<<endl;}}}}cout<<"最短路径长度：";cout<<"sum="<<process[0][(1<<(city_number-1))-1]<<endl; } int main(void) {cout<<"输入城市个数及输入城市之间的距离(0表示城市间不通)"<<endl;int city_number;while(cin>>city_number){ Tsp tsp(city_number);//初始化城市代价矩阵 tsp.correct();//纠正用户输入的代价矩阵 tsp.getShoretstDistance();//求出最短路径 cout<<"---------------------------------------"<<endl;}return 0; }

结果：

在这里插入图片描述

四、回溯法

建立一棵排列决策树，树的深度是5，不能忘记回城市1的路径。树的第i层就是对第i的城市的选择，应该有（n-i+1）个选择，最小问题的剪枝操作：只有当前的值小于已经记录的最小情况时，我们才继续下一层搜索。

代码：

#include<iostream> #include<algorithm> #define MAX 10000 using namespace std; int n; //城市个数 int A[MAX][MAX]; //城市间距离 int x[MAX]; //记录路径 int bestx[MAX] = {0}; //记录最优路径 int bestp = 63355; //最短路径长 int cp = 0; //当前路径长 void backpackTSP(int t){ if(t>n){ //最后一层 if((A[x[n]][1])&&(A[x[n]][1]+cp<bestp)){ //城市相通，并且可以返回起点 bestp = A[x[n]][1]+cp; for(int i = 1;i<=n;i++){ bestx[i] = x[i]; } } }else{ for(int i = t;i<=n;i++){ /*约束为当前节点到下一节点的长度不为0,限界为走过的长度+当前要走的长度之和小于最优长度*/ if((A[x[t-1]][x[i]])&&(cp+A[x[t-1]][x[i]]<bestp)){ swap(x[t],x[i]); cp+=A[x[t-1]][x[t]]; backpackTSP(t+1); cp-=A[x[t-1]][x[t]]; swap(x[t],x[i]); } } } } int main(){ cout<<"输入城市个数:"<<endl; cin>>n; //顶点数 for(int i = 1;i<=n;i++){ x[i] = i; } cout<<"输入城市之间的距离(0表示城市间不通):"<<endl; for(int i = 1;i<=n;i++){ for(int j = 1;j<=n;j++){ cin>>A[i][j]; } } backpackTSP(2);//默认从第一个城市出发，所以从第二层开始 cout<<"最短路径长度"<<bestp<<endl; cout<<"路径为:"<<endl; for(int i = 1;i<=n;i++){ cout<<bestx[i]<<" "; } cout<<bestx[1]; return 0; }

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253

结果：

在这里插入图片描述

时间复杂度是O(n^n)

五、分支限界法

支限界法是利用广度优先搜索的策略或者以最小耗费(最大效益)优先的方式搜索问题的解空间树，对于解空间树中的活节点只有一次机会成为拓展节点，活节点一旦成为扩展节点，那么将一次性产生其所有儿子节点。
对于优先队列式的分支限界法，这些儿子节点中，不可行解或者一定不能成为最优解的儿子节点会被舍弃，其余儿子节点将会按照优先级依次存入一个活节点表(队列) ，此后会挑出活节点表优先级最高的节点作为下次扩展节点，重复此过程，直至找到问题的最优解。
我们需要利用上界和下界来对BFS进行剪枝，通过不断更新上界和下界，尽可能的排除不符合需求的child，以实现剪枝。最终，当上限和下限等同时，我们可以获得最优的BFS解，以解决TSP问题。

代码：

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253

结果：
在这里插入图片描述

六、模拟退火

计算方法：
1.初始化：起始温度，终止温度，温度变化率，最优路径顶点集，最短长度S
2.利用蒙特卡洛法得到一个比较好的初始解
3.当前温度大于终止温度时，利用两点交换法在当前最优路径基础上构造一条新路径，计算新路径的长度S1，差值dE= S1 - S
4.若 dE < 0，当前最优路径更新为新路径，最短长度更新为S1
否则，任意产生一个介于0~1的概率rt,并计算exp(-dE/T),T为当前温度；若exp(-dE/T) > rt, 当前最优路径更新为新路径，最短长度更新为S1，更新温度

代码：

#include<iostream> using namespace std; #include<cstdlib> #include<ctime> #include<vector> #include<cmath> void TSP(vector<vector<int> > W) {int n = W.size();//顶点数量int startT = 3000;//初始温度double endT = 1e-8;//结束温度;科学计数法不需要头文件，字符间不允许有空格double delta = 0.999;//温度变化率int limit = 10000;//概率选择上限,表示已经接近最优解vector<int> path;//最优路径（顶点集）int length_sum = 0;//最优路径长度和//初始化最优路径for(int i = 0; i < n; i++){path.push_back(i);//必须使用入栈}//计算初始最优路径和for(int i = 0; i < n - 1; i++){length_sum += W[path[i]][path[i + 1]];}length_sum += W[path[n - 1]][path[0]]; //使用蒙特卡洛得到一个较好的初始解vector<int> cur = path;int cur_sum = 0;for(int i = 0; i < 8000; i++){for(int k = 0; k < n; k++){int j = rand() % n;swap(cur[k],cur[j]);}//计算初始最优路径和for(int i = 0; i < n - 1; i++){cur_sum += W[cur[i]][cur[i + 1]];}cur_sum += W[cur[n - 1]][cur[0]];if(cur_sum < length_sum){path = cur;length_sum = cur_sum;}}//模拟退火具体过程//1.若是没有此函数，每次执行该代码产生结果都相同，默认1是种子//2.有此函数，若是放在循环内部，则每次循环都设置同一个种子srand((int)(time(NULL)));//确定一个随机种子//退火模拟过程while(startT > endT)//控制循环次数{//cout<<endl<<count++<<endl; //构造新路径vector<int> path_new = path;//为构造一条新路径准备int length_sum_new = 0;//新的路径总和int P_L = 0;//以一定概率接受次数//随机产生两个点，交换，得到一条新的路径int x = rand() % n;int y = rand() % n;while(x == y)//直到随机产生两个互异顶点才继续向下执行{x = rand() % n;y = rand() % n;}swap(path_new[x], path_new[y]);//等价于在原最优路径上随机交换两个互异顶点得到新路径//计算新路径和for(int i = 0; i < n - 1; i++){length_sum_new += W[path_new[i]][path_new[i + 1]];}length_sum_new += W[path_new[n - 1]][path_new[0]];//比较新旧路径，取优double dE = length_sum_new - length_sum;if(dE < 0)//新路径更短，直接取用{path = path_new;length_sum = length_sum_new;}else //新路径不会更优，按一定概率接受{double rd = rand() / (RAND_MAX + 1.0);//随机产生概率：0~1if(exp(- dE / startT) > rd ){path = path_new;length_sum = length_sum_new;P_L++; //一定概率接受次数}}if(P_L == limit)break;//达到限制，直接退出startT *= delta;//温度变化，降低} //输出for(int i = 0; i < n - 1; i++){cout<<path[i]+1<<"-->"<<path[i + 1]+1<<" 权值为： "<<W[path[i]][path[i+1]]<<endl;}cout<<path[n -1]+1<<"-->"<<path[0]+1<< " 权值为： "<<W[path[n - 1]][path[0]]<<endl;cout<<endl<<"最短路径："<<length_sum<<endl; } int main() {int n;vector<vector<int> > w;vector<int> v;cout<<"输入城市数量:"<<endl;cin>>n;cout<<"输入城市之间的距离(0表示城市间不通):"<<endl;//输入方法，先分解为一维向量for(int i=0;i<n;i++){w.push_back(v);}int temp;for(int i=0;i<n;i++){for(int j=0;j<n;j++){cin>>temp;w[j].push_back(temp);}}TSP(w);return 0; }

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188

结果：
在这里插入图片描述