实验03 贪心算法
一、实验目的
1.掌握贪心算法的基本思想
2.掌握贪心算法中贪心选择性质和最优子结构性质的分析与证明
3.掌握贪心算法求解问题的方法
二、实验内容
1.认真阅读算法设计教材,了解贪心算法思想及方法;
2.设计用贪心算法求解最优装载哈夫曼编码、单源最短路径、最小生成树的
java程序
三、求解的问题
1.哈夫曼编码是广泛地用于数据文件压缩的十分有效的编码方法。
给出文件中
各个字符出现的频率，求各个字符的哈夫曼编码方案。
2.给定带权有向图G =(V,E)，其中每条边的权是非负实数。
另外，还给定V
中的一个顶点，称为源。
现在要计算从源到所有其他各顶点的最短路长度。
这里路的长度是指路上各边权之和。
3.设G =(V,E)是无向连通带权图，即一个网络。
E中每条边(v,w)的权为
c[v][w]。
如果G的子图G’是一棵包含G的所有顶点的树，则称G’为G的生成树。
生成树上各边权的总和称为该生成树的耗费。
在G的所有生成树中，耗费最小的生成树称为G的最小生成树。
求G的最小生成树。
四、实验程序
1．哈夫曼编码
哈夫曼算法以自底向上的方式构造表示最优前缀码的二叉树T。
算法以|C|个叶结点开始，执行|C|-1次的“合并”运算后产生最终所要求的树T。
下面所给出的算法huffmanTree中，编码字符集中的每一字符c的频率是f（c）。
以f 为键值的优先队列Q用在贪心选择时有效地确定算法当前要合并的两棵具有最小频率的树。
一旦两棵具有最小频率的树合并后，产生一棵新的树，其频率为合并两棵树的频率之和，并将新树插入优先队列Q。
private static class Huffman implements Comparable{
Bintree tree; float weight;
private Huffman(Bintree tt,float ww) {
tree=tt;weight=ww; }
public int compareTo(Object x){
float xw=((Huffman) x).weight; if(weight<xw)return -1;
if(weight==xw) return 0;return 1;}}
public static Bintree huffmanTree(float []f){
int n=f.length; Huffman []w=new Huffman [n+1];
Bintree zero=new Bintree(); for(int i=0;i<n;i++)
{ Bintree x=new Bintree();
x.makeTree(new MyInterger(i),zero,zero);
w[i+1]=new Huffman(x,f[i]); }
MinHeap H =new MinHeap();H.initialize(w,n);
for(int i=0;i<n;i++){
Huffman x=(Huffman) H.removeMin(); HUffman y=(Huffman) H.removeMin();
Bintree z=new Bintree();z.makeTree(null,x.tree,y.tree);
HUffman t=new Huffman(z,x.weight+y.weight); H.put(t);}
return ((HUffman) H.removeMin()).tree;}
算法huffmanTree首先用字符集C中每一字符c的频率f（c）初始化优先队列Q。
然后不断地从优先队列Q中取出具有最小频率的两棵树x和y，将它们合并为一棵新树z。
z的频率是x和y的频率之和。
新树z以x为其左儿子，y 为其右儿子。
经过n-1次的合并后，优先队列中只剩下一棵树，即所要求的树T。
2．单源最短路径问题
Dijkstra算法的基本思想是，设置顶点集合S并不断地做贪心算法来扩充这个集合。
一个顶点属于集合S当且仅当从源到u且中间只经过S中顶点的路称为从源到u的特殊路径，并用数组dist记录当前每个顶点所对应的最短路径长度。
Dijkstra算法每次从V-S中取出具有最短特殊路长度的顶点u，将u添加到S中，同时对数组dist进行必要的修改。
一旦S包含了所有V中顶点，dist 就记录了从源到所有其他顶点之间的最短路径长度。
public static void dijkstra(int v,float[][]a,float []dist,int []prev){ int n=dist.length-1;if(v<1||v>n)return;boolean []s=new boolean [n+1];
for(int i=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;}
dise[v]=0;s[v]=true;for(int i=1;i<n;i++){
float temp=Float.MAX_VALUE; int u=v;for(int j=1;j<=n;j++)
if((! s[j])&&(dist[j]<temp)){u=j;temp=dist[j];}
s[u]=true; for(intj=1;j<=n;j++)
if((! s[j])&&(a[u][j]<Float.MAX_VALUE)){
float newdist=dist[u]+a[u][j]; if(newdist<dist[j]{
dist[j]=newdist;prev[j]=u;}}}}
3．最小生成树问题
设G=（V，E）是连通带权图，V={1，2，…,n}。
构造G的最小生成树的Prim 算法的基本思想是：首先置S{1}，然后，只要S是V的真子集，就进行如下的贪心选择：选取满足条件i∈S，j∈V-S，且c[i][j]最小的边，将顶点j添加到S中。
这个过程一直进行到S=V时为止。
过程中所取到的边恰好构成G的一棵最小生成树。
public static void prim(int n,float [][]c){
float []lowcost=new float[n+1]; int[]closest=new int[n+1];
boolean []s=new boolean[n+1];s[1]=true;
for(int i=2;i<=n;i++){ lowcost[i]=c[1][i]; losest[i]=1;s[i]=false; }
for(int i=1;i<n;i++){ float min=Float.MAX_VALUE; int j=1;
for(int k=2;k<=n;k++) if((lowcost[k]<min)&&(! s[k])){
min=lowcost[k]; j=k;}
System.out.println(j+", "+closest[j]);
s[j]=true; for(int k=2;k<=n;k++)
if((c[j][k]<lowcost[k])&&(! s[k])){
lowcost[k]=c[j][k]; closest[k]=j;}}}
五、测试数据
1．哈夫曼编码
请输入一组数据（用空格分隔）
0.13 0.19 0.26 0.03 0.07 0.01 0.31
输出结果：
0.13：011 长度：3
0.19：00 长度：2
0.26：10 长度：2
0.03：01001 长度：5
0.07：0101 长度：4
0.01：01000 长度：5
0.31：11 长度：2
2．单源最短路径
请输入顶点个数：
4
请输入顶点的权重：
2 4 -2 -4
2 4 6 -1
5 8 -3 5
-2 9 5 -7
4-2 -4
3.最小生成树
请输入结点个数：
4
输入图结点（输入-1，-1，-1退出）
1 3 5 2
2 3 5 1
3 2 5 3
3 2 1 4
-1 -1 -1 -1
第一边：2---3
第二边：1---3
第三边：0---0。