4. 贪心算法

What

A greedy algorithm is an algorithmic paradigm that follows the problem solving heuristic of making the locally optimal choice at each stage with the hope of finding a global optimum. In many problems, a greedy strategy does not in general produce an optimal solution, but nonetheless a greedy heuristic may yield locally optimal solutions that approximate a global optimal solution in a reasonable time.
说白了，贪心算法是分步走，每一个找到最优解。总体的找到解不一定是最优解。

Why

Compare to Dynamic Programming

1. A greedy algorithm is effective powerful, beacuse it isn't pay attention to global result.
2. More then appropriate NP(Non-determine Problem) 问题

How to design

1. 贪心算法使用组合优化问题，该问题满足优化原则
2. 求解过程是多步判断过程，最终的判断序列对应问题的最优解
3. 判断一句某种短视的贪心选择原则，原则的好坏决定了算法的成败
4. 贪心法必须进行正确性证明

Greedy Select
input : S=set{1,2 ... n}，活动开始时间Si,截止时间Fi
output : A, it is one of S
A = {1}
j = 1
for i =2 to n do
  if Si > Fj
  then A = A + {i}
    j = i
return A

Sample

1. Generate Minimum Tree

Prim
input : Graphic G = < Vector, Edge, Weight>
output : Tree T
S = {1} // start
T = null
while V - S != null do
  temp = V - S
  j = selectMinimalWeightOfEdge(temp)
  T = T + ei
  S = S + j

Kruskal
input : Graphic G = < Vector, Edge, Weight>
output : Tree T
1. Sorting edges by Weight
2. T = null
3. repeat
4.   e = Minimal edge
5.   if e is not into continue branch T
6.   then T = T + e
7.   E = E - e
8. Until T include n-1 edge