华人网
标题:
贪心算法知识
[打印本页]
作者:
小宇宙OVO
时间:
2022-8-11 16:48
标题:
贪心算法知识
一个问题即使不能使用某个贪心算法,也可以通过贪心算法给出一个“还说得过去”的解,这也是贪心算法在现实中存在的意义之一。
基本的算法中贪心著名的贪心算法包括: Dijskstr单源图最短路径算法、Prim和Kruskal最小生成树算法、Huffman编码简单压缩算法等。
如果给贪心算法一个抽象地描述,我认为可以这样讲: 假设一些对象的集合S, 每个对象x对应一个收益payoff(x),对于任意S的子集T,我们有一个函数可以判断它是否合法isValid(T) ——它返回布尔值。并且这个函数通常有个性质,空集是合法的;如果 T合法,它的任意子集都合法;如果它非法,它的任意超集都非法。我们的目标是从 S中选取若干个对象,形成一个集合V,使得isValid(V) == true并且payoff(V)尽可能大。其中payoff(V)定义为V中所有对象的收益之和。贪心算法是这么解决这个问题的,从空集合开始,每次选一个payoff最大并且合法的对象x加入到V里面, V = VU{x}。
可见具备上述性质的问题实际上还是比较特殊的,而上述性质通常成为贪心选择性。
可见贪心选择是比较“短视”的,选取最优的一个元素,即使有多个,任选一个。而动态规划算法是从所有能达到当前状态的状态和决策中选取,所以从某种角度上讲,动态规划是枚举——只是聪明点的枚举罢了,它枚举的是所有状态以及该状态下的决策。而贪心只是单一的选择,盲目选择当前最优的决策。
-----------------------------------
©著作权归作者所有:来自51CTO博客作者wx62f49e890a843的原创作品,请联系作者获取转载授权,否则将追究法律责任
贪心算法知识(二)
https://blog.51cto.com/u_15748864/5567242
欢迎光临 华人网 (https://denmark.chineseol.com/)
Powered by Discuz! X3.4