有很多门课,上课的时间和时长可能会交叉,那要怎么安排在某间教室的课程安排,且最大程度利用好这间教室呢?
---按课程时间选出不冲突的,比如9:00--10:00 10:00---11;00,而不是选9:00--10:00 9:20--10:30
这就是贪婪算法,每步选择最优,也就是选择局部最优解,并非在任何情况下都行之有效,但是易于实现---联想OMP算法也是贪婪算法,每次都找到投影最大值最大的那一列
有个小偷要偷东西,现在有如上图三种东西可以偷,但是他的包只能装35kg的东西,那他偷东西的时候要怎么选最优呢? 如果开始就选了最贵的,但是重量达到30,他就没法再装下大于5的东西了,那要怎么办呢? 说明:贪婪策略斌不能获得最优解--有些情况下,完美是优秀的敌人
商人要到各个城市去,要找一条最短路径,如果要找出最短路径得把所有可能的结果都列出来是n的阶乘问题n! 所以找到一条比较短的就不错了,从出发城市开始,选择下一个城市时,就选还没去最短的城市
学习识别NPhard完全问题,以免浪费时间去寻找解决答案 1.阶乘问题 2.需要找出所有的结果,涉及所有组合 3.元素较少时,算法的运行速度非常快,但随着元素数量的增加,速度会变得非常慢 4.不能将问题分为小问题,必须考虑所有情况,可能就是NPHard问题 5.如果问题涉及序列,如旅行商问题中的城市序列,难以解决,可能就是NPHard问题 6.如果问题转为集合覆盖问题或旅行商问题,肯定是NPHard问题
贪婪算法寻找局部最优解,企图以这种方式获得全局最优解 对于NPHard问题,还没有找到快速解决方案 面临NPHard问题,最佳做法是使用近似算法 贪婪算法易于实现,运行速度快,是不错的近似算法