贪心法
贪心法的基本思想
- 每个阶段面临选择时，贪心法都做出对眼前情况的最优解，不考虑后续影响。
- 每个阶段的决策一旦做出，不可以更改，不能回溯
- 贪心法是根据贪心策略来逐步构造问题的解，策略不同结果不同
- 贪心法具有高效性和不稳定性，它可以很快得到解，但不一定是最优解。
贪心算法的好坏关键在于贪心策略的选择
贪心法的基本要素（适合的问题）
- 最优子结构性质——当一个问题的最优解一定包含其子问题的最优解时，则该问题具有最优子结构性质
- 贪心选择性质——所求问题的整体最优解可以通过一系列局部最优的选择获得。
贪心法的解题步骤及算法设计模式
分解->解决->合并
会议安排问题
策略是选择会议结束时间最早且不与已经安排的会议冲突的会议。
哈夫曼树
是一棵二叉树，一个字符串中出现概率越小的字符越远离根节点，越大的字符越靠近根进点，时间复杂度为O(n^2)，可以用最小堆优化成O(nlogn);
最小生成树
Prim算法
思路：选定一个顶点加入已选点的集合，然后选择与已选点有相邻最近边且不成环的点，加入已选点的集合，依次类推直到所有点加入集合，复杂度为O(n^2)
循环n次，每次循环里循环找出当前最短的那条边（由lowcost数组存放）与所连的结点，这个结点记做已访问，然后循环这个结点所连的边，如果比LowCost中短的则更新。
Krusal算法（避环法）
思路：每次找出图中最短的边，然后判断它是不是会变成回路，不会则加入，直到没有可以加的边为止。
时间复杂度：O(eloge)——其中的e为边数，O(n^2logn)——为完全图时，O(nlogn)——为平面图时。
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请联系我们，一经查实，本站将立刻删除。
如需转载请保留出处：https://51itzy.com/kjqy/127692.html