贪心算法
机器学习中大量使用贪心算法
- Greedy algorithm works only if the local optimum is equal to the global optimum.
- Greedy algorithm does not guarantee optimal solutions. However, it generally produces solutions that are very close in value (heuristics) to the optimal, and hence is intuitively appealing when finding the optimal solution takes too much time.
使用动态规划进行分析
- Algorithm gives non-overlapping intervals
- The result is optimal
假设我们的最优解，贪心算法一定不会更差
这个动态规划不正确，第一个活动中的情况是
- Cast the optimization problem as one in which we make a choice and are left with one subproblem to solve.
- Prove that there is always an optimal solution to the original problem that makes the greedy choice, so that the greedy choice is always safe.
- Demonstrate optimal substructure by showing that, having made the greedy choice, what remains is a subproblem with the property that if we combine an optimal solution to the subproblem with the greedy choice we have made, we arrive at an optimal solution to the original problem.
哈夫曼编码
选出来的第一个元素可以被包含
出现频率更小的字符放在更深的位置里面