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

《算法设计与分析---分支界限法实验报告.docx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、《算法设计与分析》实验报告实验四分治限界法报告书姓名指导教师学号日期班级实验内容1.迷宫最短路径在下图中，请使用广度搜索求出a到b的最短路径，有色区域为不可通过区域。2.树上最短路径dashen是个牛人。很多人都想认识dashen，但没有这个机会，于是shen粉们便想了一个方法，计算自己与dashen的ACM距离，因此很多人都去参加ACM，而ACM因此也改名为ACM国际水赛。每个ACM有n个组，每组3个人。同组的3个人都是队友。大家都想知道自己与dashen的最小距离是多少。dashen与自己的最小距离当然是0。dash

2、en的队友和dashen的最小距离是1。dashen的队友的队友和dashen的最小距离是2……以此类推。如果实在和dashen没有关系的只好输出undefined了。第一行读入n。表示有n个组。1≤n≤100接下来n行，每行有3个名字，名字之间用空格隔开。每个名字的开头都是大写的。每行输出一个名字，名字后面空格后输出数字a或者字符串undefined，a代表最小距离。名字按字典序输出。[SampleInput]7dashenOparinToropovAyzenshteynOparinSamsonovAyzenshtey

3、nChevdarSamsonovFominykhdashenOparinDublennykhFominykhIvankovBurmistrovDublennykhKurpilyanskiyCormenLeisersonRivest[SampleOutput]Ayzenshteyn2Burmistrov3Chevdar3CormenundefinedDublennykh2Fominykh1dashen0Ivankov2Kurpilyanskiy3LeisersonundefinedOparin1Rivestundefine

4、dSamsonov2Toropov1实验目的1）掌握学习什么是分支界限法。2）掌握学习BFS（宽度优先搜索）的思想过程以及编码实现。3）掌握学习简单的BFS题目如何去思考并解决实施。4）学习培养基础的快速变成能力、独立思考恩能够立与解决bug的能力。实验过程和步骤1.迷宫最短路径1.2解题思路迷宫搜索最短路径，主要考察的就是最简单裸的BFS。BFS只要掌握如何标记好数组、边界的考虑、出队进队就好了。如何保存搜索的层数？每一次节点扩散层，标记的层数值都是当前层的+1即可。至于写BFS的写法。步骤都是一样的：放第一个进队，然

5、后出队、扩散开进队并标记、出队......循环下去直到队空。写法太基础就不讲解了。1.2测试样例73246..#......##.......#.....##..#...#..###....###....1.3程序运行情况1.4程序源码（含注释）#include"bits/stdc++.h"usingnamespacestd;#defineinf999intn;//行数intsx,sy;//起点intgx,gy;//终点chare[inf][inf];//地图intbook[inf][inf];//标记地图intpos[

6、4][2]={-1,0,1,0,0,1,0,-1};//方位，上下右左voidread()//输入数据{printf("inputtherowofthemap:");scanf("%d",&n);printf("nowinputthepoint:");scanf("%d%d%d%d",&sx,&sy,&gx,&gy);//输入下标自1开始sx--;//计算下标从0开始sy--;gx--;gy--;printf("inputthemapnow:");for(inti=0;i

7、]);printf("");memset(book,0,sizeofbook);//初始化}structNode//节点{intx,y;Node(inti,intj):x(i),y(j){}};boolislegal(intx,inty)//判断是否合法{if(x<0

8、

9、x>=n

10、

11、y<0

12、

13、y>=n)returnfalse;returntrue;}voidbfs()//方便快捷{queueq;while(!q.empty())q.pop();//初始化q.push(Node(sx,sy));//放入首节

14、点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;i<4;i++){intx=t.x+pos[i][0