《算法设计与分析》实验报告

《算法设计与分析》实验报告学号：姓名：日期：得分：一、实验内容：TSP问题。二、所用算法的基本思想及复杂度分析：1、蛮力法基本思想找出所有可能的旅行路线，即以次考虑图中所有顶点的全排列，从中选取路径长度最短的哈密顿回路(也称为简单回路)。复杂度分析蛮力法求解TSP问题必须依次考察顶点集合的所有全排列，从中找出路径长度最短的简单回路，因此，其时间下界是Q(n!)。2、动态规划法基本思想TSP问题满足最优性原理。对于图G=(V,E)，假设从顶点i出发，令V’=V-I，则d(i,V’)表示从顶点i出发经过V’中各个顶点一次且仅一次，最后回到出发点i的最短路径长度。显然初始子问题为d(k,{})，即从顶点i出发只经过顶点k回到顶点i。现在考虑原问题的一部分，d(k,V’-{k})表示从顶点k出发经过V’-{k}中各个顶点一次且仅一次，最后回到出发点i的最短路径长度，则：d(k,{})=Ckid(i,V’)=min{Cik+d(k,V’-{k})}(keV,)复杂度分析算法需要对顶点集合{1,2，…，n-1}的每一个子集进行操作，因此，时间复杂性为Q(2n)。3、回溯法1）基本思想回溯法求解TSP问题，首先把所有的顶点的访问标志初始化为0,然后在解空间树中从根节点出发开始搜索，如果从根节点到当前结点对应一个部分解，即满足上述约束条件，则在当前结点处选择第一棵子树继续搜索，否则，对当前子树的兄弟结点进行搜索，如果当前结点的所有子树都已尝试过并且发生冲突，则回溯到当前结点的父节点。采用邻接矩阵mp[n][n]存储顶点之间边的情况，为避免在函数间传递参数，将数组mp设置为全局变量，设数组x[n]表示哈密顿回路经过的顶点。2）复杂度分析在哈密顿回路的可能解中，考虑到约束条件xj!=xj（1<=IJ<=n,i!=j）,则可能解应该是（1,2,…,n）的一个排列，对应的解空间树种至少有n!个叶子结点，每个叶子结点代表一种可能解。当找到可行的最优解时，算法停止。根据递归条件不同时间复杂度也会不同，这里为O（n！）。4、分支限界法1）基本思想首先确定目标函数的界[down,up]，可以用贪心法求得TSP问题的一个上界。对于无向图的代价矩阵，把矩阵中的每一行最小的元素相加，可以得到一个简单的下界。但还有一个信息量更大的下界：考虑一个TSP问题的完整解，在每条路径上，每个城市都有两条邻接边，一条是进入这个城市，另一条是离开这个城市的，那么，如果把矩阵中每一行最小的两个元素相加再除以2,假设图中的所有代价都是整数，在对这个结果向上取整，就得到了一个合理的下界。强调的是，这个解可能不是一个可行解（可能没有构成哈密顿回路），但给出了一个参考下界。2）复杂度分析目标函数（限界函数），lb分为三部分，第一部分是经过路径的长度相加的2倍，加上第二部分离着路径首尾节点最近的距离相加（不在已知路径上的），加上第三部分除了路径上节点，矩阵中两个最短的距离相加，最后这三部分和相加，得到的结果除以2便是每个节点的限界值。由于限界函数的不同，下界为O3），上界为O（25）。三、源程序及注释:1、蛮力法intmin(inta[],intcolable[],intn,introw[]){intj=0,m=a[0],k=0;while(colable[j]==0||row[j]==0){j++；m=a[j];}//求最短距离for(;j<n;j++){if(colable[j]==1&&row[j]==1)//节点没有被访问{if(m>=a[j]){m=a[j];//m始终保持最短距离k=j;}}}returnk;}intmain(){inti,j,s=0;intn;while(scanf("%d”,&n)){intcolable[n];colable[0]=0;〃对各列允许矩阵进行赋值for(i=1;i<n;i++){colable[i]=1;}introw[n];for(i=0;i<n;i++){row[i]=1;}inta[n][n];for(i=0;i<n;i++){for(j=0;j<n;j++){if(i!=j)scanf("%d”,&a[i][j]);elsea[i][j]=inf;}}i=0;while(row[i]==1){j=min(a[i],colable,n,row);row[i]=0;colable[j]=0;s=s+a[i][j];i=j;}printf("%d\n”,s);

return0;2、动态规划法classTspprivate:intcity_number;〃城市个数int**distance;//城市距离矩阵intcity_number;〃城市个数int**distance;//城市距离矩阵int**process;〃求最短路径的过程矩阵public:Tsp(intcity_number);〃构造函数voidgetShoretstDistance();〃动态规划法求最短路径};//构造函数Tsp::Tsp(intcity_num)Tsp(intcity_number);〃构造函数inti=0,j=0;city_number=city_num;//初始化城市距离矩阵distance=newint*[city_number];for(i=0;i<city_number;i++){distance[i]=newint[city_number];for(j=0;j<city_number;j++)if(i==j)distance[i][j]=0;elsecin>>distance[i][j];}//生成过程矩阵process=newint*[city_number];for(i=0;i<city_number;i++){process[i]=newint[1<<(city_number-1)];}}〃动态规划法求最短路径voidTsp::getShoretstDistance(){inti,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<<process[0][(1<<(city_number-1))-1]<<endl;}//主函数intmain(void){intcity_number;while(cin>>city_number){Tsptsp(city_number);//初始化城市代价矩阵tsp.getShoretstDistance();//求出最短路径

return0;}3、回溯法#defineMAX100usingnamespacestd;//城市个数//城市间距离〃记录路径//记录最优路径〃最短路径长〃当前路径长intn;inta[MAX][MAX];intx[MAX];intbestx[MAX]={0};intbestp=63355;intcp=0;voidbackpack(intt){//城市个数//城市间距离〃记录路径//记录最优路径〃最短路径长〃当前路径长if(t>n){if((a[x[n]][1])&&(a[x[n]][1]+cp<bestp)){bestp=a[x[n]][1]+cp;for(inti=1;i<=n;i++){bestx[i]=x[i];}}}else{for(inti=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]];backpack(t+1);cp-=a[x[t-1]][x[t]];swap(x[t],x[i]);}intmain(){cin>>n;//顶点数for(inti=1;i<=n;i++){x[i]=i;}for(inti=1;i<=n;i++){for(intj=1;j<=n;j++){if(i==j){a[i][j]=0;}else{cin>>a[i][j];}}}backpack(2);cout<<bestp<<endl;return0;}4、分支限界法#defineINF0x3f3f3f3fintn;intmp[100][100];voidin(){scanf("%d”,&n);for(inti=1;i<=n;i++){for(intj=1;j<=n;j++){if(i==j){mp[i][j]=INF;continue;}scanf("%d”,&mp[i][j]);}}}structnode{intvisp[22];//标记哪些点走了intst;//起点intst_p;//起点的邻接点inted;//终点inted_p;//终点的邻接点intk;//走过的点数intsumv;//经过路径的距离intlb;//目标函数的值booloperator<(constnode&p)const{returnlb>p.lb;}};priority_queue<node>q;intlow,up;intinq[22];〃确定上界intdfs(intu,intk,intl){if(k==n)returnl+mp[u][1];intminlen=INF,p;for(inti=1;i<=n;i++){if(inq[i]==0&&minlen>mp[u][i])/*取与所有点的连边中最小的边*/{minlen=mp[u][i];p=i;}}inq[p]=1;returndfs(p,k+1,l+minlen);}intget_lb(nodep){intret=p.sumv*2;//路径上的点的距离intmin1=INF,min2=INF;//起点和终点连出来的边for(inti=1;i<=n;i++){if(p.visp[i]==0&&min1>mp[i][p.st]){min1=mp[i][p.st];}}ret+=min1;for(inti=1;i<=n;i++){if(p.visp[i]==0&&min2>mp[p.ed][i]){min2=mp[p.ed][i];}}ret+=min2;for(inti=1;i<=n;i++){if(p.visp[i]==0){min1=min2=INF;for(intj=1;j<=n;j++){if(min1>mp[i][j])min1=mp[i][j];}for(intj=1;j<=n;j++){if(min2>mp[j][i])min2=mp[j][i];}ret+=min1+min2;}}returnret%2==0?(ret/2):(ret/2+1);}voidget_up(){inq[1]=1;up=dfs(1,1,0);}voidget_low(){low=0;for(inti=1;i<=n;i++){/*通过排序求两个最小值*/intmin1=INF,min2=INF;inttmpA[22];for(intj=1;j<=n;j++){tmpA[j]=mp[i][j];}sort(tmpA+1,tmpA+1+n);//对临时的数组进行排序low+=tmpA[1];}}intsolve(){/*贪心法确定上界*/get_up();/*取每行最小的边之和作为下界*/get_low();/*设置初始点,默认从1开始*/nodestar;star.st=1;star.k=1;for(inti=1;i<=n;i++)star.visp[i]=0;star.visp[1]=1;star.sumv=0;star.lb=low;/*ret为问题的解*/intret=INF;q.push(star);while(!q.empty()){nodetmp=q.top();q.pop();if(tmp.k==n-1){/*找最后一个没有走的点*/intp;for(inti=1;i<=n;i++){if(tmp.visp[i]==0){p=i;break;}}intans=tmp.sumv+mp[p][tmp.st]+mp[tmp.ed][p];nodejudge=q.top();/*如果当前的路径和比所有的目标函数值都小则跳出*/if(ans<=judge.lb){ret=min(ans,ret);break;}/*否则继续求其他可能的路径和，并更新上界*/else{up=min(up,ans);ret=min(ret,ans);continue;}}/*当前点可以向下扩展的点入优先级队列*/nodenext;for(inti=1;i<=n;i++){if(tmp.visp[i]==0){next.st=tmp.st;/*更新路径和*/next.sumv=tmp.sumv+mp[tmp.ed][i];/*更新最后一个点*/next.ed=i;/*更新顶点数*/next.k=tmp.k+1;/*更新经过的顶点*/for(intj=1;j<=n;j++)next.visp[j]=tmp.visp[j];next.visp[i]=1;/*求目标函数*/next.lb=get_lb(next);/*如果大于上界就不加入队列*/if(next.lb>up)continue;q.push(next);}}}returnret;}intmain(){in();cout<<solve();return0;}四、运行输出结果：蛮力法：R\Users\fcxl9技档伏学\算法设计与分析\T$P-1,exe313616578916

动态规划法:■F:\Users\foclg吱档\大学值法设计与分析1TSP2exe621481o62_y324438861±1±1±621481o62_y324438861±1±1±1±85566693

197—349711IIC.II...J445_y1725_y4-u11±31±6

I|:-:||4

_y-u

I1.2.60427—

I|:-:||I|凸

_y661±_y-u1±6_y1±7I1.2.1±12644546487—II...JII...J464815_y341±I|凸

_y6-u1±711812o464488646333_y7—1_y1±1±1±1±4-I1.2.回溯法:F:\UseUcxI9技档\大学\算法设计与分析'TSP-3.exeooO41-U2II..J65O51O口54^ll■_^^ll■_^-54■-■.J(4)分支限界法：F:\Users\focl9械档\大学\算法设计与分析\TSP-4,exe31536716457489216五、调试和运行程序过程中产生的问题、采取的措施及获得的相关经验教训：1、首先是部分函数以及头文件的使用，在编写程序过程中经常会遇到需要使用自带或额外编写函数，经常需要查询相关资料。2、代码运行时需要对oj上题目所要求的输入输出进行对应修改，否则会得至寸wronganswero3、由于算法的不同需要使用不同的数据结构进行存储，在数据结构的切换时会出现各种各样的问题，查询资料并逐步调试可以解决。六、算法与代码的对应与解释(抽讲)蛮力法：借助矩阵把问题转换为矩阵中点的求解。首先构造距离矩阵，任意节点到自身节点的距离为无穷大。在第一行找到最小项a[1][j]，从而跳转到第j行，再找到最小值a[j][k]，再到第k行进行查找然后构造各行允许数组row[n]={1,1・・・1}，各列允许数组colable[n]={0,1,1・・・.1}，其中1表示允许访问，即该节点未被访问；0表示不允许访问，即该节点已经被访问。如果改行或该列不允许访问，跳过该点访问