贪婪算法原理介绍与实例解析

一 贪婪算法定义

每次都选择最优解&＃xff0c;期望最后得到最优全局解

二 适用场景

1 最优子结构
2 子问题不是重叠的

三 拟阵–贪婪算法的一个应用场景

3.1 拟阵的定义&＃xff1a;

如果一个序列对&＃xff1a;M&＃61; 满足&＃xff1a;
1 S 是有穷集合
2 N 是S的所有独立子集。 并且对于任意B∈N,且有A⊆B ,那么A∈N 这种性质叫做遗传性
3 如果A∈N&＃xff0c;B∈N且 |A| < |B| ,则对于任意e∈B-A,有A⋃e∈N. 称M满足交换性质。
则该序列为拟阵

3.2 拟阵的应用

很多可以使用贪心算法的的问题&＃xff0c;都可以转化为在加权矩阵中找最大权值的独立子集问题。&＃xff08;可以简单的理解为&＃xff0c;很多问题都能转化为最小生成树问题&＃xff1f;&＃xff09;