关于贪婪法

源代码 · 2024-9-22 19:56:27

     贪婪法是一种不寻求最优解，只盼望得到较为满意解的方法。贪婪法一样平常可以快速得到满意的解，由于它省去了为找最优解要穷尽全部大概而必须泯灭的大量时间。贪婪法常以当前环境为根本作最优选择，而不思量各种大概的整体环境。
        在求最优解题目的过程中，依据某种贪婪标准，从题目的初始状态出发，直接去求每一步的最优解，通过若干次的贪婪选择，终极得出整个题目的最优解，这种求解方法就是贪默算法。
        从贪默算法的界说可以看出，贪默算法并不是从整体上思量题目，它所做出的选择只是在某种意义上的局部最优解，而由题目自身的特性决定了该题运用贪默算法是否可以得到最优解。

使用贪婪法求解须要留意以下两点：
（1）贪婪法求解是否适合。
用贪婪法解题很方便，但它的实用范围很小，判定一个题目是否适实用贪婪法求解，须要在平常多加训练，依据解题履向来判定是否适合使用贪默算法。如下边的例子：以找币题目为例，假如一个钱币体系有3种币值，面值分别为一角、五分和一分，求最小找币数时，可以用贪婪法求解；假如将这三种币值改为一角一分、五分和一分，就不能使用贪婪法求解。
（2）选择何种贪婪标准才气包管求得最优解。
在选择贪婪标定时，要对所选的贪婪标准举行验证才气使用，不要被外貌上看似正确的贪婪标准所迷惑。

贪婪法的根本原理是从题目的某一个初始解出发徐徐逼近给定的目的，以尽大概快的地求得更好的解。当到达某算法中的某一步不能再继续进步时，算法克制。
因此，贪婪法存在以下题目：
（1）不能包管求得的末了解是最优解；
（2）不能用来求最大或最小解题目；
（3）只能求满意某些束缚条件的可行解的题目。
使用贪婪法解题，通常的解题思绪为：
（1）创建数学模子来形貌题目；
（2）把求解的题目分成若干个子题目；
（3）对每一子题目求解，得到子题目的局部最优解；
（4）把子题目的解局部最优解合成原来解题目的一个解

使用贪婪法解题，通常的步调为以下三步：
（1）从题目的某一初始解出发；
（2）循环求解，求出可行解的一个解元素；
（3）由全部解元素组合成题目的一个可行解。

关于贪婪法

所属分类: 问答交流

新帖推荐: 30日

推荐作品