贪心算法
一、[实验目的]
掌握贪心算法的基本思想
掌握贪心算法中贪心选择性质和最优子结构性质的
分析
定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析
与证明
掌握贪心算法求解问题的
方法
快递客服问题件处理详细方法山木方法pdf计算方法pdf华与华方法下载八字理论方法下载
二、[实验
内容
财务内部控制制度的内容财务内部控制制度的内容人员招聘与配置的内容项目成本控制的内容消防安全演练内容
]
哈夫曼编码是广泛地用于数据文件压缩的十分有效的编码方法。给出文件中各个字符出现的频率，求各个字符的哈夫曼编码
方案
气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载
。
给定带权有向图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串作为其代码，并要求任一字符的代码都不是其他字符代码的前缀。这种编码称为前缀码。
编码的前缀性质可以使译码方法非常简单。
表
关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf
示最优前缀码的二叉树总是一棵完全二叉树，即树中任一结点都有2个儿子结点。 平均码长定义为: B(T),f(c)d(c),T,cC使平均码长达到最小的前缀码编码方案称为给定编码字符集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，且u,U，v,V-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的真子集，就作如下的贪心选择:选取满足条件i,S，j,V-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. 哈夫曼编码
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class Huffman {
private List
nums;
private List numsMo;
private List trees;
private String temp;
public Huffman() {
nums = new ArrayList();
numsMo = new ArrayList();
trees = new ArrayList();
temp="";
}
public void addNums() {// 给定一组数
System.out.println("请输入一组数，中间用空格分隔:");
Scanner sca = new Scanner(System.in);
String str = sca.nextLine();
String[] strs = str.split(" ");
for (int i = 0; i < strs.length; i++) {
nums.add(Double.parseDouble(strs[i]));
numsMo.add(Double.parseDouble(strs[i])); }
}
public void compareNum(List nums,List trees) {// 递归算法
double[] min = new double[2];
if(nums.size()>1){
min = minTwo(nums);
Tree t = new Tree(min[0],min[1],min[0]+min[1]);
nums.remove(Double.valueOf(min[0]));
nums.remove(Double.valueOf(min[1]));
nums.add(min[0]+min[1]);
trees.add(t);
compareNum(nums,trees);
}
}
public void print(double num) {// 递归打印编码
for(Tree t : trees){
if(num == t.getRchild()){
temp = 1+temp;
print(t.getParents());
break;
}else if(num == t.getLchild()){
temp = 0+temp;
print(t.getParents());
break;
}
}
}
public void write(double d){
temp = "";
System.out.print(d+" : ");
print(d);
System.out.print(temp);
System.out.println(" 码长:"+temp.length());
}
public double[] minTwo(List nums) {// 在一组数中选则最小的两个，按递增排序返回
Double temp = 0.0;
for (int j = 0; j < 2; j++) {
for (int i = 1; i < nums.size(); i++) {
if (nums.get(i - 1) < nums.get(i)) {
temp = nums.get(i);
nums.set(i, nums.get(i - 1));
nums.set(i - 1, temp);
}
}
}
double[] n = {nums.get(nums.size()-1),nums.get(nums.size()-2)};
return n;
}
public void start(){
addNums();
compareNum(nums,trees);
while(numsMo.size()>1){
double[] mins = minTwo(numsMo);
if(mins[0]!=mins[1]){
numsMo.remove(Double.valueOf(mins[0]));
write(mins[0]);
}
}
if(!numsMo.isEmpty()){
write(numsMo.get(0));
}
}
public static void main(String[] args){
new Huffman().start();
}
}
2. 单源最短路径
import java.util.Scanner; public class Dijkstra { private static int n;// G图中的顶点个数
private static int[] distent = null;// 最短路径长度
private static int[] previous = null;// 前驱顶点集合
public static void Dijkstras(int v, int[][] a, int[] dist, int[] prev)
{
// 单元最短路径的Dijkstra算法
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;
}
dist[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 (int j = 1; j <= n; j++) if ((!s[j]) && (a[u][j] edge = new ArrayList();
private int[] near = new int[MAX];
private static double INFINITY = 99999999.99;//定义无穷大
private double mincost = 0.0;//最小成本
private int n;//结点个数
public Prim(){}
public static 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(cost[i],INFINITY); }
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;
} cost[p][q] = w; cost[q][p] = w;
}
Edge tmp = getMinCostEdge();
edge.add(tmp); p = tmp.start;
q = tmp.end; mincost = cost[p][q];
for(int i = 1; i <= n; ++i){
if(cost[i][p] < cost[i][q]){
near[i] = p;
}else{
near[i] = q;
}
}
near[p] = near[q] = 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(cost[i][j] < min){
min = cost[i][j];
tmp.start = i;
tmp.end = j; } }
}
//System.out.println(min);
return tmp;
}
//prim算法主体
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(near[j] != 0 && cost[j][near[j]] < min){
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(int k = 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("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. 哈夫曼编码
请输入一组数，中间用空格分隔:
0.01 0.03 0.07 0.13 0.19 0.26 0.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
请输入顶点的权重: 2 4 -2 -4 2 4 6 -1
5 8 -3 5
-2 9 5 -7 4 -2 -4
3. 最小生成树
spanning tree begin!Input the node number:
4
Input the graph(-1,-1,-1 to exit)
1 3 5 2
2 3 5 1
3 2 5 3
3 2 1 4
-1 -1 -1 -1
the 1th edge:2---3
the 2th edge:1---3
the 3th edge:0---0
浙公网安备 33021202002483