组合优化学习笔记<之>从贪心算法到子集系统再到拟阵

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

贪心算法是用的比较多的一种优化算法，因为它过程简洁优美，而且结果有效。有些优化问题如最大权森林（MWF）是可以用贪心问题求解的，由于最小支撑树（MST）问题与MWF是等价的，所以MST也是可以用贪心算法求解。当然，贪心算法不是万能的（对于某些问题贪心算法并不能求得最优解，如旅行商问题（TSP）、最大匹配问题），但并不妨碍人们对它的喜爱。

贪心算法(greedy algorithm)伪代码：

input:一组带权的元素集合E; 一组条件集合C
output:找出集合A⊆E，使得A是满足C的所有E的子集中权值最大的子集
//“集合的权值”定义为：集合中所有元素的权值之和
//“满足C”定义为:满足C中的所有条件。这里设定空集是满足C的。
begin
A = {};
while E!={}
找出E中权值最大的元素，假设该元素是e;
E=E-{e};
if A+e 满足C
A=A∪{e};
end
//注：这里部分采用C语言的运算符定义。
// 即"="表示赋值; "!="表示不等号

从以上描述中可以看出来，过程很简单，可以说是简单暴力的。所以，我们很容易会产生疑问：这样的算法最后得出的解一定是全局最优解吗？

在回答之前，我们要搞清楚的是：当前要解决的问题实例对可行解的定义是什么？换句话说，我们要找的“最优解”是从哪个可行解集中找出来的。即，去掉“最优的”限制条件后，还有哪些条件。那么满足这些条件的所有集合就是可行解集，下一步就是从这个可行解集中找出一个最优的。到这里工作重点已然转化为找一个合适的优化算法。

其次，这个优化问题可以用贪心算法求出最优解吗？答案显然是不一定的。比如，我们要考虑：

（1）若可行解集无限且其权值不收敛，那必然是不能解的。因为这个问题实例本身是没有最优解的。

（2）可行解有限，或者无限但权值收敛的情况下，在以什么样的条件下定义出的可行解集中用贪心算法可以最后得到最优解呢？

先引入一个概念：子集系统

已知集合E={e₁,e₂,...,e_n}; I⊆P(E)且I以包含关系封闭。那么称二元组S=(E，I)为子集系统。I中每个成员称为独立集。

//注：P(E)表示E的幂集。

如A={1,2,3,4,5,6}，B={{2},{2,4},{4,6},{2,4,6}}，则(A,B)是子集系统。

再引入一个概念：拟阵

对于某个子集系统M=(E,I)，若能用贪心算法找出I中权值最大的独立集，那么这个子集系统就是拟阵。

看起来似乎问题又绕回去了，没关系，下面3个命题的等价性可以解惑:

命题1：M是拟阵。

命题2：若E_p∈I，E_p+1∈I，且|E_p|=p,|E_p+1|=p+1，则∃e∈E_p+1-E_p,使得 E_p∪{e} ∈ I。

命题3：若A⊆E，且E_p，E_p+1是A的两个极大独立集，则|E_p|=|E_p+1|。

总结：贪心算法有这么多的条件限制，为什么还有这么被爱呢？开头说过了，因为它简洁优美。最关键的是，对于很多甚至说很大一部分问题，我们往往未必需要找出的它的最优解，近似最优已然足够。

参考资料：《组合最优化算法和复杂性》

组合优化学习笔记<之>从贪心算法到子集系统再到拟阵的更多相关文章

机器学习实战（Machine Learning in Action）学习笔记————08&period;使用FPgrowth算法来高效发现频繁项集
机器学习实战(Machine Learning in Action)学习笔记————08.使用FPgrowth算法来高效发现频繁项集关键字:FPgrowth.频繁项集.条件FP树.非监督学习作者:米 ...
机器学习实战（Machine Learning in Action）学习笔记————07&period;使用Apriori算法进行关联分析
机器学习实战(Machine Learning in Action)学习笔记————07.使用Apriori算法进行关联分析关键字:Apriori.关联规则挖掘.频繁项集作者:米仓山下时间:2018 ...
机器学习实战（Machine Learning in Action）学习笔记————02&period;k-邻近算法（KNN）
机器学习实战(Machine Learning in Action)学习笔记————02.k-邻近算法(KNN) 关键字:邻近算法(kNN: k Nearest Neighbors).python.源 ...
[ML学习笔记] 朴素贝叶斯算法（Naive Bayesian)
[ML学习笔记] 朴素贝叶斯算法(Naive Bayesian) 贝叶斯公式 \[P(A\mid B) = \frac{P(B\mid A)P(A)}{P(B)}\] 我们把P(A)称为"先 ...
Effective STL 学习笔记 31：排序算法
Effective STL 学习笔记 31:排序算法 */--> div.org-src-container { font-size: 85%; font-family: monospace; ...
HMM模型学习笔记（前向算法实例）
HMM算法想必大家已经听说了好多次了,完全看公式一头雾水.但是HMM的基本理论其实很简单.因为HMM是马尔科夫链中的一种,只是它的状态不能直接被观察到,但是可以通过观察向量间接的反映出来,即每一个观察 ...
KVM性能优化学习笔记
本学习笔记系列都是采用CentOS6.x操作系统,KVM虚拟机的管理也是采用virsh方式,网上的很多的文章都基于ubuntu高版本内核下,KVM的一些新的特性支持更好,本文只是记录了CentOS6. ...
深挖计算机基础：Linux性能优化学习笔记
参考极客时间专栏<Linux性能优化实战>学习笔记一.CPU性能:13讲 Linux性能优化实战学习笔记:第二讲 Linux性能优化实战学习笔记:第三讲 Linux性能优化实战学习笔记: ...
Pandas 性能优化学习笔记
摘要本文介绍了使用 Pandas 进行数据挖掘时常用的加速技巧. 实验环境 import numpy as np import pandas as pd print(np.__version__) ...

随机推荐

python之最强王者（4）——字符串
1.Python 中文编码前面章节中我们已经学会了如何用 Python 输出 "Hello, World!",英文没有问题,但是如果你输出中文字符"你好,世界&quot ...
Springmvc常用注解
1. @RequestMapping注解的作用位置 @RequestMapping可以作用在类名上,也可以作用在方法上. 如果都有, 产生作用的路径是类名上的路径+方法上的路径. 比如Employee ...
亚马逊开放机器学习系统源代码：挑战谷歌TensorFlow
北京时间5月17日上午消息,亚马逊在开源技术领域迈出了更大的步伐,宣布开放该公司的机器学习软件DSSTNE的源代码.这个最新项目将与谷歌的TensorFlow竞争,后者已于去年开源.亚马逊表示,在缺乏 ...
python数字图像处理（11）：图像自动阈值分割
图像阈值分割是一种广泛应用的分割技术,利用图像中要提取的目标区域与其背景在灰度特性上的差异,把图像看作具有不同灰度级的两类区域(目标区域和背景区域)的组合,选取一个比较合理的阈值,以确定图像中每个像素 ...
javascript-for-loop-example--reference
We hear a lot about loops, especially for loops. So what, in fact, are they? They’re just pieces of ...
[TYVJ] P1238 路径
路径描述 Description 图是由一组顶点和一组边组成的.一条边连接两个顶点.例如,图1表示了一个有4个顶点V.5条边的图.图中,每条边e是有方向的,方向从起点到终点,并且每条边都有价值.用整 ...
添加Main-Class到manifest中
Maven默认打包生成的jar是不能够直接运行的,因为带有main方法的类信息不会添加到manifest中(打开jar文件中的META-INF/MANIFEST.MF文件,将无法看到Main-Clas ...
Could not establish trust relationship for the SSL/TLS secure channel 问题解决方法
最近在写一个跟第三方对接的数据同步服务,在本地都没有问题,今天放到生产环境测试报错: System.Net.WebException: The underlying connection was cl ...
docker简单介绍----存储
docker容器中使用Volumes来实现数据的持久性,因为容器的删除会丢失数据,而关闭或者重启容器不会丢失数据 docker run -v即可使用Volumes 1.docker-managed ...
Django之ORM