算法设计与分析
学习基本的统计分析方法,如假设检验和回归分析 #生活技巧# #工作学习技巧# #数字技能学习#
旅行商问题,即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; }
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112结果:
四、回溯法
建立一棵排列决策树,树的深度是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问题。
代码:
#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结果:
六、模拟退火
计算方法:
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结果:
网址:算法设计与分析 https://www.yuejiaxmz.com/news/view/190011
相关内容
【算法设计与分析】递推算法《数据结构与算法分析
Matlab数据分析与多项式计算
常用计算机维修方法有哪些,计算机常见硬件故障的诊断及其处理分析
《既有建筑节能改造碳排放计算标准和分析方法》.pdf
办公室计算机的日常维护分析
ssm健康饮食推荐系统分析与设计 毕业设计
闲置物品交易系统的分析与设计(项目文档)
建筑环境设计与生活空间关系分析
项目分析:大学生个人财务管理系统的设计与实现