算法实习报告.docx

算法实习报告.docx

《算法实习报告.docx》由会员分享，可在线阅读，更多相关《算法实习报告.docx（13页珍藏版）》请在冰点文库上搜索。

算法实习报告

普里姆（Prim）算法：

假设N=（V，{E}）是连通网，V={V1，V2，…，Vn}是网的顶点集合，{E}是N上最小生成树中边的集合。

引入顶点集合U和边的集合TE，U的初试状态为{V1}，它存放的是当前所得到的（还未完成的）最小代价生成树上所有顶点，TE的初始状态为{}。

在Prim算法的每一步，都从所有的边{（u,v）,uÎU,vÎV}中找出所有代价最小的边（u，v），同时将v

并入U，（u，v）并入集合TE，直到U=V为止。

此时TE中必有n-1条边，则T=（V，{TE}）为N的最小生成树。

克鲁斯卡尔（Kruskal）算法：

假设G=（V，{E}）是一个连通的无向图，其中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、循环2~4步，直到T中所有顶点都在同一个连通图上为止。

拓扑排序的计算机实现：

方法：

采用邻接表作为有向图的存储结构，且在头结点中增加一个有效

顶点的入度，入度为零的顶点既为滑有前趋的顶点，删除顶点及

弧可以使入度减1。

为避免重复检测入度为零的顶点，可另设一链表将所有入度为零

的顶点链结到一起，每当输出便删除，反之，当有新的入度为零的顶

点则插入，这相当于一个栈。

算法：

1、查邻接表中入度为零的顶点，并进栈；

2、当栈非空时，进行拓扑排序；

（1）输出栈顶的顶点Vj并退栈；

（2）输出栈顶的顶点Vj的直接后继Vk（k=1,2,…），将Vk的入度

减1，并将入度为0的顶点进栈。

（3）若栈空时输出的顶点数不足AOV-网中顶点数n，则说明有

向图中存在有向环，否则拓扑排序完毕。

StatusTopologicalSort（ALGraphG）

{

FindInDegree（G,indegree）;

InitStack（S）;

for（i=0;i

if（!

indegree（i））

push（S,i）;

count=0;

if（!

StachEmpty（s））{

pop（S,i）;

printf（i,G.vertices（i）,data）;

count++;

for（p=G.vertices[i].firstarc;p;p=p->nextarc）{

k=p->adjvex;

if（!

（--indegree（k）））

push（S,K）;

}

}

if（count

returnERROR;

else

returnOK;

}

迪杰斯拉特（Dijkstra）算法：

该算法提出了一个按路径递增的顺序产生最短路径的算法。

首先引入一个辅助向量D，它的分量D（i）表示当前所有找到的从始点V到每个终点Vi的最短路径的长度。

其初态为：

若从V到Vi有弧，则D（i）为弧上权，否则为无穷大；显然，长度为

D（j）=Min{D（i）|ViÎV}

的路径是从V出发的最短一条路径，此路径为（V,Vj）。

网络的可靠性

时间限制：

3000ms|内存限制：

65535KB

难度：

3

描述

A公司是全球依靠的互联网解决方案提供商，也是2010年世博会的高级赞助商。

它将提供先进的网络协作技术，展示其”智能+互联“的生活概念，同时为参观者提供高品质的个人体验和互动，以”信息通信，尽情城市梦想”为主题贯穿。

借助奇幻的剧场大屏幕和特效，展现信息通信技术的应用前景，通过生动形象的故事，向观众展示沟通无限制的未来社会前景。

为此，A公司为世博园的N个区域建立了视频通信系统，其中每个区域建立一个基站，编号依次为1，2，3...,N。

通过基站之间的通信线路为各区域的参观者提供视频服务。

已知在各基站之间已铺设了一些光纤通讯线路，这些线路覆盖了所有的区域，即任意两个区域都可以进行视频传递。

但为了节约成本开支，目前只铺设了N-1条线路，同时为了减轻各基站的信息传递负载，每个基站最多有三条光纤通讯线路与之连接。

但在通信系统试运行期间，A公司发现当某个基站发生故障时，会导致其它区域之间无法进行信息传递。

为了提高该通信网络的可靠性，A公司准备在基站之间再新铺设一些光纤线路，使得任意一个基站故障后，其它基站之间仍然可以通讯。

由于铺设线路的成本昂贵，A公司希望新增设的光纤线路越少越好。

A公司请求Dr.Kong来完成这个任务

输入

有多组测试数据，以EOF为结束标志。

第一行：

N表示有N个基站

接下来有N-1行：

XY表示第X个基站与第Y个基站直连

1<=N<=10000

输出

输出一个整数，表示至少需新铺设的光纤线路数

样例输入

8

13

32

53

54

56

27

28

样例输出

3

#include

#include

#include

usingnamespacestd;

#definemax10001

intresult[max];

intmain（）

{

intn,i,a,b;

while（scanf（"%d",&n）!

=EOF）

{

memset（result,0,sizeof（result））;

for（i=0;i

{

scanf（"%d%d",&a,&b）;

result[a]++;

result[b]++;

}

intsum=0;

for（i=0;i<=n;i++）

{

if（result[i]==1）

sum++;

}

printf（"%d\n",sum%2==0?

sum/2:

（sum/2+1））;

}

return0;

}

回溯法：

实际上是一种搜索问题的解的一种方法。

所采用的方法一般为深度优先搜索法，所搜索的路径一般是沿树形结构进行搜索。

在搜索过程中，首先会判断所搜索的树结点是否包含问题的解，如果肯定不包含，则不再搜索以该结点为根的树结点，而向其祖先结点回溯。

否则进入该子树，继续按深度优先策略搜索。

1）递归回溯

利用递归算法对树进行深度遍历，并在遍历过程中不断地判断当前搜索的结点是否符合搜索条件，如果符合继续进行深度遍历，否则剪去该分支，搜索后续分支。

2）迭代回溯

采用树的非递归深度优先遍历方法也可实现回溯算法。

非递归算法实际上是用循环来取代递归进行回溯。

装载问题

有一批共n个集装箱要装上2艘载重量分别为c1和c2的轮船，其中集装箱i的重量为wi,且∑wi<=C1+C2,其中1<=i<=n。

问是否可以找到一种装载方法是的这n个集装箱可以装载到这2艘轮船上。

装载问题是一个NP问题。

在该问题中，可以采用下面的策略：

（1）首先尽可能的将第一艘轮船装满。

（2）看剩余的货物能否装入第2艘船。

为什么可采用上述策略呢？

可以证明！

显然，对于策略

（1）需要去搜索一些货物，使其货物重量尽可能的接近于第一艘轮船的装载量。

这个搜索策略当然可采用回溯法实现。

//ModifyMaxLoading.cpp:

定义控制台应用程序的入口点。

//

#include"stdafx.h"

#include

usingnamespacestd;

template

TypeMaxLoading（Typew[],Typec,intn）;

template

classLoading{

friendTypeMaxLoading（Type[],Type,int）;

public:

voidBacktrack（inti）;

intn;//集装箱数量

//w-->集装箱重量数组;c-->第一艘轮船的载重量；cw-->当前载重量;bestw-->当前最优载重量

Type*w,c,cw,bestw;

//剩余集装箱重量

Typer;

};

intmain（）

{

int*w,c,n,bestw,tc,Maxw=0;

//输入必要的数据

cout<<"PleaseinputthenumberofContainer:

";

cin>>n;

w=newint[n];

cout<<"Pleaseinputtheweightofeachcontainer:

";

for（inti=1;i<=n;i++）{

cin>>w[i];

Maxw+=w[i];

}

cout<<"PleaseinputtheMaximumweightforthefirstship:

";

cin>>c;

cout<<"PleaseinputtheMaximumweightforthesecondship:

";

cin>>tc;

//调用函数实现回溯法搜索是否可以以最大限度的形式装载集装箱到第一艘船

bestw=MaxLoading（w,c,n）;

//判断第2艘船是否可以装载下剩余的集装箱

if（Maxw-bestw

cout<<"thetwoshipcanloadallthecontainer:

"<

else

cout<<"thetwoshipcann'tloadallthecontainer"<

return0;

}

template

voidLoading:

:

Backtrack（inti）

{

//如果已到叶子结点

if（i>n）{

if（cw>bestw）bestw=cw;

return;

}

//搜索子树,减去第i个集装箱的重量为剩余集装箱重量

r-=w[i];

//访问左子树

if（cw+w[i]<=c）{

cw+=w[i];

Backtrack（i+1）;

cw-=w[i];

}

//如果当前已装载货物的重量+剩余集装箱货物的重量>当前已求的的最优解，则访问右子树

if（cw+r>bestw）

Backtrack（i+1）;

//因为是访问右子树，因此第i个集装箱并不装载到轮船上

r+=w[i];

}

template

TypeMaxLoading（Typew[],Typec,intn）

{

LoadingX;

X.w=w;

X.c=c;

X.n=n;

X.bestw=0;

X.cw=0;

//求解剩余集装箱的重量

X.r=0;

for（inti=1;i<=n;i++）

X.r+=w[i];

X.Backtrack

（1）;

returnX.bestw;

}

上述算法只求的了最优解，但具体是元素构成了最优解呢并不知道。

因此可通过增加两个成员变量的方法来记录求解出的最优解。

一个是x,另一个是bestx。

X用于记录从根到当前结点的路径，bestx记录当前最优解。

//XModifyMaxLoading.cpp:

定义控制台应用程序的入口点。

#include"stdafx.h"

#include

usingnamespacestd;

template

TypeMaxLoading（Typew[],Typec,intn,intbestx[]）;

template

classLoading{

friendTypeMaxLoading（Type[],Type,int,int[]）;

public:

voidBacktrack（inti）;

intn;//集装箱数量

//x-->当前解bestx-->当前最优解

int*x,*bestx;

//w-->集装箱重量数组;c-->第一艘轮船的载重量；cw-->当前载重量;bestw-->当前最优载重量

Type*w,c,cw,bestw;

//剩余集装箱重量

Typer;

};

intmain（）

{

int*w,c,n,bestw,tc,Maxw=0,*bestx;

//输入必要的数据

cout<<"PleaseinputthenumberofContainer:

";

cin>>n;

w=newint[n+1];

bestx=newint[n+1];

cout<<"Pleaseinputtheweightofeachcontainer:

";

for（inti=1;i<=n;i++）{

cin>>w[i];

Maxw+=w[i];

}

cout<<"PleaseinputtheMaximumweightforthefirstship:

";

cin>>c;

cout<<"PleaseinputtheMaximumweightforthesecondship:

";

cin>>tc;

//调用函数实现回溯法搜索是否可以以最大限度的形式装载集装箱到第一艘船

bestw=MaxLoading（w,c,n,bestx）;

//判断第2艘船是否可以装载下剩余的集装箱

if（Maxw-bestw

cout<<"thetwoshipcanloadallthecontainer:

"<

else

cout<<"thetwoshipcann'tloadallthecontainer"<

return0;

}

template

voidLoading:

:

Backtrack（inti）

{

//如果已到叶子结点

if（i>n）{

if（cw>bestw）{

//如果当前解是目前所找到的最优解，将当前解作为最优解保存到bestx中

for（intj=1;j<=n;j++）

bestx[j]=x[j];

bestw=cw;

}

return;

}

//搜索子树,减去第i个集装箱的重量为剩余集装箱重量

r-=w[i];

//访问左子树

if（cw+w[i]<=c）{

//用1表示第i个结点是被选中的结点

x[i]=1;

cw+=w[i];

Backtrack（i+1）;

cw-=w[i];

}

//如果当前已装载货物的重量+剩余集装箱货物的重量>当前已求的的最优解，则访问右子树

if（cw+r>bestw）{

//该结点未被选中

x[i]=0;

Backtrack（i+1）;

}

//因为是访问右子树，因此第i个集装箱并不装载到轮船上

r+=w[i];

}

template

TypeMaxLoading（Typew[],Typec,intn,intbestx[]）

{

LoadingX;

X.w=w;

X.c=c;

X.n=n;

X.bestw=0;

X.bestx=bestx;

X.cw=0;

//分配n+1个空间用于存储每个集装箱是否被选中的标志

X.x=newint[n+1];

//求解剩余集装箱的重量

X.r=0;

for（inti=1;i<=n;i++）

X.r+=w[i];

X.Backtrack

（1）;

delete[]X.x;

returnX.bestw;

}

感想：

在这短暂而又漫长的二十天实习中，我们在相同的兴趣下一起训练，一起A题，一起学习，在这当中我们学到了很多，也提高了很多。

在实习过程中，我认识了许多以前很少听说和接触的算法，虽然还不是很深透的理解，但是在不断地钻研和请教中编程能力的确有了很大的提高。

在编程的时候，面对每个问题都需要自己想出合适的思路和算法，在无数次的wronganswer后看到令你欣喜若狂的accepted，那种心情简直兴奋的无法形容。

同时以小组的形式做题更增强了我的团队合作能力和组织能力，团队合作总是比孤军奋战强。

看到同伴的努力自己自然而然地积极起来，看到同伴提交的题目通过后自然增强了团队的自信心。

通过团队合作获得的胜利喜悦之情无疑是这个夏日里最凉爽的清泉。

在这里，我也要感谢各位一起集训的ACM校队的大神们给我们仔细地讲解题目，在QQ群里不断更新，很多都是有用的信息。

这次实习是人生中一大宝贵财富。