算法设计与分析分支界限法实验报告文档格式.docx

1、Sample Input7dashen Oparin ToropovAyzenshteyn Oparin SamsonovAyzenshteyn Chevdar SamsonovFominykh dashen OparinDublennykh Fominykh IvankovBurmistrov Dublennykh KurpilyanskiyCormen Leiserson RivestSample OutputAyzenshteyn 2Burmistrov 3Chevdar 3Cormen undefinedDublennykh 2Fominykh 1dashen 0Ivankov 2Ku

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

3、。步骤都是一样的：放第一个进队，然后出队、扩散开进队并标记、出队.循环下去直到队空。写法太基础就不讲解了。1.2 测试样例3 24 6.#.#.#.#.#.#.#.1.3 程序运行情况1.4 程序源码（含注释）#includebits/stdc+.husing 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

4、 row of the map:）; scanf（%d,&n）;now input the point:n%d%d%d%dsx,&sy,&gx,&gy）;/输入下标自1开始 sx-;/计算下标从0开始 sy-; gx-; gy-;input the map now: for（int i=0;in;i+）%s,ei）; memset（book,0,sizeof book）;/初始化struct Node /节点 int x,y; Node（int i,int j）:x（i）,y（j） ;bool islegal（int x,int y）/判断是否合法 if（x=n|y=n）return fals

5、e; return true;void bfs（）/方便快捷 queueq; while（!q.empty（）q.pop（）; q.push（Node（sx,sy）;/放入首节点 booksxsy=0;/标记q.empty（） Node t=q.front（）; q.pop（）;/取出节点 int tag=bookt.xt.y; if（t.x=gx&t.y=gy）break;/提前结束4; int x=t.x+posi0; int y=t.y+posi1; if（islegal（x,y）&exy=.!bookxy）/放入 未越界、可走、未走过的 q.push（Node（x,y）; bookxy

6、=tag+1;void output（）-n int i,j; for（i=0; for（j=0;jj+）%d ,bookij）;int main（） read（）;/输入 bfs（）; output（）;/输出 return 0;2树上最短路径2.1 解题思路 问题问每个人和dashen 的距离，组员的距离为1。也就是说，人与人之间的距离都是通过“组员”来不断量化的。那么可以想到，组员之间可以画一条边，问题问的整个人际之间的图建好之后，将人看为节点，求出每个节点与某个定点的最短距离。这个图的遍历+定点最短距离问题显然用BFS很好解决。 问题的难点：1）映射字符串到id的关系，我用的是STL的

7、map容器解决。2）保存点之间边的关系，本来用的是矩阵保存，但是写到后来很麻烦，就用邻接表保存3）输出的时候有点麻烦2.2 测试样例2.3 程序运行情况2.4 程序源码（含注释）#define INF 999999999int n,num;/行数，以及不重复人数int origin;/ 起点，即dashen 的标号int bookinf;vectoredgeinf;/每个点的边集struct Student/学生类,下标自1始 string name; int id; int rank; void set（string s,int i） name=s; id=i; rank=INF;/所有人的

8、距离默认无穷大 bool operator（const Student& t）const namet.name;studentinf; num=0;/人数初始化/初始化标记 coutnow input the each group mates: mapm; m.clear（）; string s3;/临时存放 for（int j=0;3;j+）/读入点，建点sj; if（msj=0）/没出现过就赋予标号以及存储名字 msj=+num; studentnum.set（sj,num）;/存储此人id和名字 if（sj=dashen） origin=msj;2;j+） /建图 for（int k=j

9、+1;kk+） int a=msj; int b=msk; edgea.push_back（b）;/加入边集 edgeb.push_back（a）;void bfs（）/根据id进行bfs q.push（origin）; bookorigin=1;/标记走过 studentorigin.rank=0;/dashen是0 int v=q.front（）; int len=edgev.size（）;len; int u=edgevi; studentu.rank=min（studentv.rank+1,studentu.rank）; if（!booku） q.push（u）; booku=1; int i; sort（student+1,student+num+1）;/排序 for（i=1;=num;studenti.name int id=studenti.id; if（studenti.rank=INF）undefinedendl; elsestudenti.rank