首页> 算法/机器学习校招面试题目合集> 贪婪算法
219

问答题 219 /376

贪婪算法

参考答案

参考回答：

贪婪算法(贪心算法)是指在对问题进行求解时，在每一步选择中都采取最好或者最优(即最有利)的选择，从而希望能够导致结果是最好或者最优的算法。贪婪算法所得到的结果往往不是最优的结果(有时候会是最优解)，但是都是相对近似(接近)最优解的结果。贪婪算法并没有固定的算法解决框架，算法的关键是贪婪策略的选择，根据不同的问题选择不同的策略。

必须注意的是策略的选择必须具备无后效性，即某个状态的选择不会影响到之前的状态，只与当前状态有关，所以对采用的贪婪的策略一定要仔细分析其是否满足无后效性。

其基本的解题思路为：1)建立数学模型来描述问题;2)把求解的问题分成若干个子问题;3)对每一子问题求解，得到子问题的局部最优解;4)把子问题对应的局部最优解合成原来整个问题的一个近似最优解。

纠错 收藏
查看讨论
上一题 下一题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号