贪心算法是指，在对问题求解时，总是做出在当前
各位读友大家好，此文档由网络收集而来，欢迎您下载，谢谢
贪心算法。
贪心算法是指。
在对问题求解时。
总是做出在当前看来是最好的选择。
也就是说。
不从整体最优上加以考虑。
他所做出的是在某种意义上的局部最优解。
贪心算法不是对所有问题都能得到整体最优解。
关键是贪心策略的选择。
选择的贪心策略必须具备无后效性。
即某个状态以前的过程不会影响以后的状态。
只与当前状态有关。
中文名,贪心算法。
别称,贪婪算法。
性质,一种改进了的分级处理方法。
核心,根据题意选取一种量度标准。
基本要素。
贪心选择是指所求问题的整体最优解可以通过一系列局部最优
的选择。
即贪心选择来达到。
这是贪心算法可行的第一个基本要素。
也是贪心算法与动态规划算法的主要区别。
贪心选择是采用从顶向下。
以迭代的方法做出相继选择。
每做一次贪心选择就将所求问题简化为一个规模更小的子问题。
对于一个具体问题。
要确定它是否具有贪心选择的性质。
我们必须证明每一步所作的贪心选择最终能得到问题的最优解。
通常可以首先证明问题的一个整体最优解。
是从贪心选择开始的。
而且作了贪心选择后。
原问题简化为一个规模更小的类似子问题。
然后。
用数学归纳法证明。
通过每一步贪心选择。
最终可得到问题的一个整体最优解。
当一个问题的最优解包含其子问题的最优解时。
称此问题具有最优子结构性质。
运用贪心策略在每一次转化时都取得了最优解。
问题的最优子结构性质是该问题可用贪心算法或动态规划算法求解的关键特征。
贪心算法的每一次操作都对结果产生直接影响。
而动态规划则不是。
贪心算法对每个子问题的解决方案都做出选择。
不能回退；动态规划则会根据以前的选择结果对当前进行选择。
有回退功能。
动态规划主要运用于二维或三维问题。
而贪心一般是一维问题。
基本思路。
贪心算法的基本思路是从问题的某一个初始解出发一步一步地进行。
根据某个优化测度。
每一步都要确保能获得局部最优解。
每一步只考虑一个数据。
他的选取应该满足局部优化的条件。
若下一个数据和部分最优解连在一起不再是可行解时。
就不把该数据添加到部分解中。
直到把所有数据枚举完。
或者不能再添加算法停止。
算法特性。
贪婪算法可解决的问题通常大部分都有如下的特性：。
例题分析。
有一个背包。
背包容量是M=150kg。
有7个物品。
物品不可以分割成任
意大小。
要求尽可能让装入背包中的物品总价值最大。
但不能超过总容量。
物品A B C D E F G重量35kg 30kg 6kg 50kg 40kg 10kg 25kg价值10$ 40$ 30$ 50$ 35$ 40$ 30$分析：目标函数：∑pi最大约束条件是装入的物品总重量不超过背包容量：∑wi 64输出一个解。
返回上一步骤c--的八个方位的子结点。
选出那些可行的子结点循环遍历所有可行子结点。
步骤c++重复2显然⑵是一个递归调用的过程。
大致如下：C++程序：Pascal程序：这样做是完全可行的。
它输入的是全部解。
但是马遍历当8×8时解是非常之多的。
用天文数字形容也不为过。
这样一来求解的过程就非常慢。
并且出一个解也非常慢。
怎么才能快速地得到部分解呢？【贪心算法】其实马踏棋盘的问题很早就有人提出。
且早在1823年。
就提出了一个有名的算法。
在每个结点对其子结点进行选取时。
优先选择
‘出口’最小的进行搜索。
‘出口’的意思是在这些子结点中它们的可行子结点的个数。
也就是‘孙子’结点越少的越优先跳。
为什么要这样选取。
这是一种局部调整最优的做法。
如果优先选择出口多的子结点。
那出口少的子结点就会越来越多。
很可能出现‘死’结点。
这样对下面的搜索纯粹是徒劳。
这样会浪费很多无用的时间。
反过来如果每次都优先选择出口少的结点跳。
那出口少的结点就会越来越少。
这样跳成功的机会就更大一些。
这种算法称为为贪心算法。
也叫贪婪算法或启发式算法。
它对整个求解过程的局部做最优调整。
它只适用于求较优解或者部分解。
而不能求最优解。
这样的调整方法叫贪心策略。
至于什么问题需要什么样的贪心策略是不确定的。
具体问题具体分析。
实验可以证明马遍历问题在运用到了上面的贪心策略之后求解速率有非常明显的提高。
如果只要求出一个解甚至不用回溯就可以完成。
因为在这个算
法提出的时候世界上还没有计算机。
贪婪
这种方法完全可以用手工求出解来。
其效率可想而知。
备注。
贪心算法当然也有正确的时候。
求最小生成树的Prim算法和Kruskal 算法都是漂亮的贪心算法。
贪心法的应用算法有Dijkstra的单源最短路径和Chvatal的贪心集合覆盖启发式所以需要说明的是。
贪心算法可以与随机化算法一起使用。
具体的例子就不再多举了。
其实很多的智能算法。
本质上就是贪心算法和随机化算法结合——这样的算法结果虽然也是局部最优解。
但是比单纯的贪心算法更靠近了最优解。
例如遗传算法。
模拟退火算法。
应用。
贪婪如把3/7和13/23分别化为三个单位分数的和【贪心算法】设a。
b为互质正整数。
a。
各位读友大家好，此文档由网络收集而来，欢迎您下载，谢谢。