贪心算法.docx

1、贪心算法一、实验目的掌握贪心算法的基本思想掌握贪心算法中贪心选择性质和最优子结构性质的分析与证明掌握贪心算法求解问题的方法二、实验内容哈夫曼编码是广泛地用于数据文件压缩的十分有效的编码方法。给出文件中各个字符出现的频率，求各个字符的哈夫曼编码方案。给定带权有向图G =(V,E)，其中每条边的权是非负实数。另外，还给定V中的一个顶点，称为源。现在要计算从源到所有其他各顶点的最短路长度。这里路的长度是指路上各边权之和。设G =(V,E)是无向连通带权图，即一个网络。E中每条边(v,w)的权为cvw。如果G的子图G是一棵包含G的所有顶点的树，则称G为G的生成树。生成树上各边权的总和称为该生成树的耗费

2、。在G的所有生成树中，耗费最小的生成树称为G的最小生成树。求G的最小生成树。三、算法原理1. 哈夫曼编码1.1前缀码对每一个字符规定一个0,1串作为其代码，并要求任一字符的代码都不是其他字符代码的前缀。这种编码称为前缀码。编码的前缀性质可以使译码方法非常简单。 表示最优前缀码的二叉树总是一棵完全二叉树，即树中任一结点都有2个儿子结点。平均码长定义为：使平均码长达到最小的前缀码编码方案称为给定编码字符集C的最优前缀码。1.2.构造哈夫曼编码哈夫曼提出构造最优前缀码的贪心算法，由此产生的编码方案称为哈夫曼编码。哈夫曼算法以自底向上的方式构造表示最优前缀码的二叉树T。算法以|C|个叶结点开始，执行|

3、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就记录了从源到所有其他顶点之间的最

4、短路径长度。2.2.算法的正确性和计算复杂性(1)贪心选择性质(2)最优子结构性质(3)计算复杂性 。3. 最小生成树 3.1.最小生成树性质用贪心算法设计策略可以设计出构造最小生成树的有效算法。本节介绍的构造最小生成树的Prim算法和Kruskal算法都可以看作是应用贪心算法设计策略的例子。尽管这2个算法做贪心选择的方式不同，它们都利用了下面的最小生成树性质：设G=(V,E)是连通带权图，U是V的真子集。如果(u,v)E，且uU，vV-U，且在所有这样的边中，(u,v)的权cuv最小，那么一定存在G的一棵最小生成树，它以(u,v)为其中一条边。这个性质有时也称为MST性质。 3.2.Prim

5、算法 设G=(V,E)是连通带权图，V=1,2,n。构造G的最小生成树的Prim算法的基本思想是：首先置S=1，然后，只要S是V的真子集，就作如下的贪心选择：选取满足条件iS，jV-S，且cij最小的边，将顶点j添加到S中。这个过程一直进行到S=V时为止。在这个过程中选取到的所有边恰好构成G的一棵最小生成树。 3.3.Kruskal算法Kruskal算法构造G的最小生成树的基本思想是，首先将G的n个顶点看成n个孤立的连通分支。将所有的边按权从小到大排序。然后从第一条边开始，依边权递增的顺序查看每一条边，并按下述方法连接2个不同的连通分支：当查看到第k条边(v,w)时，如果端点v和w分别是当前2

6、个不同的连通分支T1和T2中的顶点时，就用边(v,w)将T1和T2连接成一个连通分支，然后继续查看第k+1条边；如果端点v和w在当前的同一个连通分支中，就直接再查看第k+1条边。这个过程一直进行到只剩下一个连通分支时为止。 四、实验代码1. 哈夫曼编码package Arith_Sort;import java.util.ArrayList;import java.util.List;public class Hoffmann /* * 哈夫曼算法java实现 */ public static void main(String args) /*初始化树*/ int A=1,2,3,5; cha

7、r C=a,b,c,d; List Tree=new ArrayList(); for(int i=0;i=2) QuickSort(Tree,start,Tree.size()-1); /取权值最小的两个节点组合成为新节点，根据排序规则，最小的两个数位于列表的前两位 TreeNode newNode=new TreeNode(TreeNode)Tree.get(start).getNodeValue()+(TreeNode)Tree.get(start+1).getNodeValue(),null); newNode.setLeftNode(TreeNode)Tree.get(start);

8、 newNode.setRightNode(TreeNode)Tree.get(start+1); Tree.add(newNode); /将两个节点组合而成的节点添置列表末尾 freeNodeNum-; /自由节点数减一 buildTree(Tree,start+2,freeNodeNum); /* * 快速排序方法实现 * param Tree * param p * param r */ public void QuickSort(List Tree,int p,int r) int q=0; if(pr) q=partion(Tree,p,r); QuickSort(Tree,p,q-

9、1); QuickSort(Tree,q+1,r); public int partion(List Tree,int p,int r) int x=(TreeNode)Tree.get(r).getNodeValue(); int i=p-1; for(int j=p;j=r-1;j+) /换个方向就是从大到小 if(TreeNode)Tree.get(j).getNodeValue()=x) i+; Object temp=Tree.get(i); Tree.set(i, Tree.get(j); Tree.set(j, temp); Object temp=Tree.get(i+1);

10、Tree.set(i+1, Tree.get(r); Tree.set(r, temp); return i+1; /* * 节点类 * author s001 * */class TreeNode /左节点 TreeNode leftNode; /右节点 TreeNode rightNode; /节点值-频度 int nodeValue; String charValue; public TreeNode(int nodeValue,String charValue ) this.nodeValue=nodeValue; this.charValue=charValue; public St

11、ring getCharValue() return charValue; public void setCharValue(String charValue) this.charValue = charValue; public TreeNode getLeftNode() return leftNode; public void setLeftNode(TreeNode leftNode) this.leftNode = leftNode; public TreeNode getRightNode() return rightNode; public void setRightNode(T

12、reeNode rightNode) this.rightNode = rightNode; public int getNodeValue() return nodeValue; public void setNodeValue(int nodeValue) this.nodeValue = nodeValue; 2. 单源最短路径import java.util.Scanner;public class Dijkstra private static int n;/ G图中的顶点个数private static int distent = null;/ 最短路径长度private stat

13、ic int previous = null;/ 前驱顶点集合public static void Dijkstras(int v, int a, int dist, int prev)/ 单元最短路径的Dijkstra算法int n = dist.length - 1;if (v n)return;boolean s = new booleann + 1;/ 初始化 for (int i = 1; i = n; i+) disti = avi; si = false; if(disti =Float.MAX_VALUE) previ = 0; else previ = v;distv = 0

14、;sv = true;for (int i = 1; i n; i+) float temp = Float.MAX_VALUE;int u = v;for (int j = 1; j = n; j+)if (!sj) & (distj temp)u = j;temp = distj;su = true;for (int j = 1; j = n; j+)if (!sj) & (aujFloat.MIN_VALUE)int newdist = distu + auj;if (newdist distj ) distj = newdist;prevj = u;for(int k = 2;k n;

15、k+)System.out.print(distk+ );System.out.println(distn);public static void main(String args) / TODO Auto-generated method stubint v = 1;Scanner sc = new Scanner(System.in);System.out.println(请输入定点个数:);String line = sc.nextLine();n = Integer.parseInt(line);distent = new int n + 1;previous = new int n

16、+ 1;int a = new int n + 1n + 1;System.out.println(请输入顶点的权重:);for(int i = 1;i = n;i+)line = sc.nextLine();String str = line.split( );for(int j=1;j=str.length;j+) aij=Integer.parseInt(strj - 1);Dijkstras(v,a,distent,previous);3. 最小生成树import java.util.Scanner;import java.util.Arrays;import java.util.Ar

17、rayList;public class Prim private static int MAX = 100; private double cost = new doubleMAXMAX; private ArrayList edge = new ArrayList(); private int near = new intMAX; private static double INFINITY = 99999999.99;/定义无穷大 private double mincost = 0.0;/最小成本 private int n;/结点个数 public Prim() public sta

18、tic void main(String args) Prim sp = new Prim(); sp.init(); sp.prim(); sp.print(); public void init() Scanner scan = new Scanner(System.in); int p,q,w; System.out.println(spanning tree begin!Input the node number:); n = scan.nextInt(); /二维数组的填充要注意 for(int i = 0; i MAX; +i) Arrays.fill(costi,INFINITY

19、); System.out.println(Input the graph(-1,-1,-1 to exit); while(true) p = scan.nextInt(); q = scan.nextInt(); w = scan.nextInt(); if(p 0 | q 0 | w 0) break; costpq = w; costqp = w; Edge tmp = getMinCostEdge(); edge.add(tmp); p = tmp.start; q = tmp.end; mincost = costpq; for(int i = 1; i = n; +i) if(c

20、ostip costiq) neari = p; else neari = q; nearp = nearq = 0; /寻找最小成本的边 public Edge getMinCostEdge() Edge tmp = new Edge(); double min = INFINITY; for(int i = 1; i n; +i) for(int j = i+1; j = n; +j) if(costij min) min = costij; tmp.start = i; tmp.end = j; /System.out.println(min); return tmp; /prim算法主

21、体 public void prim() /找剩下的n-2条边 for(int i = 2; i n; +i) double min = INFINITY; Edge tmp = new Edge(); for(int j = 1; j = n; +j) if(nearj != 0 & costjnearj min) tmp.start = j; tmp.end = nearj; min = costjnearj; mincost += costtmp.starttmp.end; edge.add(tmp); neartmp.start = 0; for(int k = 1; k costkt

22、mp.start) neark = tmp.start; if(mincost = INFINITY) System.out.println(no spanning tree); /打印结果 public void print() for(int i = 0; i edge.size(); +i) Edge e = edge.get(i); System.out.println(the + (i+1) + th edge: + e.start + - + e.end); class Edge public int start;/始边 public int end;/终边 五、实验结果1. 哈夫

23、曼编码请输入一组数，中间用空格分隔：0.01 0.03 0.07 0.13 0.19 0.26 0.31输出结果为：0.01 : 01000 码长：50.03 : 01001 码长：50.07 : 0101 码长：40.13 : 011 码长：30.19 : 00 码长：20.26 : 10 码长：20.31 : 11 码长：22. 单源最短路径请输入定点个数:4请输入顶点的权重:2 4 -2 -42 4 6 -15 8 -3 5-2 9 5 -74 -2 -43. 最小生成树 spanning tree begin!Input the node number:4Input the graph(-1,-1,-1 to exit)1 3 5 22 3 5 13 2 5 33 2 1 4-1 -1 -1 -1the 1th edge:2-3the 2th edge:1-3the 3th edge:0-0