算法实习报告

1、.普里姆 (prim) 算法：假 n=（ v ，e ）是 通网， v=v1 ，v2 ， vn 是网的 点集合，e 是 n 上最小生成 中 的集合。引入 点集合u 和 的集合te，u 的初 状 v1 ，它存放的是当前所得到的（ 未完成的）最小代价生成 上所有 点，te 的初始状 。在 prim 算法的每一步， 都从所有的 (u,v), uu, vv 中找出所有代价最小的 (u ，v)，同 将 v并入 u ，（ u，v）并入集合te ，直到 u=v 止。此 te 中必有 n-1 条 ， 则 t=（ v ，te ）为 n 的最小生成 。克 斯卡 (kruskal) 算法 ：假 g=（ v ， e ）

2、是一个 通的无向 ，其中v=1 ，2， n ，引入 助集合t ，来存放当前所形成的最小生成 的所有 ，其初始状 空，kruskal 算法是逐步 t 添加不和 t 中的 构成回路的当前最小代价 。具体步 ：1、初始化t= ;2、当 t 的 小于n-1 ，做如下工作；3、从 e(g)中 取代价最小的 (v,u)并 除之；4、若 (v,u)不和 t 中的 一起构成回路， 将 (v,u)并入 t 中。5、循 24 步，直到t 中所有 点都在同一个 通 上 止。拓扑排序的 算机 ：方法：采用 接表作 有向 的存 构，且在 点中增加一个有效 点的入度，入度 零的 点既 滑有前 的 点， 除 点及弧可以使入

3、度减1。 避免重复 入度 零的 点，可另 一 表将所有入度 零的 点 到一起，每当 出便 除，反之，当有新的入度 零的 点 插入， 相当于一个 。算法：1、 接表中入度 零的 点，并 ；2、当 非空 ， 行拓扑排序；（ 1） 出 的 点 vj 并退 ；（ 2） 出 的 点 vj 的直接后 vk(k=1,2, )，将 vk 的入度减 1，并将入度 0 的 点 。（ 3）若 空 出的 点数不足aov- 网中 点数 n， 明有向 中存在有向 ，否 拓扑排序完 。status topologicalsort(algraph g)findindegree(g ,indegree);initstack(s

4、);for(i=0;inextarc)k=p-adjvex;if(!(-indegree(k)push(s,k);if(countg .vexnum)returnerror;elsereturn ok;迪杰斯拉特（dijkstra ）算法 ：该算法提出了一个按路径递增的顺序产生最短路径的算法。首先引入一个辅助向量d ，它的分量 d(i) 表示当前所有找到的从始点v 到每个终点vi 的最短路径的长度。其初态为：若从 v 到 vi 有弧，则d(i) 为弧上权，否则为无穷大；显然，长度为d(j)=mind(i)| viv的路径是从v 出发的最短一条路径，此路径为(v, vj ) 。网络的可靠性时间限

5、制： 3000 ms|内存限制： 65535 kb难度： 3描述a 公司是全球依靠的互联网解决方案提供商，也是2010 年世博会的高级赞助商。它将提供先进的网络协作技术，展示其”智能+互联“的生活概念，同时为参观者提供高品质的个人体验和互动，以”信息通信，尽情城市梦想”为主题贯穿。借助奇幻的剧场大屏幕和特效，展现信息通信技术的应用前景，通过生动形象的故事，向观众展示沟通无限制的未来社会前景。为此， a 公司为世博园的 n 个区域建立了视频通信系统，其中每个区域建立一个基站，编号依次为 1， 2， 3.,n。通过基站之间的通信线路为各区域的参观者提供视频服务。已知在各基站之间已铺设了一些光纤通讯

6、线路，这些线路覆盖了所有的区域，即任意两个区域都可以进行视频传递。但为了节约成本开支，目前只铺设了 n-1 条线路，同时为了减轻各基站的信息传递负载，每个基站最多有三条光纤通讯线路与之连接。但在通信系统试运行期间， a 公司发现当某个基站发生故障时， 会导致其它区域之间无法进行信息传递。 为了提高该通信网络的可靠性， a 公司准备在基站之间再新铺设一些光纤线路，使得任意一个基站故障后，其它基站之间仍然可以通讯。;.由于铺设线路的成本昂贵，a 公司希望新增设的光纤线路越少越好。a 公司请求dr. kong来完成这个任务输入有多组测试数据，以eof 为结束标志。第一行：n 表示有 n 个基站接下来

7、有 n-1 行： x y表示第 x 个基站与第y 个基站直连1=n=10000输出输出一个整数，表示至少需新铺设的光纤线路数样例输入81 33 25 35 45 62 72 8样例输出3#include#include #includeusing namespace std;#define max 10001int resultmax;int main()int n,i,a,b;while(scanf(%d,&n)!=eof)memset(result,0,sizeof(result);for(i=0;in-1;i+)scanf(%d%d,&a,&b);resulta+;resultb+;in

8、t sum=0;for(i=0;i=n;i+);.if(resulti=1)sum+;printf(%dn,sum%2=0?sum/2:(sum/2+1);return 0;回溯法：实际上是一种搜索问题的解的一种方法。所采用的方法一般为深度优先搜索法，所搜索的路径一般是沿树形结构进行搜索。在搜索过程中， 首先会判断所搜索的树结点是否包含问题的解，如果肯定不包含，则不再搜索以该结点为根的树结点，而向其祖先结点回溯。否则进入该子树，继续按深度优先策略搜索。1）递归回溯利用递归算法对树进行深度遍历，并在遍历过程中不断地判断当前搜索的结点是否符合搜索条件，如果符合继续进行深度遍历，否则剪去该分支，搜索

9、后续分支。2）迭代回溯采用树的非递归深度优先遍历方法也可实现回溯算法。非递归算法实际上是用循环来取代递归进行回溯。装载问题有一批共n 个集装箱要装上2 艘载重量分别为c1 和 c2 的轮船， 其中集装箱i 的重量为wi, 且 wi=c1+c2,其中 1=i=n 。问是否可以找到一种装载方法是的这n 个集装箱可以装载到这2 艘轮船上。装载问题是一个np 问题。在该问题中，可以采用下面的策略：（1）首先尽可能的将第一艘轮船装满。（2）看剩余的货物能否装入第2 艘船。为什么可采用上述策略呢？可以证明！显然，对于策略 （ 1）需要去搜索一些货物，使其货物重量尽可能的接近于第一艘轮船的装载量。这个搜索策

10、略当然可采用回溯法实现。/ modifymaxloading.cpp :定义控制台应用程序的入口点。/#include stdafx.h#include using namespace std;template type maxloading(type w,type c, int n);template class loadingfriend type maxloading(type , type, int);.public:void backtrack(int i);int n;/集装箱数量/w- 集装箱重量数组;c- 第一艘轮船的载重量；cw- 当前载重量 ;bestw- 当前最优载重量t

11、ype *w,c,cw,bestw;/ 剩余集装箱重量type r;int main()int *w,c,n,bestw,tc, maxw=0;/输入必要的数据coutn;w=new intn;coutplease input the weight of each container:;for(int i=1;iwi;maxw+=wi;coutc;couttc;/调用函数实现回溯法搜索是否可以以最大限度的形式装载集装箱到第一艘船 bestw=maxloading(w,c,n);/判断第 2 艘船是否可以装载下剩余的集装箱if(maxw-bestwtc)coutthe two ship can

12、load all the container:endl;else;.coutthe two ship cannt load all the containerendl;return 0;template void loading :backtrack(int i)/如果已到叶子结点if(in)if(cwbestw) bestw=cw;return;/搜索子树 ,减去第 i 个集装箱的重量为剩余集装箱重量r-=wi;/访问左子树if(cw+wi当前已求的的最优解，则访问右子树if(cw+rbestw)backtrack(i+1);/因为是访问右子树，因此第i 个集装箱并不装载到轮船上r+=wi;

13、template type maxloading(type w,type c, int n)loading x;x.w =w;x.c=c;x.n =n;x.bestw=0;x.cw=0;/求解剩余集装箱的重量;.x.r=0;for(int i=1;i=n;i+)x.r+=wi;x.backtrack(1);return x.bestw;上述算法只求的了最优解，但具体是元素构成了最优解呢并不知道。因此可通过增加两个成员变量的方法来记录求解出的最优解。一个是 x,另一个是 bestx。 x 用于记录从根到当前结点的路径，bestx 记录当前最优解。/ xmodifymaxloading.cpp :

14、定义控制台应用程序的入口点。#include stdafx.h#include using namespace std;template type maxloading(type w,type c, int n,int bestx);template class loadingfriend type maxloading(type , type, int, int );public:void backtrack(int i);int n;/集装箱数量/x- 当前解bestx- 当前最优解int *x,*bestx;/w- 集装箱重量数组;c- 第一艘轮船的载重量；cw- 当前载重量 ;best

15、w- 当前最优载重量type *w,c,cw,bestw;/ 剩余集装箱重量type r;int main();.int *w,c,n,bestw,tc, maxw=0,*bestx;/输入必要的数据coutn;w=new intn+1;bestx=new int n+1;coutplease input the weight of each container:;for(int i=1;iwi;maxw+=wi;coutc;couttc;/调用函数实现回溯法搜索是否可以以最大限度的形式装载集装箱到第一艘船 bestw=maxloading(w,c,n,bestx);/判断第 2 艘船是否可以

16、装载下剩余的集装箱if(maxw-bestwtc)coutthe two ship can load all the container:endl;elsecoutthe two ship cannt load all the containerendl;return 0;template void loading :backtrack(int i)/如果已到叶子结点if(in)if(cwbestw)/如果当前解是目前所找到的最优解，将当前解作为最优解保存到bestx中for(int j=1;j=n;j+);.bestxj=xj;bestw=cw;return;/搜索子树 ,减去第 i 个集装

17、箱的重量为剩余集装箱重量r-=wi;/访问左子树if(cw+wi当前已求的的最优解，则访问右子树if(cw+rbestw)/ 该结点未被选中xi=0;backtrack(i+1);/ 因为是访问右子树，因此第 i 个集装箱并不装载到轮船上 r+=wi;template type maxloading(type w,type c, int n,int bestx)loading x;x.w =w;x.c=c;x.n =n;x.bestw=0;x.bestx=bestx;x.cw=0;/分配 n+1 个空间用于存储每个集装箱是否被选中的标志x.x=new intn+1;./求解剩余集装箱的重量x.r=0;for(int i=1;i=n;i+)x.r+=wi;x.backtrack(1);delete x.x;return x.bestw;感想：在这短暂而又漫长的二十天实习中，我们在相同的兴趣下一起训练，一起a 题，一起学习，在这当中我们学到了很多，也提高了很多。在实习过程中，我认识了许多以前很少听说和接触的算法，虽然还不是很深透的理解，但是在不断地钻研和请教中编程能力