文章目录

  上次课老师讲了贪心算法,贪心算法的基本思路很简单,最接近没有学习算法的人的一般思维模式,因而也最好理解,核心的思路是总是作出当前看来最好的选择。

  可用贪心算法解决的经典问题有:活动安排问题、Dijkstra算法、Prim算法、Kruskal算法、Haffman编码等。

  活动安排问题的实现如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
package greedyAlgorithm;

import java.util.Arrays;

/**
* 活动安排问题的贪心算法求解
* @author jrhu05
*
*/
public class ActivityArrangement {
public static void main(String[] args) {
int[] start={1,3,0,5,3,5,6,8,8,2,12};
int[] end={4,5,6,7,8,9,10,11,12,13,14};
int[] arrangement=greedyArrangement(start,end);
System.out.println("the arrangement is:"+Arrays.toString(arrangement));
}

public static int[] greedyArrangement(int[] s,int[] e) {
int total=s.length;
int endFlag=e[0];
int[] arrangement=new int[total];
arrangement[0]=1;
int arrangeCount=1;
for (int i = 0; i < s.length; i++) {
if(s[i]>endFlag){
arrangement[arrangeCount]=i+1;
arrangeCount+=1;
endFlag=e[i];
}
}
return arrangement;
}

}

  Dijkstra算法是经典的求单源点最短路径的算法,其java实现如下(用邻接矩阵来表示有向图):

  本例中的有向图如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
package greedyAlgorithm;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Set;
/**
* 单源点最短路径Dijkstra算法实现
* @author jrhu05
*
*/
public class Dijkstra {
private static int maxD=Integer.MAX_VALUE;
private static int minD=0;
private static HashMap<Integer, Integer> distanceMap;
private static Set<Integer> findedSet;
private static int[] pre;
public static void main(String[] args) {
int[][] matrix={{maxD,10,maxD,30,100},
{maxD,maxD,50,maxD,maxD},
{maxD,maxD,maxD,maxD,10},
{maxD,maxD,20,maxD,60},
{maxD,maxD,maxD,maxD,maxD}};
int start=1;//从哪一个点开始找
dijkstraFind(matrix, start-1);
for (int i = 0; i < pre.length; i++) {
pre[i]+=1;
}
for(Entry<Integer, Integer> entry:distanceMap.entrySet()){
if (entry.getKey()!=start-1) {
System.out.println("start to "+(entry.getKey()+1)+" dis "+entry.getValue());
System.out.print("path:"+(entry.getKey()+1));
printPath(pre, entry.getKey());
System.out.println();
}
}

}

public static void printPath(int[] pre,int i) {
if(pre[i]!=0) {
System.out.print("-->"+(pre[i]));
printPath(pre, pre[i]-1);
}
}

public static Map<Integer, Integer> dijkstraFind(int[][] matrix,int start) {
pre=new int[matrix.length];
pre[start]=-1;
// 用来存放起始点到其它点当前的距离
distanceMap = new HashMap<Integer, Integer>();
// 用来存放已经找到最短路径的点的集合
findedSet = new HashSet<Integer>();
findedSet.add(start);
// 用start相邻的点初始化distanceMap
for (int i = 0; i < matrix.length; i++) {
distanceMap.put(i, matrix[start][i]);
}
// for(Entry<Integer, Integer> entry:distanceMap.entrySet()){
// System.out.println(entry.getKey()+"--->"+entry.getValue());
// }
while (findedSet.size() != matrix.length) {
int currentMinIndex = currentMinIndex();
// 用此结点更新其它结点的距离
for (int i = 0; i < matrix.length; i++) {
if (!findedSet.contains(i) && matrix[currentMinIndex][i] != maxD
&& matrix[currentMinIndex][i] + distanceMap.get(currentMinIndex) < distanceMap.get(i))
{ distanceMap.put(i, matrix[currentMinIndex][i] + distanceMap.get(currentMinIndex));
pre[i]=currentMinIndex;}
}
// 放入findedset
findedSet.add(currentMinIndex);
}
return distanceMap;
}

// 返回当前最小距离的点(必须不包含在findedSet中)
private static int currentMinIndex() {
// TODO 自动生成的方法存根
Iterator<Entry<Integer, Integer>> it = distanceMap.entrySet().iterator();
int min = Integer.MAX_VALUE;
int minIndex = -1;
while (it.hasNext()) {
Entry<Integer, Integer> entry = it.next();
if (!findedSet.contains(entry.getKey()) && entry.getValue() < min) {
min = entry.getValue();
minIndex = entry.getKey();
}
}
return minIndex;
}
}

  输出如下:

  Prim算法和Kruskal算法都是为了解决无向图最小生成树问题所设计的算法,所以该部分实例用同一个无向图来进行计算,还是用邻接矩阵来表示该无向图。

  该无向图如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
Prim算法实现:
package greedyAlgorithm;
/**
* prim算法的java实现
* @author jrhu05
*
*/
public class Prim {
static int MAX = Integer.MAX_VALUE;

public static void main(String[] args) {
int[][] map = new int[][]{
{MAX,6,1,5,MAX,MAX},
{6,MAX,5,MAX,3,MAX},
{1,5,MAX,5,6,4},
{5,MAX,5,MAX,MAX,2},
{MAX,3,6,MAX,MAX,6},
{MAX,MAX,4,2,6,MAX},
};
prim(map, map.length);
}

public static void prim(int[][] graph, int n){

char[] c = new char[]{'1','2','3','4','5','6'};
int[] lowcost = new int[n];
int[] mst = new int[n];
int i, j, min, minid, sum = 0;

for(i = 1; i < n; i++){
lowcost[i] = graph[0][i];
mst[i] = 0;
}

for(i = 1; i < n; i++){
min = MAX;
minid = 0;
//找出代价最小的那个点
for(j = 1; j < n; j++){
if (lowcost[j] < min && lowcost[j] != 0) {
min = lowcost[j];
minid = j;
}
}
System.out.println(c[mst[minid]] + "to" + c[minid] + " value:" + min);

sum += min;
lowcost[minid] = 0;
//将上一次计算后得到点的邻接边的权值赋给 lowcost[]
for (j = 1; j < n; j++) {
if (graph[minid][j] < lowcost[j]) {
lowcost[j] = graph[minid][j];
mst[j] = minid;
}
}
}

System.out.println("sum:" + sum);

}
}

  Prim算法结果:

  kruskal算法的实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
package greedyAlgorithm;

/**
* kruskal算法的java实现
* @author jrhu05
*
*/
public class Kruskal {
static int MAX = Integer.MAX_VALUE;
public static void main(String[] args) {
int[][] map = new int[][]{
{MAX,6,1,5,MAX,MAX},
{6,MAX,5,MAX,3,MAX},
{1,5,MAX,5,6,4},
{5,MAX,5,MAX,MAX,2},
{MAX,3,6,MAX,MAX,6},
{MAX,MAX,4,2,6,MAX},
};
kruskal(map, map.length);
}

private static void kruskal(int[][] map, int length) {
//顶点个数
int num = length;
//存放对应顶点所在连通图标识
int[] group = new int[num];

int sum = 0, n1 = 0, n2 = 0;
boolean finished = false;
int groupNum = 1;

while(!finished) {
int min = Integer.MAX_VALUE;
//找出所有边中最小值
for(int i = 0; i < num; i++) {
for(int j = i+1; j < num; j++) {
if(map[i][j] > 0 && map[i][j] < min){
//如果group相同,则表示处理过,不相同或都为0都表示没处理过
if (group[i] != group[j] || (group[i] == 0 && group[j] == 0)) {
min = map[i][j];
n1 = i;
n2 = j;
}
}
}
}

if(min == Integer.MAX_VALUE){
continue;
}

System.out.println(n1 + " ---> " + n2 + " " + min);
sum += min;

//找到了最小值,设置连通标记
if(group[n1] == 0 && group[n2] == 0){
group[n1] = groupNum;
group[n2] = groupNum;
groupNum++;
}
else if(group[n1] > 0 && group[n2] > 0) {
int tmp = group[n2];
for(int m = 0; m < group.length; m++){
if(group[m] == tmp){
group[m] = group[n1];
}
}
}
else{
if(group[n1] == 0){
group[n1] = group[n2];
}
else{
group[n2] = group[n1];
}
}

for(int i = 0; i < group.length; i++) {
if(group[i] != group[0]){
finished = false;
break;
}
else{
finished = true;
}
}

if(finished) {
break;
}
}

System.out.println(" sum:"+sum);

}

}

  其结果如下:

  哈夫曼编码的生成算法留待下次再补。

  补上哈夫曼编码的实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
package greedyAlgorithm;

/**
* huffman编码的java实现
* @author jrhu05
*
*/
public class Huffman {
//最大权值
static final int MAXVALUE=1000;
int nodeNum ; //叶子结点个数

public static void main(String[] args) {

int[] weight = {20,19,18,17,15,10,1};
int n=weight.length ;
Huffman haffTree = new Huffman(n);
HuffNode[] nodes = new HuffNode[2*n-1];
Code[] codes = new Code[n];
//构造哈夫曼树
haffTree.huffman(weight, nodes);
//生成哈夫曼编码
haffTree.huffmanCode(nodes, codes);

//打印哈夫曼编码
for(int i=0;i<n;i++)
{
System.out.print("Weight="+codes[i].weight+" Code=");
for(int j=codes[i].start+1;j<n;j++)
{
System.out.print(codes[i].bit[j]);
}
System.out.println();
}

}


public Huffman(int n)
{
this.nodeNum = n;
}

//构造哈夫曼树算法
public void huffman(int[] weight,HuffNode[] nodes)//权值数组,所有节点数组
{
int n = this.nodeNum;
//m1,m2,表示最小的两个权值,x1,x2,表示最小两个权值对应的编号,m1表示最小,m2表示次小
int m1,m2,x1,x2;

//初始化所有的结点,对应有n个叶子结点的哈夫曼树,有2n-1个结点。
for(int i=0;i < 2*n-1;i++)
{
HuffNode temp = new HuffNode();
//初始化n个叶子结点,就是输入的节点。0、1、2、3是叶子节点也是输入的节点
if(i < n)
{
temp.weight = weight[i];
}
else
{
temp.weight = 0;
}
temp.parent = 0;
temp.flag = 0;
temp.leftChild = -1;
temp.rightChild = -1;
nodes[i] = temp;
}

for(int i=0;i<n-1;i++){//初始化n-1个非叶子结点,n-1表示要循环n-1次求的n-1个数。
m1 = m2 = MAXVALUE;
x1 = x2 =0;
for(int j=0;j< n+i;j++)//求得这n-1个数时,每次都是从0到n+i-1,并且flag=0的,flag=1表示已经加入到二叉树。
{ //以下2步是找出权值最小的2个
if(nodes[j].weight<m1 && nodes[j].flag==0)//if成立了else if就不进去了。
{
//m1,x1初始值为第一个元素,后面如果比m1要小,则m1指向更小的,原来m1指向的现在由m2指向,
//如果后面比m1大比m2小,则m2指向这个比m1大比m2小的,
//也就是说m1指向最小的,m2指向第2小的。
m2 = m1;
x2 = x1;
m1 = nodes[j].weight;
x1 = j;
}
else if(nodes[j].weight<m2 && nodes[j].flag ==0)
{
m2 = nodes[j].weight;
x2 = j;
}
}
//将权值最小的2个组合成一个2插树
nodes[x1].parent = n+i;
nodes[x2].parent = n+i;
nodes[x1].flag = 1;
nodes[x2].flag = 1;
nodes[n+i].weight = nodes[x1].weight + nodes[x2].weight;
nodes[n+i].leftChild = x1;
nodes[n+i].rightChild = x2;
}

}

//哈弗曼编码算法
public void huffmanCode(HuffNode[] nodes,Code[] haffCode)
{
int n = this.nodeNum;
Code code = new Code(n);
int child,parent;

for(int i=0;i<n; i++)//给前面n个输入的节点进行编码
{
code.start = n-1;
code.weight = nodes[i].weight;
child = i;
parent = nodes[child].parent;
//从叶子节点向上走来生成编码,画图即可。
while(parent!=0)
{
if(nodes[parent].leftChild == child)
{
code.bit[code.start] = 0;
}
else
{
code.bit[code.start] = 1;
}

code.start--;
child = parent;
parent = nodes[child].parent;
}

Code temp = new Code(n);
for(int j=code.start+1;j < n;j++)
{
temp.bit[j] = code.bit[j];
}
temp.weight = code.weight;
temp.start = code.start;
haffCode[i] = temp;
}
}
}
//哈夫曼树的结点类
class HuffNode {

int weight; //权值
int parent ;//他的双亲
int flag ;//标志,是否为叶子节点
int leftChild; //他的左孩子
int rightChild;//他的右孩子

HuffNode()
{

}
}

//哈夫曼编码类
class Code {

int[] bit; //编码的数组
int start; //编码的开始下标
int weight; //权值
Code(int n){
bit = new int[n];
start = n-1;
}
}


如果觉得文章很有趣或对你带来了帮助,欢迎请我喝杯咖啡哦~

文章目录