贪心法

引言

优化问题:贪心法常用于解优化问题

应用:

  1. 货箱装船问题
  2. 背包问题
  3. 拓扑排序问题
  4. 哈夫曼编码问题
  5. 最短路径问题
  6. 最小代价生成树
  7. 偶图覆盖问题

优化解即指始目标函数极大化(或极小化)的可行解,对应的目标函数值成为优化值。

很多优化问题时NP-难度问题,迄今找不到他们的多项式算法。所以计算上可行的方法就是求其近似解。贪心法是求近似算法的主要途径。

贪心法:一种多步求解的方法

每步按一种局部优化的策略选择解(元组)的一个分量;

算法以第n步结束时构造出的对象(元组)作为问题的解;

这种局部优化的策略又称为“贪心标准”。

贪心法主要特点

  1. 不回溯:选定一个分量后,不重试其他可能。
  2. 使用局部优化策略的主要原因是减小计算开销。但局部优化策略不保证得到精确优化解,可能得到的是近似解。特别是对NP-难度问题。
  3. 不同的“贪心”策略得到不同的算法。
  4. 常常采纳使目标函数有最大增量的策略为贪心策略;增量是局部性概念。

遗传算法,神经网络等等都是具有这类贪心性质的启发式算法。

贪心算法性能

贪心算法并不总能求得问题的整体最优解。但对于活动安排问题,机器调度问题,上述贪心算法却总能求得整体最优解。

K-优化算法

K-优化算法是上述密度贪心算法的改进,改进后误差可控制在1/(k+1)*100%之内

算法得时间复杂度随k的增大而增加:

  • 需要测试的子集数目为O(pow(n,k));
  • 每一个子集做贪心法需时间O(n);
  • 因此当k>0时总的时间开销为O(pow(n,k+1));

内容:

  • 先对物品按密度从大到小排序;
  • 先将一些物品装入背包,然后对其余物品使用贪心法;
  • 预先装入的物品数不超过k;
  • 对所有物品数不超过k的物品子集执行上述过程,并从中找到有最大效益值得解作为k-优化算法得解。

哈夫曼编码问题

前缀码:对每一个字符规定一个0,1串作为其代码,并要求任一字符的代码都不是其他字符代码的前缀,这种编码成为前缀码。

使平均码长达到最小的前缀码编码方案成为未定编码字符集C的最优前缀码。

哈夫曼提出构造最优前缀码的贪心算法,由此产生的编码方案成为哈夫曼编码。

具体算法:

  1. 根据n个权值{w1, w2, …, wn}构成n棵二叉树的集合F={T1,T2,… Tn},其中每棵二叉树Ti中只有一个带权值为wi的根节点,其左右子树均为空。
  2. 在F中选取两棵根节点权值最小的树作为左右子树来构造一棵新的二叉树,且置新的二叉树的根节点的权值为其左右子树的根节点权值之和。
  3. 在F中删除这两棵树,同时将新得到的二叉树加入F中。
  4. 重复step2,3,直到F中只含一棵树时为止。称这棵树为最优二叉树或哈夫曼树。

如果约定将每个节点的左分支表示字符‘0’,右分支表示字符‘1’,则可以把从根节点到某叶子节点的路径上分支字符组成的字符串作为该叶子节点的编码。

哈夫曼算法以自底向上的方式构造表示最优前缀码的二叉树T。

算法以|C|个叶节点开始,执行|C|-1次的“合并”运算后产生最终所要求的树T。

关于n个字符的哈夫曼算法的计算时间为O(nlogn)。

拓扑排序

邻接矩阵与邻接表

邻接矩阵

邻接表

拓扑排序定义:根据任务的有向图建立拓扑序列的过程。

贪心策略:从当前尚不在拓扑排序序列的顶点中选择一项顶点w,其所有先行节点v都在已产生的拓扑序列中(或无先行顶点)并将其加入到拓扑序列中。

使用栈的伪代码:

  1. 计算每个顶点的入度

  2. 将入度为0的顶点入栈

  3. While(栈不空){

    ​ 任取一入度为0的顶点放入拓扑序列中;

    ​ 将与其相邻的顶点的入度减1;

    ​ 如有新的入度为0的顶点出现,将其放入栈中;

    }

  4. 如有剩余的顶点则该图有环路

代码:

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
bool Network::Topological(int v[])
{
//计算有向图中顶点的拓扑次序
//如果找到了一个拓扑次序,则返回true,此时,在v[0:n-1]中记录拓扑次序
//如果不存在拓扑次序,则返回false
int n=Vertices();
//计算入度
int *InDegree=new int[n+1];
InitializePos();//图遍历器数组
for(int i=1;i<=n;i++)//初始化
InDegree[i]=0;
for(int i=1;i<=n;i++)//从i出发的边
{
int u=Begin(i);
while(u)
{
InDegree[u]++;
u=NextVertex(i);
}
}
//把入度为0的顶点压入堆栈
LinkedStack<int> S;
for(int i=1;i<=n;i++)
if(!InDegree[i]) S.Add(i);
//产生拓扑次序
i=0;//数组v的游标
while(!S.IsEmpty())//从堆栈中选择下一个顶点
{
int w;
S.Delete(w);
v[i++]=w;
int u=Begin(w);
while(u)//修改入度
{
InDegree[u]--;
if(!InDegree[u]) S.Add[u];
u=NextVertex(w);
}
}
DeactivatePos();
delete [] InDegree;
return (i==n);
}

上述算法的时间复杂度:

Θ(n²):使用邻接矩阵;Θ(n+e):使用邻接表

单源最短路径

任给一有向图G,它的每条边都有一个非负的权值,路径的长度定义为路径上边的权值之和。

单源最短路径问题:给定的源节点s,找出从s到图中所有其他节点(成为目的)的最短路径(优化解)及其长度(优化值)

Dijkstra‘s最短路算法

  • 如果链路权值非负,则最短路的子路径也是最短路,其长度小于原来路径的长度。所以,长度较小的最短路容易找到。
  • 贪心策略:按最短路长度从小到大依次求解。
  • Dijkstra’s最短路算法使用上述贪心策略,是图论算法中应用最为广泛的算法,主要原因是其计算复杂度低且容易实现。

基本步骤:

  1. 维护一个集合S,该集合中源节点到其他节点的最短路已知,初始时该集合为空;
  2. 从V-S结合中找一节点v,满足源节点到该节点距离最小;
  3. 更新v的临界点的到源节点的距离值。

Example:1

Dijkstra‘s最短路算法实例

S:{A,C,E,B,D}

源节点为A,所以S:{A};

在S中的节点中找到于之有关的最短路径,将另一节点放入S中;

即AC=min,所以S:{A,C};

CE=min,所以S:{A,C,E};

CB=min,所以S:{A,C,E,B};

BD=min,所以S:{A,C,E,B,D}

∴S:{A,C,E,B,D}

Example:2

实例

Example of breadth-first search:

广度优先搜索实例

Bellman-Ford算法

介绍:Dijkstra算法无法判断含负权边的图的最短路。如果遇到负权,在没有负权回路(回路的权值和为负,即便有负权的边)存在时,也可以采用Bellman - Ford算法正确求出最短路径。

Bellman-Ford算法能在更普遍的情况下(存在负权边)解决单源点最短路径问题。对于给定的带权(有向或无向)图 G=(V,E), 其源点为s,加权函数 w是 边集 E 的映射。对图G运行Bellman - Ford算法的结果是一个布尔值,表明图中是否存在着一个从源点s可达的负权回路。若不存在这样的回路,算法将给出从源点s到 图G的任意顶点v的最短路径d[v]。

Floyd算法

时间复杂度:O(n³);空间复杂度:O(n²)(矩阵)

最小生成树

  • 具有n个顶点的连通无向图G,图的每条边e有一非负权值c(e),也称为成本,求有最小成本的生成树。
  • 每个生成树刚好具有n-1条边,所以问题是用某种方法选择n-1条边使它们形成G的最小生成树。
  • Kruskal’s算法;Prim‘s算法。

Kruskal’s算法

贪心策略:每次选择权值c(e)最小且与以前选择的边不构成回路的边。

上述策略要求按权值从小到大对边排序。

算法可在O(n+eloge)找出最小生成树。

算法正确性证明

Prim‘s算法

步骤:

  1. 在图中选出权值最小的边,边的两个顶点放入点集V;
  2. 在图中找到权值最小且与点集V有关的边;
  3. 重复2直至找到最小生成树。

偶图覆盖问题(二分覆盖)

  • 偶图是一个无向图,它的n个顶点分为集合A和集合B,且同一集合中的任意两个顶点无边相连。
  • A的一个子集A’覆盖集合B iff B中每一个顶点至少和A’中一顶点相连。覆盖A‘的大小指A’中的顶点数目。
  • 在偶图中寻找最小覆盖的问题成为偶图覆盖(bipartite-cover)问题。

Example:

偶图覆盖问题实例

  • 上图为有17个顶点的二分图;
  • A={1,2,3,16,17};B={4,5,6,7,8,9,10,11,12,13,14,15};
  • 子集A’={1,16,17}是B的最小覆盖:1覆盖{4,6,7,8,9,13};16覆盖{5,6,8,12,14,15};17覆盖{4,9,10,11}
  • 贪心策略:选择覆盖B中那些尚未被覆盖的顶点数最多的A的系节点。
  • 对上图应用上述贪心法,得到A‘={1,16,17}。
  • 覆盖算法总的算法复杂性为O(Sizeof(A²)+n²)或O(Sizeof(A²)+n+e)。

连续背包问题

一种可行的贪心策略:按价值密度非递减的顺序检查物品,若剩余容量能容下正在考察的物品,将其装入;否则往背包中装入此物品的一部分。

证明这种贪心算法总能产生最优解:

证明这种贪心算法总能产生最优解

9