Joyce' Blog
0%

算法复习笔记（二）

发表于 更新于

图

定义：“路径”，“简单”，“连通”，“圈(k>2)”，“树(连通且无圈)”

图的连通性与图的遍历

广度优先(Breadth-First Search) —队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
BFS(s): 
置Discovered[s]=true, 其他v, 置Discovered[v]=false 
初始化L[0], 单个元素s构成 
置层计数器i=0 
置BFS树T=空集
While L[i]非空
	初始化一个空表L[i+1]
	For 每个结点L[i]中结点u 
	考虑每条关联到u的边(u,v) 
    If Discovered[v]=false then 
    	置Discoverd[v]=true 
        把边(u,v)加到树T上 
        把v加到表L[i+1]
    Endif 
  Endfor 
 层计数器加1 
Endwhile

如果图是邻接表给出，BFS将以O(m+n)时间运行

DFS—栈

1
2
3
4
5
6
7
8
9
10
11
DFS(s) 
初始化S为具有一个元素s的栈 
While S 非空
	从S中取出一个节点u 
	If Explored[u]=false then 
		置Explored[u]=true 
    	For每条与u关联的边(u,v) 
    		把v加到栈S 
    	Endfor 
    EndIf 
EndWhile

对无向图中任两个结点s与t,它 们的连通分支或者相等，或者不相交。
对有向图中的任何两个结点s与 t,它们的强连通分支或者相等，或者不相交。

强连通：图中每对结点相互可达

二分性测试

如果一个图是二部图，那么它不可能包含一个奇圈。没有边与同一层的两个结点相交。

BFS—存在 O(m + n) 的有效算法判别图G是 否强连通。

DAG(DirectedAcyclicGraphs)有向无圈图~拓扑排序

在O(m + n) 时间内找到一个拓扑排序—考虑边逐次递减的代价O(m); 追踪被删除 的结点代价O(n).（邻接表+零入度节点的栈）

贪心算法

证明贪心算法对一个问题能够提供一个优解：贪心算法领先、交换论证

区间调度

失败的尝试：开始时间、区间的宽度、最少“冲突”。

贪心算法：把任务(需求)按照结束时间递增排序。依次选取与前面已选定任务相容的新任务。O(nlogn)

用贪心算法领先的思路，说明以“最小结束时间”为贪心策略的最优性（归纳法）。

推广：在线算法、加权的区间调度

区间划分

在任何区间划分的实例中，资源数必须至少是区间集合的深度。一个区间集合的深度是通过时间线上任何一点的最大区间数。

贪心算法：需求按照开始时间排序，把需求安排到不冲突的资源中。对于每一个教室k, 记录下后一个需求的结束时间；把教室放在一个优先队列中(按照结束时间 先后)。 O(nlogn)

最小延迟调度

失败的尝试：任务长度、松弛时间（最晚开始时间）

贪心算法：按照结束时间增长的次序排序(最早截止时间优先)，用交换论证的方法证明最优性。

推广：增加释放时间（最早开始时间）

最优超高速缓存

“最远将来规则”（Farthest-in-future） When di需要被放入超高速缓存，收回在最远的将来被需要的那个项。

推广：最近最少使用原则（LRU)。把时间方向倒过来：过去的久而不是将来的远，恰好是Belady算法，因为实际必须在不知道将来需求的情况下匆忙做出收回的决定。

图的最短路径

Dijkstra算法

1
2
3
4
5
6
7
8
9
Dijkstra算法(G,l) 
设S是被探查的结点集合 
	对每个S中的u,存储一个d(u); 
初始S={s}且d(s)=0 
While S!=V 
	选择一个结点不在S中的结点v,使得从S到v至少有一条边连接并且	      		
	d'(v)=min_{e=(u,v), u in S}d(u)+le 最小 
    将v加入S并且定义d(v)=d'(v) 
Endwhile

使用优先队列与邻接链表使整个时间复杂度优化到 O( (M+N)logN )

  • d[]是最小堆，所以每次取出最小值只需$O(1)$的时间，并花费$O(logn)$的时间重新调整成最小堆；
  • 需要n-1次操作才可以找出剩下的n-1个点，在这期间，需要访问m次边，每次访问都可能造成d[]的改变。

最小生成树

Kruskal算法

将边按照费用递增次序排列，只要不构成圈，把边e插入树中。采用union-find数据结构，生成一个小生成树T，保持每一个连通分支的集合。算法代价：O(mlog n).

1
2
3
4
5
6
7
8
9
10
//在一个具有n 个顶点的网络中找到一棵最小生成树
令T为所选边的集合，初始化T=Φ
令E为网络中边的集合
while (E≠Φ) && (|T|≠n-1) {
令(u,v)为E中代价最小的边
E=E-{ (u,v) } / /从E中删除边
if ((u,v)加入T中不会产生环路) 将(u,v)加入T
}
i f (|T| == n-1) T是最小耗费生成树
else 网络不是连通的，不能找到生成树

反向删除算法

依照费用递减的次序开始删除边，只要不破坏当前图的连通性。

Prim算法

初始S={s}，然后贪心增长树T. 每步选择一端在T中， 费用小的边与T连接。复杂度估计：用矩阵，O(n^2)； 采用优先队列 （堆），O(mlogn)

1
2
3
4
5
6
7
8
9
10
11
12
//假设网络中至少具有一个顶点
设T为所选择的边的集合，初始化T=Φ
设TV为已在树中的顶点的集合，置TV={1}
令E为网络中边的集合
while (E<>Φ) && (|T|<>n-1) {
	令(u,v)为最小代价边，其中u∈TV,v∈TV
	if (没有这种边) break
	E=E-{(u,v)}//从E中删除此边
	在T中加入边(u,v)
}
if (|T|==n-1) T是一棵最小生成树
else 网络是不连通的，没有最小生成树

一个圈和一个割有偶数条相交边。

推广

存在相同费用的边、关心点到点的距离 、每条边运输不超过确定的交通量、删除一条边后仍保持畅通

聚类

运行Kruskal算法，但是就在它加最后的k-1条边之前停止。等价于取整棵最小生成树T,然后删除k-1 条最贵的边。

Huffman码与数据压缩

证明：归纳步骤中用反证法。假设贪心算法产生的树T不是最优的，存在树Z, 使得ABL(Z)<ABL(T),根据前面的命题，存在这样一棵树Z,其中y*与z*(频率最低的两个字母)是兄弟。类似的，我们可以得到Z’, 满足：ABL(Z’)=ABL(Z) - fw. 于是就得到：ABL(Z’)<ABL(T’)，与作为S’前缀码的T’最优性相矛盾。

基本是到此结束的，但是上机考试的经历实在不忍回首，真是对不起葡萄。要在这里好好学下huffman的代码了。

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
// huffman.h
#pragma once
#include<iostream>
#include<list>
#include <algorithm>
#include<string>
using namespace std;
int T = 0;
class binaryTree
{
public:
	binaryTree* right;
	binaryTree* left;
	int weight;//权重
	char key;//字母
	binaryTree(int theWeight=0,char theKey=0,binaryTree* theLeft=NULL, binaryTree* theRight = NULL)
	{ weight = theWeight; right = theRight; left = theLeft; key = theKey; }
	void makeTree(binaryTree, binaryTree);
};
void binaryTree::makeTree(binaryTree theLeft, binaryTree theRight)
{
	binaryTree* ltree = new binaryTree(theLeft.weight, theLeft.key, theLeft.right, theLeft.left);
	binaryTree* rtree = new binaryTree(theRight.weight, theRight.key, theRight.right, theRight.left);
	left = ltree;
	right = rtree;
}
struct hpair
{//权重-字母-编码
	int weight;
	char key;
	string huffString = "";
};
hpair* p = NULL;//申明自定义的类的对象时，要写在类定义之后！！
bool compare(binaryTree* a,binaryTree* b)
{
	return a->weight<b->weight; //升序排列
}

binaryTree* myTree = NULL;
void huffmanTree(hpair* code, int n)
{
	list<binaryTree*> tlist;
	binaryTree *hNode = new binaryTree[n];
	//创建n个叶节点
	for (int i = 0; i < n; i++)
	{
		hNode[i] = binaryTree(code[i].weight, code[i].key, NULL, NULL);
		hNode[i].key = code[i].key;
		tlist.push_back(&hNode[i]);
	}
	//每次取权最小的两个节点，构成新的节点
	while (tlist.size()>1)
	{
		tlist.sort(compare);
		binaryTree *theR,*theL;
		theR = tlist.front();
		tlist.pop_front();
		theL = tlist.front();
		tlist.pop_front();
		binaryTree* tree =new binaryTree(theR->weight + theL->weight, ' ', theL, theR);
		tlist.push_back(tree);
	}
	binaryTree* tmp = tlist.front();
	myTree = new binaryTree(tmp->weight, tmp->key, tmp->left, tmp->right);
}
void huffCode(binaryTree* tree, string s)
{
	if ((tree->left) == NULL || (tree->right) == NULL)
	{//递归得到叶节点
		cout << tree->key << "-----" << s << endl;
		for (int i = 0; i < T; i++)
		{
			if (p[i].key == tree->key)
				p[i].huffString = s;
		}
	}
	else
	{//向左附加0，向右附加1，递归
		huffCode(tree->left, s + "0");
		huffCode(tree->right, s + "1");
	}
}
hpair* createPair(string s)
{//根据传入的字符串确定出现的符号和频率
	int num[26];
	for (int i = 0; i < 26; i++)
		num[i] = 0;
	int len = s.length();
	for (int i = 0;i < len; i++)	
		num[s[i] - 'a']++;//出现次数
	int total = 0;//字母种数
	for(int i=0;i<26;i++)
		if (num[i])
		{
			total++;
		}
	T = total;
	int j = 0;
	p = new hpair[total];
	for (int i = 0; i < 26; i++)
	{
		if (num[i])
		{
			p[j].key = 'a' + i;
			p[j++].weight = num[i];
		}
	}
	return p;
}
string encode(string a)
{//用已有的哈夫曼树得出的字母编码，将字符串转为01串
	string ret = "";
	int len = a.length();
	for (int i = 0; i < len; i++)
	{
		for (int j = 0; j < T; j++)
		{
			if (p[j].key == a[i])
				ret += p[j].huffString;
		}
	}
	return ret;
}

string trans(string num)
{//将01串转为原文
	string tr = "";
	char temp;
	binaryTree* tt;
	int len = num.length();
	for (int i = 0; i < len; )
	{
		tt = myTree;
		while (tt->left != NULL)
		{//读到0向左读到1向右
			temp = num[i++];
			if (temp == '0')
				tt = tt->left;
			else
				tt = tt->right;
		}
		//到达叶节点，附加字母
		tr += tt->key;
	}
	return tr;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// main.cpp
#include"huffman.h"
#include<vector>
#include<string>
#include<iostream>
using namespace std;
void main()
{
	string s = "iisssksssskkttteonoks";
	cout << s << endl;
	hpair* hp = NULL;
	hp= createPair(s);
	huffmanTree(hp, T);
	huffCode(myTree, "");
	cout << '\n' << "--------------After encode--------------" << endl;
	string ret=encode(s);
	cout << ret << endl;
	cout << '\n' << "--------------Translation--------------" << endl;
	string tr = trans(ret);
	cout << tr << endl;
	system("pause");
}