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

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

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

3、h IvankovBurmistrov Dublennykh KurpilyanskiyCormen Leiserson RivestSample OutputAyzenshteyn 2Burmistrov 3Chevdar 3Cormen undefinedDublennykh 2Fominykh 1dashen 0Ivankov 2Kurpilyanskiy 3Leiserson undefinedOparin 1Rivest undefinedSamsonov 2Toropov 1实验目的1）掌握学习什么是分支界限法。2）掌握学习BFS（宽度优先搜索）的思想过程以及编码实现。3）掌握学习

4、简单的BFS题目如何去思考并解决实施。4）学习培养基础的快速变成能力、独立思考恩能够立与解决bug的能力。实验过程和步骤1. 迷宫最短路径1.2 解题思路 迷宫搜索最短路径，主要考察的就是最简单裸的BFS。BFS只要掌握如何标记好数组、边界的考虑、出队进队就好了。 如何保存搜索的层数？每一次节点扩散层，标记的层数值都是当前层的+1 即可。 至于写BFS的写法。步骤都是一样的：放第一个进队，然后出队、扩散开进队并标记、出队.循环下去直到队空。写法太基础就不讲解了。1.2 测试样例73 24 6.#.#.#.#.#.#.#.#.1.3 程序运行情况1.4 程序源码（含注释）#include&quo

5、t;bits/stdc+.h"using namespace std;#define inf 999int n;/行数int sx,sy;/起点int gx,gy;/终点char einfinf;/地图int bookinfinf;/标记地图int pos42=-1,0,1,0,0,1,0,-1;/方位，上下右左void read()/输入数据 printf("input the row of the map:"); scanf("%d",&n); printf("now input the point:n"); s

6、canf("%d%d%d%d",&sx,&sy,&gx,&gy);/输入下标自1开始 sx-;/计算下标从0开始 sy-; gx-; gy-; printf("input the map now:n"); for(int i=0;i<n;i+) scanf("%s",ei); printf("n"); memset(book,0,sizeof book);/初始化struct Node /节点 int x,y; Node(int i,int j):x(i),y(j) ;bool

7、 islegal(int x,int y)/判断是否合法 if(x<0|x>=n|y<0|y>=n)return false; return true;void bfs()/方便快捷 queue<Node>q; while(!q.empty()q.pop();/初始化 q.push(Node(sx,sy);/放入首节点 booksxsy=0;/标记 while(!q.empty() Node t=q.front(); q.pop();/取出节点 int tag=bookt.xt.y; if(t.x=gx&&t.y=gy)break;/提前结束

8、 for(int i=0;i<4;i+) int x=t.x+posi0; int y=t.y+posi1; if(islegal(x,y)&&exy='.'&&!bookxy)/放入 未越界、可走、未走过的 q.push(Node(x,y); bookxy=tag+1; void output() printf("-n"); int i,j; for(i=0;i<n;i+) for(j=0;j<n;j+) printf("%d ",bookij); printf("n"

9、;); int main() read();/输入 bfs(); output();/输出 return 0;2树上最短路径2.1 解题思路 问题问每个人和dashen 的距离，组员的距离为1。也就是说，人与人之间的距离都是通过“组员”来不断量化的。那么可以想到，组员之间可以画一条边，问题问的整个人际之间的图建好之后，将人看为节点，求出每个节点与某个定点的最短距离。这个图的遍历+定点最短距离问题显然用BFS很好解决。 问题的难点：1） 映射字符串到id的关系，我用的是STL的map容器解决。2） 保存点之间边的关系，本来用的是矩阵保存，但是写到后来很麻烦，就用邻接表保存3） 输出的时候有点麻烦

10、2.2 测试样例7dashen Oparin ToropovAyzenshteyn Oparin SamsonovAyzenshteyn Chevdar SamsonovFominykh dashen OparinDublennykh Fominykh IvankovBurmistrov Dublennykh KurpilyanskiyCormen Leiserson Rivest2.3 程序运行情况2.4 程序源码（含注释）#include"bits/stdc+.h"using namespace std;#define inf 999#define INF int n,

11、num;/行数，以及不重复人数int origin;/ 起点，即dashen 的标号int bookinf;/标记vector<int>edgeinf;/每个点的边集struct Student/学生类,下标自1始 string name; int id; int rank; void set(string s,int i) name=s; id=i; rank=INF;/所有人的距离默认无穷大 bool operator<(const Student& t)const name<; studentinf;void read()/输入数据 num=0

12、;/人数初始化 memset(book,0,sizeof book);/初始化标记 cout<<"input the num of the groups:" cin>>n; cout<<"now input the each group mates:n" map<string,int>m; m.clear(); string s3;/临时存放 for(int i=0;i<n;i+) for(int j=0;j<3;j+)/读入点，建点 cin>>sj; if(msj=0)/没出现过就

13、赋予标号以及存储名字 msj=+num; studentnum.set(sj,num);/存储此人id和名字 if(sj="dashen") origin=msj; for(int j=0;j<2;j+) /建图 for(int k=j+1;k<3;k+) int a=msj; int b=msk; edgea.push_back(b);/加入边集 edgeb.push_back(a); printf("n");void bfs()/根据id进行bfs queue<int>q; while(!q.empty()q.pop();/初

14、始化 q.push(origin);/放入首节点 bookorigin=1;/标记走过 studentorigin.rank=0;/dashen是0 while(!q.empty() int v=q.front(); q.pop();/取出节点 int len=edgev.size(); for(int i=0;i<len;i+) int u=edgevi; studentu.rank=min(studentv.rank+1,studentu.rank); if(!booku) q.push(u); booku=1; void output() printf("-n"); int i; sort(student+1,student+num+1);/排序 for(i=1;i<=num;i+) cout<<st