原理
步骤
-
建立数学模型来描述问题,并建立一个备选答案区
-
把求解的问题分成若干个子问题,
-
使用一个选择函数对每个子问题求解最优解,并判断是否可用于整体问题
-
把所有子问题的最优解合成一个整的解
适用情况
贪婪算法适用于一些数学问题等,大部分适用的问题都有两个特点:
Greedy choice property (贪婪选择的属性)
Optimal substructure (最优子结构)
如以下几种类型的问题
Matroids (拟阵)
(子模块函数)
一个函数 定义了当集合 的所有子集合 都满足 的情况即为子模块.
假设有人想要找到一个集合 使得函数 最大.贪婪算法将会通过逐个添加在每一步中使得 增加最多的元素,产生一个结果至少是 ??todo. 所以,贪婪算法至少得出最优解的 倍的解.
其他一些相对可以使用的问题
- The
- [
这些问题也可以使用贪婪算法,但不是最好的解法,他们在最差的情况下,可能会得到很差的结果.
失败的情况
比如下图,贪婪算法只考虑到下一步的最优解,但是却没有考虑到之后的解决方案,导致实际上得出的不是一个最优解.
Greedy-search-path-example.gifApplication
Reference
About Me
微信公众号
[图片上传失败...(image-ee4c03-1560057222368)]