贪心算法.docx
《贪心算法.docx》由会员分享，可在线阅读，更多相关《贪心算法.docx（17页珍藏版）》请在冰点文库上搜索。
贪心算法
一、[实验目的]
掌握贪心算法的基本思想
掌握贪心算法中贪心选择性质和最优子结构性质的分析与证明
掌握贪心算法求解问题的方法
二、[实验内容]
哈夫曼编码是广泛地用于数据文件压缩的十分有效的编码方法。
给出文件中各个字符出现的频率，求各个字符的哈夫曼编码方案。
给定带权有向图G=（V,E），其中每条边的权是非负实数。
另外，还给定V中的一个顶点，称为源。
现在要计算从源到所有其他各顶点的最短路长度。
这里路的长度是指路上各边权之和。
设G=（V,E）是无向连通带权图，即一个网络。
E中每条边（v,w）的权为c[v][w]。
如果G的子图G’是一棵包含G的所有顶点的树，则称G’为G的生成树。
生成树上各边权的总和称为该生成树的耗费。
在G的所有生成树中，耗费最小的生成树称为G的最小生成树。
求G的最小生成树。
三、[算法原理]
1.哈夫曼编码
1.1前缀码
对每一个字符规定一个0,1串作为其代码，并要求任一字符的代码都不是其他字符代码的前缀。
这种编码称为前缀码。
编码的前缀性质可以使译码方法非常简单。
表示最优前缀码的二叉树总是一棵完全二叉树，即树中任一结点都有2个儿子结点。
平均码长定义为：
使平均码长达到最小的前缀码编码方案称为给定编码字符集C的最优前缀码。
1.2.构造哈夫曼编码
哈夫曼提出构造最优前缀码的贪心算法，由此产生的编码方案称为哈夫曼编码。
哈夫曼算法以自底向上的方式构造表示最优前缀码的二叉树T。
算法以|C|个叶结点开始，执行|C|－1次的“合并”运算后产生最终所要求的树T。
2.单源最短路径
2.1.算法基本思想
Dijkstra算法是解单源最短路径问题的贪心算法。
其基本思想是，设置顶点集合S并不断地作贪心选择来扩充这个集合。
一个顶点属于集合S当且仅当从源到该顶点的最短路径长度已知。
初始时，S中仅含有源。
设u是G的某一个顶点，把从源到u且中间只经过S中顶点的路称为从源到u的特殊路径，并用数组dist记录当前每个顶点所对应的最短特殊路径长度。
Dijkstra算法每次从V-S中取出具有最短特殊路长度的顶点u，将u添加到S中，同时对数组dist作必要的修改。
一旦S包含了所有V中顶点，dist就记录了从源到所有其他顶点之间的最短路径长度。
2.2.算法的正确性和计算复杂性
（1）贪心选择性质
（2）最优子结构性质（3）计算复杂性。
3.最小生成树
3.1.最小生成树性质
用贪心算法设计策略可以设计出构造最小生成树的有效算法。
本节介绍的构造最小生成树的Prim算法和Kruskal算法都可以看作是应用贪心算法设计策略的例子。
尽管这2个算法做贪心选择的方式不同，它们都利用了下面的最小生成树性质：
设G=（V,E）是连通带权图，U是V的真子集。
如果（u,v）E，且uU，vV-U，且在所有这样的边中，（u,v）的权c[u][v]最小，那么一定存在G的一棵最小生成树，它以（u,v）为其中一条边。
这个性质有时也称为MST性质。
3.2.Prim算法
设G=（V,E）是连通带权图，V={1,2,…,n}。
构造G的最小生成树的Prim算法的基本思想是：
首先置S={1}，然后，只要S是V的真子集，就作如下的贪心选择：
选取满足条件iS，jV-S，且c[i][j]最小的边，将顶点j添加到S中。
这个过程一直进行到S=V时为止。
在这个过程中选取到的所有边恰好构成G的一棵最小生成树。
3.3.Kruskal算法
Kruskal算法构造G的最小生成树的基本思想是，首先将G的n个顶点看成n个孤立的连通分支。
将所有的边按权从小到大排序。
然后从第一条边开始，依边权递增的顺序查看每一条边，并按下述方法连接2个不同的连通分支：
当查看到第k条边（v,w）时，如果端点v和w分别是当前2个不同的连通分支T1和T2中的顶点时，就用边（v,w）将T1和T2连接成一个连通分支，然后继续查看第k+1条边；如果端点v和w在当前的同一个连通分支中，就直接再查看第k+1条边。
这个过程一直进行到只剩下一个连通分支时为止。
四、[实验代码]
1.哈夫曼编码
packageArith_Sort;
importjava.util.ArrayList;
importjava.util.List;
publicclassHoffmann{
/**
*哈夫曼算法—java实现
*/
publicstaticvoidmain（String[]args）{
/*****************初始化树**********************/
int[]A={1,2,3,5};
char[]C={'a','b','c','d'};
ListTree=newArrayList（）;
for（inti=0;i{
TreeNodetreeNode=newTreeNode（A[i],C[i]+""）;
Tree.add（treeNode）;
}
/*****************初始化树**********************/
//开始建树
（newHoffmann（））.buildTree（Tree,0,A.length）;
//获得最小生成树的根节点
TreeNodetreeNode=（TreeNode）Tree.get（Tree.size（）-1）;
//遍历这棵树，同时给出每个字符对应的编码
（newHoffmann（））.seekTree（treeNode,""）;
}
publicvoidseekTree（TreeNodetreeNode,Stringcode）
{
if（treeNode!
=null）
{
seekTree（treeNode.getLeftNode（）,code+"0"）;
if（treeNode.getCharValue（）!
=null）
System.out.println（"字符：
"+treeNode.getCharValue（）+"频数：
"+treeNode.getNodeValue（）+"编码：
"+code）;
seekTree（treeNode.getRightNode（）,code+"1"）;
}
}
/**
*建立最小生成树将两个节点组合而成的节点添置列表末尾，新一轮的排序起始位置向后移两位，自由节点数目减少1
*@paramTree
*@paramstart排序列表中剩余自由节点的起始位置
*@paramfreeNodeNum列表中的自由节点数量
*/
publicvoidbuildTree（ListTree,intstart,intfreeNodeNum）
{
if（Tree!
=null&&freeNodeNum>=2）
{
QuickSort（Tree,start,Tree.size（）-1）;
//取权值最小的两个节点组合成为新节点，根据排序规则，最小的两个数位于列表的前两位
TreeNodenewNode=newTreeNode（（（TreeNode）Tree.get（start））.getNodeValue（）+（（TreeNode）Tree.get（start+1））.getNodeValue（）,null）;
newNode.setLeftNode（（TreeNode）Tree.get（start））;
newNode.setRightNode（（TreeNode）Tree.get（start+1））;
Tree.add（newNode）;//将两个节点组合而成的节点添置列表末尾
freeNodeNum--;//自由节点数减一
buildTree（Tree,start+2,freeNodeNum）;
}
}
/**
*快速排序方法实现
*@paramTree
*@paramp
*@paramr
*/
publicvoidQuickSort（ListTree,intp,intr）
{
intq=0;
if（p{
q=partion（Tree,p,r）;
QuickSort（Tree,p,q-1）;
QuickSort（Tree,q+1,r）;
}
}
publicintpartion（ListTree,intp,intr）
{
intx=（（TreeNode）Tree.get（r））.getNodeValue（）;
inti=p-1;
for（intj=p;j<=r-1;j++）
{
//换个方向就是从大到小
if（（（TreeNode）Tree.get（j））.getNodeValue（）<=x）
{
i++;
Objecttemp=Tree.get（i）;
Tree.set（i,Tree.get（j））;
Tree.set（j,temp）;
}
}
Objecttemp=Tree.get（i+1）;
Tree.set（i+1,Tree.get（r））;
Tree.set（r,temp）;
returni+1;
}
}
/**
*节点类
*@authors001
*
*/
classTreeNode{
//左节点
TreeNodeleftNode;
//右节点
TreeNoderightNode;
//节点值-频度
intnodeValue;
StringcharValue;
publicTreeNode（intnodeValue,StringcharValue）
{
this.nodeValue=nodeValue;
this.charValue=charValue;
}
publicStringgetCharValue（）{
returncharValue;
}
publicvoidsetCharValue（StringcharValue）{
this.charValue=charValue;
}
publicTreeNodegetLeftNode（）{
returnleftNode;
}
publicvoidsetLeftNode（TreeNodeleftNode）{
this.leftNode=leftNode;
}
publicTreeNodegetRightNode（）{
returnrightNode;
}
publicvoidsetRightNode（TreeNoderightNode）{
this.rightNode=rightNode;
}
publicintgetNodeValue（）{
returnnodeValue;
}
publicvoidsetNodeValue（intnodeValue）{
this.nodeValue=nodeValue;
}
}
2.单源最短路径
importjava.util.Scanner;
publicclassDijkstra{
privatestaticintn;//G图中的顶点个数
privatestaticint[]distent=null;//最短路径长度
privatestaticint[]previous=null;//前驱顶点集合
publicstaticvoidDijkstras（intv,int[][]a,int[]dist,int[]prev）
{
//单元最短路径的Dijkstra算法
intn=dist.length-1;
if（v<1||v>n）return;
boolean[]s=newboolean[n+1];
//初始化
for（inti=1;i<=n;i++）
{
dist[i]=a[v][i];
s[i]=false;
if（dist[i]==Float.MAX_VALUE）
prev[i]=0;
else
prev[i]=v;
}
dist[v]=0;
s[v]=true;
for（inti=1;ifloattemp=Float.MAX_VALUE;
intu=v;
for（intj=1;j<=n;j++）
if（（!
s[j]）&&（dist[j]u=j;
temp=dist[j];
}
s[u]=true;
for（intj=1;j<=n;j++）
if（（!
s[j]）&&（a[u][j]{
intnewdist=dist[u]+a[u][j];
if（newdistdist[j]=newdist;
prev[j]=u;
}}}
for（intk=2;kSystem.out.print（dist[k]+""）;
}System.out.println（dist[n]）;}
publicstaticvoidmain（String[]args）{
//TODOAuto-generatedmethodstub
intv=1;
Scannersc=newScanner（System.in）;
System.out.println（"请输入定点个数:
"）;
Stringline=sc.nextLine（）;
n=Integer.parseInt（line）;
distent=newint[n+1];
previous=newint[n+1];
inta[][]=newint[n+1][n+1];
System.out.println（"请输入顶点的权重:
"）;
for（inti=1;i<=n;i++）{
line=sc.nextLine（）;
String[]str=line.split（""）;
for（intj=1;j<=str.length;j++）{
a[i][j]=Integer.parseInt（str[j-1]）;
}}
Dijkstras（v,a,distent,previous）;
}
}
3.最小生成树
importjava.util.Scanner;
importjava.util.Arrays;
importjava.util.ArrayList;
publicclassPrim{
privatestaticintMAX=100;
privatedoublecost[][]=newdouble[MAX][MAX];
privateArrayListedge=newArrayList（）;
privateint[]near=newint[MAX];
privatestaticdoubleINFINITY=99999999.99;//定义无穷大
privatedoublemincost=0.0;//最小成本
privateintn;//结点个数
publicPrim（）{}
publicstaticvoidmain（Stringargs[]）{
Primsp=newPrim（）;
sp.init（）;
sp.prim（）;
sp.print（）;
}
publicvoidinit（）{
Scannerscan=newScanner（System.in）;
intp,q,w;
System.out.println（"spanningtreebegin!
Inputthenodenumber:
"）;
n=scan.nextInt（）;
//二维数组的填充要注意
for（inti=0;iArrays.fill（cost[i],INFINITY）;}
System.out.println（"Inputthegraph（-1,-1,-1toexit）"）;
while（true）{p=scan.nextInt（）;q=scan.nextInt（）;
w=scan.nextInt（）;
if（p<0||q<0||w<0）{
break;
}cost[p][q]=w;cost[q][p]=w;
}
Edgetmp=getMinCostEdge（）;
edge.add（tmp）;p=tmp.start;
q=tmp.end;mincost=cost[p][q];
for（inti=1;i<=n;++i）{
if（cost[i][p]near[i]=p;
}else{
near[i]=q;
}
}
near[p]=near[q]=0;
}
//寻找最小成本的边
publicEdgegetMinCostEdge（）{
Edgetmp=newEdge（）;
doublemin=INFINITY;
for（inti=1;ifor（intj=i+1;j<=n;++j）{
if（cost[i][j]min=cost[i][j];
tmp.start=i;
tmp.end=j;}}
}
//System.out.println（min）;
returntmp;
}
//prim算法主体
publicvoidprim（）{
//找剩下的n-2条边
for（inti=2;idoublemin=INFINITY;
Edgetmp=newEdge（）;
for（intj=1;j<=n;++j）{
if（near[j]!
=0&&cost[j][near[j]]tmp.start=j;
tmp.end=near[j];
min=cost[j][near[j]];
}
}
mincost+=cost[tmp.start][tmp.end];
edge.add（tmp）;
near[tmp.start]=0;
for（intk=1;k<=n;++k）{
if（near[k]!
=0&&cost[k][near[k]]>cost[k][tmp.start]）{
near[k]=tmp.start;
}
}
}
if（mincost>=INFINITY）{
System.out.println（"nospanningtree"）;
}
}
//打印结果
publicvoidprint（）{
for（inti=0;iEdgee=edge.get（i）;
System.out.println（"the"+（i+1）+"thedge:
"+e.start+"---"+e.end）;
}
}
}
classEdge
{
publicintstart;//始边
publicintend;//终边
}
五、[实验结果]
1.哈夫曼编码
请输入一组数，中间用空格分隔：
0.010.030.070.130.190.260.31
输出结果为：
0.01:
01000码长：
5
0.03:
01001码长：
5
0.07:
0101码长：
4
0.13:
011码长：
3
0.19:
00码长：
2
0.26:
10码长：
2
0.31:
11码长：
2
2.单源最短路径
请输入定点个数:
4
请输入顶点的权重:
24-2-4
246-1
58-35
-295-7
4-2-4
3.最小生成树
spanningtreebegin!
Inputthenodenumber:
4
Inputthegraph（-1,-1,-1toexit）
1352
2351
3253
3214
-1-1-1-1
the1thedge:
2---3
the2thedge:
1---3
the3thedge:
0---0
升级会员 