第六章 贪心算法
- 顾名思义，贪心算法总是作出当前看来最好的选择，也就是说贪心算法并不从整体最优考虑，是某种意义上的局部最优解。许多情况下，局部最优的组合就是整体最优解。
小数背包问题GREEDYKNAPSACK
- 相较于0/1背包问题，小数背包是指在选择把物品
装入背包时，可以选择物品的一部分（价值与体积成正比），而不是全部装入背包。
- 由于是按比率放入背包，我们可以贪心地先放性价比最高的，再放其次的······直到背包被装满，这样得到的背包价值一定最大。
GREEDYKNAPSACK
输入：物品集合U={u1, u2,..., un}，体积分别为s1, s2,..., sn，价值分别为v1, v2,..., vn，容量为C的背包。
输出：在约束条件
下最大，
。
comment: 物品已经按性价比降序排列好
x <- 0 #x(i)指示着第i个物品被选择多少，1表示全部选择
c <- C
for i <- 1 to n
if w(i) <= c then
x(i) <- 1
c <- c - w(i)
else exit
if i <= n
then x(i) <- c/w(i)
return x
霍夫曼编码Huffman Coding
在计算机数据处理中，霍夫曼编码使用变长编码表对源符号（如文件中的一个字母）进行编码，其中变长编码表是通过一种评估来源符号出现机率的方法得到的，出现机率高的字母使用较短的编码，反之出现机率低的则使用较长的编码，这便使编码之后的字符串的平均长度、期望值降低，从而达到无损压缩数据的目的。
-
霍夫曼编码的具体操作
- 将信号源符号按照出现概率从大到小排序（此时为
棵树的森林，特殊地是每棵树只有一个节点）；
- 将最小的两个符号概率
相加得到新概率
，并由新概率
为根，
- 易知，最终的根节点概率为
，依照“左
右
- 对于树上的每个字符节点，其霍夫曼编码就是根节点到该节点的唯一路径编号组合；
例如，经统计信号源符号满足：
，请构造霍夫曼树并求每个字符的编码。
- 每次合并后，将由新的根节点取代原来的树。例如第二步，
合并为
后，接下来是取
的最小两个
。
字符 编码 - 将信号源符号按照出现概率从大到小排序（此时为
HUFFMAN
输入：n个字符的集合C={c1, c2,..., cn}和它们的频度{f(c1), f(c2),..., f(cn)}。
输出：C的Huffman树(V, T)。
根据频度将所有字符插入最小堆H
V <- C; T = {}
for j <- 1 to n-1
c1 <- DELETEMIN(H)
c2 <- DELETEMIN(H)
f(v) <- f(c1) + f(c2) #新节点v的频度
INSERT(H, v) #将v替代c1，c2加入最小堆
V = V并{v}
T = T并{(v, c1), (v,c2)}
end while
生成树Minimum Spanning Tree,MST
- 定义：设
是无向连通带权图（也称为一个网络）。
中每条边
的权值为
。如果
的子图
是一棵包含
Prim算法
Prim算法从建立两个集合开始：
。在每一步中，选取
集合到
集合的权重最小的边
（这条边当然不会与
加入
-
例如如下，从顶点
开始：
中选择
，将
加入集合
中选择
，将
加入集合
-
中选择
加入集合
······
PRIM
输入：含权连通无向图G(V,E)，V={1, 2,..., n}。
输出：由G生成的最小耗费生成树T组成的边的集合。
comment: 图G用二维数组A表示。
T <- {}; X <- {1}; Y <- V-{1} #T的元素为(x,y)指示一条边
while Y not empty:
min = infty
#两层for循环找出X->Y的最短边
for each i in X:
for each j in Y:
if A[i][j] < min then
min <- A[i][j]
x <- i
y <- j
end if
end for
end for
X <- X并{y}
Y <- Y减{y}
T <- T并{(x,y)}
end while
return T
- 易知，
循环执行
次迭代查找最小边花费
的时间，
。
Kruskal算法
Prim算法可以从任意一个顶点开始执行可能产生多种最小生成树，与Prim算法十分类似，Kruskal算法也是将顶点分为两个集合，按照一定规则进行搬运。
-
思路：
- 将图
- 每次从边集合
中取出一条边，若不与生成树集合
内的点连通则加入
- 将图
-
例子如下：
边
，加入
-
边
，加入
······
边
，加入会使得
连通，舍弃；
-
边
，不与
······
KRUSKAL
输入：包含n个顶点的含权连通无向图G=(V,E)。
输出：由G生成的最小耗费生成树T组成的边的集合。
按非降序权重将E中的边重新排序
for each v in V
MAKESET({v})
end for
T = {}
while |T| < n - 1
令(x, y)为E中的下一条边
if FIND(x) != FIND(y) then
将(x, y)加入T
UNION(x, y)
end if
end while
return T
单源最短路径
- 设
，称为源。需要确定源
的距离定义为从
- 下面介绍解决该问题的一个算法：Dijkstra算法。该算法与Floyd算法的执行过程十分类似，不断试探中间顶点对最短路径的影响。
Dijkstra算法
- 初始时，将顶点分为两个集合
为从源到
- 在每一次迭代中，我们选择
最小，将该顶点加入
DIJKSTRA
输入：含权有向图G=(V,E)，V={1, 2,..., n}。
输出：G中顶点1到其他顶点的距离。
X = {1}; Y <- V - {1}; l[1] <- 0
for y <- 2 to n
if y相邻于1 then l[y] <- length[1,y]
else l[y] <- infty
end if
end for
for j <- 1 to n-1
取y属于Y，且l[y]最小
X <- X并{y}
Y <- Y减{y}
for each w in X
if l[y] + length[y,w] < l[w] then
l[w] <- l[y] + length[y,w]
end for
end for
Bellmen-Floyd算法
松弛操作
：假设已知一条从
的路径长度为
，而通过节点
的路径
的路径更短，则更新
-
过程：
- 初始时，设置源点
- 遍历每一条边，并尝试将该边加入路径，进行松弛操作。
- 最后遍历一次边，若节点
- 初始时，设置源点
BELLMAN-FLOYD
输入：含权有向图G=(V,E)，V={1, 2,..., n}。
输出：G中顶点1到其他顶点的距离。
d[1] <- 0
for each v in V-{1}
d[v] <- infty
for i <- 1 to |V|-1
for each edge(u,v) in E #使用邻接表更容易实现该算法
if d[v] > d[u] + w(u,v) then
d[v] <- d[u] + w(u,v)
end if
end for
end for
for each edge(u,v) in E
if d[v] > d[u] + w(u,v)
then report a negative-weight cycle exists.
return d
- 时间复杂度为
。
