中南大学算法实验报告Word文件下载.docx
- 文档编号:5740882
- 上传时间:2023-05-05
- 格式:DOCX
- 页数:24
- 大小:274.19KB
中南大学算法实验报告Word文件下载.docx
《中南大学算法实验报告Word文件下载.docx》由会员分享,可在线阅读,更多相关《中南大学算法实验报告Word文件下载.docx(24页珍藏版)》请在冰点文库上搜索。
publicinttime;
//记录打开、关闭节点的时间
}
publicclassVNode{//节点类
publicintdata;
//节点的内容
publicbooleanvisited=false;
//是否访问过
publicbooleanifclosed=false;
//是否被放在关闭的表中
publicintdistance=10000;
//距离某一点的最短距离
publicintfront=10000;
//前驱节点
publicArcNodenextarc=null;
//下一条边
publicintentertime,exittime;
//打开、关闭节点的时间
publicclassArcNode{//边类
publicintadjvex;
//该弧所指向的顶点的位置
publicintweight=0;
//该边的权值
}
2.DFS
publicvoidDFS(GraphG){//DFS的起始调用方法
intvexmun=G.vexmun;
G.time=0;
for(intv=1;
v<
=vexmun;
v++){
if(G.arrVnode[v].visited==false){
DFS_VISIT(G,v);
}
publicvoidDFS_VISIT(GraphG,intv){//应用递归的DFS访问
G.arrVnode[v].visited=true;
G.time++;
//time是给后面的拓扑排序实验用的
G.arrVnode[v].entertime=G.time;
System.out.println(G.arrVnode[v].data);
ArcNodenode=G.arrVnode[v].nextarc;
while(node!
=null){
intp=node.adjvex;
if(G.arrVnode[p].visited==false&
&
G.arrVnode[p]!
DFS_VISIT(G,p);
node=node.nextarc;
G.arrVnode[v].exittime=G.time;
3.BFS
publicvoidBFS(QueueQueue,GraphG,intv){
if(visited[v]==false){
visited[v]=true;
System.out.print(G.arrVnode[v].data);
System.out.print("
"
);
ArcNodenode=G.arrVnode[v].nextarc;
//QueueFunction.EnQueue(Queue,v);
//while(Queue!
if(visited[node.adjvex]==false&
queueed[node.adjvex]==false){
QueueFunction.EnQueue(Queue,node.adjvex);
queueed[node.adjvex]=true;
node=node.nextarc;
BFS(Queue,G,QueueFunction.DeQueue(Queue));
实验结果:
数据说明:
5个节点,10条边,每行数字分别是起始节点、终止节点、权值。
实验总结:
DFS与BFS较为简单,是图论的基础。
在以后的实验中,不管是动态规划、贪心算法、回溯法都会以DFS或BFS为基础,应当是我们每个人都要掌握的。
实验二最近点对问题
运用分治算法,解决最近点对问题。
使用分治法解决最近点对问题就是将集合S分成两个子集是S1和S2,每个子集中有N/2个点。
然后再每个子集中递归的求其最接近的点对,求出每个子集的最接近点对后,如果集合S中最接近的点对都在两个子集中,问题解决。
当两个点分别在两个子集中时,则最近点对为S1和S2的最接近点。
其时间复杂度为O(nlogn)。
1.排序
第一步是将所有从文件获取的点按照X轴升序排列,若X坐标相同则按Y轴坐标由小到大排列。
//按照X轴坐标升序排序
Arrays.sort(point,newComparator<
Neighborpoint>
(){
publicintcompare(Neighborpointo1,Neighborpointo2){
if(o1.x<
o2.x)
return-1;
if(o1.x>
return1;
if(o1.y<
o2.y)
if(o1.y>
return0;
});
2.分治法求最近点对
publicstaticdoubleClose_pair(Neighborpoint[]point,intleft,intright){
doubled=1e20;
if(right==left)//同一点,返回很大值
returnd;
if(left+1==right)
returndistance(left,right);
intmid=(left+right)>
>
1;
//除以2
doubled1=Close_pair(point,left,mid);
doubled2=Close_pair(point,mid+1,right);
d=min(d1,d2);
inti,j,k=0;
tmpt=newint[10000];
//分离d区域
for(i=left;
i<
=right;
i++){
if(Math.abs(point[mid].x-point[i].x)<
d)
tmpt[k++]=i;
数据文件:
点的显示:
结果显示:
按照分治法,可以很方便的解决这个问题。
虽然心里还是很排斥递归,但是真正用到的话还是比较简洁的。
另外最开始做这个实验的时候,还不太熟悉比较器,本来是可以直接把点记录下来的,但当时是将点的值存入到数组以后再排序的,所以没能很方便的读出最近点的坐标,这个有时间再进行改进。
实验三拓扑排序
实现一个拓扑排序
由AOV网构造拓扑序列的拓扑排序算法主要是循环执行以下两步,直到不存在入度为0的顶点为止。
(1)选择一个入度为0的顶点并输出之;
(2)从网中删除此顶点及所有出边。
循环结束后,若输出的顶点数小于网中的顶点数,则输出“有回路”信息,否则输出的顶点序列就是一种拓扑序列。
1.数据结构与DFS
拓扑排序基本上和DFS没什么区别,它的本质其实就是DFS关闭节点的倒序输出。
所以在数据结构上,和第一个实验用的是相同的数据结构来保存图。
publicinttime;
值得注意的是,以上两个变量,是用来实现拓扑排序的关键部分。
2.拓扑排序的实现
publicvoidToposortmethod(GraphG){
MaxPQ<
VNode>
pq1=newMaxPQ<
(newComparator<
publicintcompare(VNodeo1,VNodeo2){
if(o1.exittime<
o2.exittime)return-1;
elseif(o1.exittime==o2.exittime)return0;
elsereturn1;
GrahpFuntion.DFS1(G);
for(inti=1;
=G.vexmun;
pq1.insert(G.arrVnode[i]);
System.out.println("
拓扑排序顺序:
"
VNodeVnode;
Vnode=pq1.delMax();
System.out.println(Vnode.data);
上面那个是因为调用了DFS而产生的DFS输出结果
由于有了之前的铺垫,所以拓扑排序相对来说比较简单,我只是在图的设计类中添加了一个时间变量,而在节点的打开、关闭的过程中增加了时间。
拓扑排序是计算机网络的基础,在很多地方都有体现,值得我们注意。
实验四N皇后问题
应用回溯法解决N皇后问题
(1)针对所给问题,定义问题的解空间;
(2)确定易于搜索的解空间结构;
(3)以深度优先的方式搜索解空间,并且在搜索过程中用剪枝函数避免无效搜索。
首先找出解空间:
给棋盘的行和列都编上1到N的号码,皇后也给编上1到N的号码。
由于一个皇后应在不同的行上,为不失一般性,可以假定第i个皇后将放在第i行上的某列。
因此N皇后问题的解空间可以用一个N元组(X1,X2,.....Xn)来表示,其中Xi是放置皇后i所在的列号。
这意味着所有的解都是N元组(1,2,3,.......,N)的置换。
解空间大小为N!
。
其次我们看约束条件:
因为解空间已经给我们排除了不在同一行(因为每个皇后分别已经对应不同的行号)的约束条件。
我们要判断的是不在同一列和不在同一斜线的约束。
因为Xi表示皇后所在的列号,所以如果存在X(k)=X(i)那么肯定存在第k个皇后和第i个皇后同列。
所以不同列的判段条件是X(k)!
=X(i),1<
k<
i。
又因为同一斜线的特征是要么行号和列号之和不变(右高左低)要么是行号和列号只差相等(左高右低),所以同斜线的判断条件是i+X(i)=k+X(k)或i-X(i)=k-X(k),两式合并得|X(i)-X(k)|=|i-k|。
关于N皇后问题,我设计了两种方式,一个是递归回溯,另一个是非递归回溯版本。
1.判断是否可以放置的place方法
booleanplace(intk){
inti;
for(i=1;
k;
if(column[i]==column[k]||Math.abs(i-k)==Math.abs(column[i]-column[k]))
returnfalse;
returntrue;
2.递归回溯
voidbacktrack(intt){//递归版本
inti=0;
if(t>
N){
System.out.println("
第"
+count+"
组"
count++;
for(i=1;
=N;
System.out.println("
("
+i+"
"
+column[i]+"
)"
}
}else{
column[t]=i;
if(place(t))backtrack(t+1);
3.非递归回溯
voidbacktrack2(){//非递归
count=1;
column[1]=0;
intk=1;
while(k>
0){
column[k]++;
while((column[k]<
=N)&
!
place(k)){
column[k]++;
if(column[k]<
=N){
if(k==N){
System.out.println("
count++;
for(i=1;
System.out.println("
}
}else{
k++;
column[k]=0;
}
else{//回溯
k--;
当参数设置N=4,即四皇后问题。
N皇后问题是回溯法的经典问题,在通过多次减枝以后,可以有效的减少时间复杂度。
实验五0-1背包问题
应用动态规划解决0-1背包问题
f[i][v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。
则其状态转移方程便是:
f[i][v]=max{f[i-1][v],f[i-1][v-w[i]]+v[i]}。
可以压缩空间,f[v]=max{f[v],f[v-w[i]]+v[i]}
“将前i件物品放入容量为v的背包中”这个子问题,若只考虑第i件物品的策略(放或不放),那么就可以转化为一个只牵扯前i-1件物品的问题。
如果不放第i件物品,那么问题就转化为“前i-1件物品放入容量为v的背包中”,价值为f[i-1][v];
如果放第i件物品,那么问题就转化为“前i-1件物品放入剩下的容量为v-w[i]的背包中”,此时能获得的最大价值就是f[i-1][v-w[i]]再加上通过放入第i件物品获得的价值v[i]。
注意f[v]有意义当且仅当存在一个前i件物品的子集,其费用总和为v。
所以按照这个方程递推完毕后,最终的答案并不一定是f[N][V],而是f[N][0..V]的最大值。
如果将状态的定义中的“恰”字去掉,在转移方程中就要再加入一项f[v-1],这样就可以保证f[N][V]就是最后的答案。
1.背包类的设计
publicclassPackage{
privateintweight;
//背包重量
privateintvalue;
//背包价值
publicPackage(intweight,intvalue){
this.value=value;
this.weight=weight;
}
publicintgetWeight(){
returnweight;
publicintgetValue(){
returnvalue;
publicStringtoString(){
return"
[weight:
+weight+"
+"
value:
+value+"
]"
;
2.求解最优值
for(intj=0;
j<
=totalWeight;
j++){
for(inti=0;
i<
=n;
i++){
if(i==0||j==0){
bestValues[i][j]=0;
else
{
//如果第i个背包重量大于总承重,则最优解存在于前i-1个背包中,
//注意:
第i个背包是bags[i-1]
if(j<
bags[i-1].getWeight()){
bestValues[i][j]=bestValues[i-1][j];
//如果第i个背包不大于总承重,则最优解要么是包含第i个背包的最优解,
//要么是不包含第i个背包的最优解,取两者最大值,这里采用了分类讨论法
//第i个背包的重量iweight和价值ivalue
intiweight=bags[i-1].getWeight();
intivalue=bags[i-1].getValue();
bestValues[i][j]=
Math.max(bestValues[i-1][j],ivalue+bestValues[i-1][j-iweight]);
}//else
}//else
}//for
3.求解背包组成
if(bestSolution==null){
bestSolution=newArrayList<
Package>
();
inttempWeight=totalWeight;
for(inti=n;
i>
=1;
i--){
if(bestValues[i][tempWeight]>
bestValues[i-1][tempWeight]){
bestSolution.add(bags[i-1]);
//bags[i-1]表示第i个背包
tempWeight-=bags[i-1].getWeight();
if(tempWeight==0){break;
bestValue=bestValues[n][totalWeight];
设置每个物品的重量以及价值:
最终效果:
0-1背包问题是动态规划的一道经典问题,在上机实验之前我认为对理论知识已经掌握得非常完全,然而到解决寻找“最优子集”的时候还是遇到了一些麻烦。
通过这次试验我得知自己在某些方面还存在着缺陷,只是之前依照课本上的知识足够得到解决,以后还是需要多做实验。
实验六最短路径
dijkstra算法解决最短路径问题
算法描述如下:
1)令arcs表示弧上的权值。
若弧不存在,则置arcs为∞(在本程序中为MAXCOST)。
S为已找到的从出发的的终点的集合,初始状态为空集。
那么,从出发到图上其余各顶点可能达到的长度的初值为D=arcs[LocateVex(G,)],∈V;
2)选择,使得D=Min{D|∈V-S};
3)修改从出发的到集合V-S中任一顶点的最短路径长度。
1.数据结构和之前几个实验的图结构一模一样,值得注意的是
publicintweight;
这个变量是在边类里的,在dijkstra算法里需要初始化为一个极大值。
publicbooleanifclosed=false;
这个变量在节点类里,用来判断节点是否已经关闭。
2.查找两个节点之间的权值
publicintfind_weight(GraphG,intu,intv){//返回两个节点的权值
ArcNodep=G.arrVnode[u].nextarc;
if(p.adjvex==v){
从"
+u+"
到"
+v+"
的权值:
+p.weight);
returnp.weight;
while(p.nextarc!
=null){
p=p.nextarc;
if(p.adjvex==v){
returnp.weight;
return10000;
3.松弛、更改节点最小距离
publicvoidRelax(GraphG,intu,intv,intw){
intdistance1=G.arrVnode[u].distance;
intdistance2=G.arrVnode[v].distance;
if(distance2>
distance1+w){
G.arrVnode[v].distance=distance1+w;
System.out.println(G.arrVnode[v].data+"
更改距离为:
+G.arrVnode[v].distance);
G.arrVnode[v].front=u;
4.dijkstra类
publicvoidDijkstra1(GraphG,intv){
G.arrVnode[v].distance=0;
G.arrVnode[v].ifclosed=true;
VNode[]S=newVNode[100];
ArcNodep=newArcNode();
intcount=1;
System.out.println(count);
S[count]=G.arrVnode[v];
System.out.println(v+"
的距离:
+S[count].distance);
if(G.arrVnode[v].nextarc!
p=G.arrVnode[v].nextarc;
}else{return;
//设置一个判断方法,判断是否在表S,若
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 中南 大学 算法 实验 报告