本文共 498 字,大约阅读时间需要 1 分钟。
本文参考:《算法的乐趣》,老师上课ppt
一般将求解过程分为若干个步骤,在每个步骤都应用贪心原则,选择当前状态下最好或最优的解。
贪心算法与其他算法最大的不同:
贪婪法每一步选择结束后,局部最优解就确定了,不再进行回溯处理。也就是说,每一个步骤的局部最优解确定后,就不再进行修改,直到算法结束。
贪婪法只在少部分情况下可以得到最优解,如 Dijkstra 算法、Kruskal 与 Prim 最小生成树算法、Huffman构造算法(该复习了吖?)
贪婪法的基本设计思想:
(1) 建立对问题精确描述的数学模型,包括定义最优解的模型;
(2) 将问题分解为一系列子问题,同时定义子问题的最优子结构;
(3) 应用贪心原则确定每一个子问题的局部最优解,并根据最优解的模型,用子问题的局部最优解堆叠出全局最优解。
如:
需要注意的是,0 - 1背包不可以使用贪心算法求解,而部分背包问题可以使用贪心算法求解。
转载地址:http://zxtai.baihongyu.com/