算法设计与分析---分支界限法实验报告

《算法设计与分析》实验报告实验四分治限界法报告书姓名指导教师学号日期班级实验内容1.迷宫最短路径在下图中，请使用广度搜索求出a到b的最短路径，有色区域为不可通过区域。2.树上最短路径dashen是个牛人。很多人都想认识dashen，但没有这个机会，于是shen粉们便想了一个方法，计算自己与dashen的ACM距离，因此很多人都去参加ACM，而ACM因此也改名为ACM国际水赛。每个ACM有n个组，每组3个人。同组的3个人都是队友。大家都想知道自己与dashen的最小距离是多少。dashen与自己的最小距离当然是0。dashen的队友和dashen的最小距离是1。dashen的队友的队友和dashen的最小距离是2……以此类推。如果实在和dashen没有关系的只好输出undefined了。第一行读入n。表示有n个组。1≤n≤100接下来n行，每行有3个名字，名字之间用空格隔开。每个名字的开头都是大写的。每行输出一个名字，名字后面空格后输出数字a或者字符串undefined，a代表最小距离。名字按字典序输出。[SampleInput]7dashenOparinToropovAyzenshteynOparinSamsonovAyzenshteynChevdarSamsonovFominykhdashenOparinDublennykhFominykhIvankovBurmistrovDublennykhKurpilyanskiyCormenLeisersonRivest[SampleOutput]Ayzenshteyn2Burmistrov3Chevdar3CormenundefinedDublennykh2Fominykh1dashen0Ivankov2Kurpilyanskiy3LeisersonundefinedOparin1RivestundefinedSamsonov2Toropov1实验目的1）掌握学习什么是分支界限法。2）掌握学习BFS（宽度优先搜索）的思想过程以及编码实现。3）掌握学习简单的BFS题目如何去思考并解决实施。4）学习培养基础的快速变成能力、独立思考恩能够立与解决bug的能力。实验过程和步骤1.迷宫最短路径1.2解题思路迷宫搜索最短路径，主要考察的就是最简单裸的BFS。BFS只要掌握如何标记好数组、边界的考虑、出队进队就好了。如何保存搜索的层数？每一次节点扩散层，标记的层数值都是当前层的+1即可。至于写BFS的写法。步骤都是一样的：放第一个进队，然后出队、扩散开进队并标记、出队......循环下去直到队空。写法太基础就不讲解了。1.2测试样例73246..#......##.......#.....##..#...#..###....###....1.3程序运行情况1.4程序源码（含注释）#includebits/stdc++.husingnamespacestd;#defineinf999intn;//行数intsx,sy;//起点intgx,gy;//终点chare[inf][inf];//地图intbook[inf][inf];//标记地图intpos[4][2]={-1,0,1,0,0,1,0,-1};//方位，上下右左voidread()//输入数据{printf(inputtherowofthemap:);scanf(%d,&n);printf(nowinputthepoint:\n);scanf(%d%d%d%d,&sx,&sy,&gx,&gy);//输入下标自1开始sx--;//计算下标从0开始sy--;gx--;gy--;printf(inputthemapnow:\n);for(inti=0;in;i++)scanf(%s,e[i]);printf(\n);memset(book,0,sizeofbook);//初始化}structNode//节点{intx,y;Node(inti,intj):x(i),y(j){}};boolislegal(intx,inty)//判断是否合法{if(x0||x=n||y0||y=n)returnfalse;returntrue;}voidbfs()//方便快捷{queueNodeq;while(!q.empty())q.pop();//初始化q.push(Node(sx,sy));//放入首节点book[sx][sy]=0;//标记while(!q.empty()){Nodet=q.front();q.pop();//取出节点inttag=book[t.x][t.y];if(t.x==gx&&t.y==gy)break;//提前结束for(inti=0;i4;i++){intx=t.x+pos[i][0];inty=t.y+pos[i][1];if(islegal(x,y)&&e[x][y]=='.'&&!book[x][y])//放入未越界、可走、未走过的{q.push(Node(x,y));book[x][y]=tag+1;}}}}voidoutput(){printf(---------------------\n);inti,j;for(i=0;in;i++){for(j=0;jn;j++)printf(%d,book[i][j]);printf(\n);}}intmain(){read();//输入bfs();output();//输出return0;}2树上最短路径2.1解题思路问题问每个人和dashen的距离，组员的距离为1。也就是说，人与人之间的距离都是通过“组员”来不断量化的。那么可以想到，组员之间可以画一条边，问题问的整个人际之间的图建好之后，将人看为节点，求出每个节点与某个定点的最短距离。这个图的遍历+定点最短距离问题显然用BFS很好解决。问题的难点：1）映射字符串到id的关系，我用的是STL的map容器解决。2）保存点之间边的关系，本来用的是矩阵保存，但是写到后来很麻烦，就用邻接表保存3）输出的时候有点麻烦2.2测试样例7dashenOparinToropovAyzenshteynOparinSamsonovAyzenshteynChevdarSamsonovFominykhdashenOparinDublennykhFominykhIvankovBurmistrovDublennykhKurpilyanskiyCormenLeisersonRivest2.3程序运行情况2.4程序源码（含注释）#includebits/stdc++.husingnamespacestd;#defineinf999#defineINF999999999intn,num;//行数，以及不重复人数intorigin;//起点，即dashen的标号intbook[inf];//标记vectorintedge[inf];//每个点的边集structStudent{//学生类,下标自1始stringname;intid;intrank;voidset(strings,inti){name=s;id=i;rank=INF;//所有人的距离默认无穷大}booloperator(constStudent&t)const{namet.name;}}student[inf];voidread()//输入数据{num=0;//人数初始化memset(book,0,sizeofbook);//初始化标记coutinputthenumofthegroups:;cinn;coutnowinputtheeachgroupmates:\n;mapstring,intm;m.clear();strings[3];//临时存放for(inti=0;in;i++){for(intj=0;j3;j++)//读入点，建点{cins[j];if(m[s[j]]==0)//没出现过就赋予标号以及存储名字{m[s[j]]=++num;student[num].set(s[j],num);//存储此人id和名字}if(s[j]==dashen)origin=m[s[j]];}for(intj=0;j2;j++)//建图for(intk=j+1;k3;k++){inta=m[s[j]];intb=m[s[k]];edge[a].push_back(b);//加入边集edge[b].push_back(a);}}printf(\n);}voidbfs()//根据id进行bfs{queueintq;while(!q.empty())q.pop();//初始化q.push(origin);//放入首节点book[origin]=1;//标记走过student[origin].rank=0;//dashen是0while(!q.empty()){intv=q.front();q.pop();//取出节点intlen=edge[v].size();for(inti=0;ilen;i++){intu=edge[v][i];student[u].rank=min(student[v].rank+1,student[u].rank);if(!book[u]){q.push(u);book[u]=1;}}}}voidoutput(){printf(---------------------\n);inti;sort(student+1,student+num+1);//排序for(i=1;i=num;i++){coutstudent[i].name;intid=student[i].id;if(student[i].rank==INF)coutundefinedendl;elsecoutstudent[i].rankendl;}}intmain(){read();//输入bfs();output();//输出return0;}