Greedy Algorithm贪心算法.pdf

GreedyGreedy AlgorithmsAlgorithms Dr. Zhenyu He Autumn 2008 11 1616 GreedyGreedyAlgorithmsAlgorithms Similar to dynamic programming. Used for optimization problems. Optimization problems typically go through a sequence of steps, with a set of choices at each step. For manyy opptimization pproblems,, usingg dyynamic pproggrammingg to determine 2 the best choices is overkill (过度的杀伤威力). Greedy Algorithm: Simpler, more efficient 1616 GreedyGreedyAlgorithmsAlgorithms Greedyy alggorithms ((GA)) do not alwayys yyield optimal solutions, but for many problems they do. 3 1616.11, thethe activityactivity-selectionselection problemproblem （（活动安排活动安排）） 16.2, basic elements of the GA; knapsack prob. （贪婪算法的基本特征；背包问题） 16.3, an important application: the design of data compression (Huffman) codes. （哈夫曼编码） 16.5,6.5, uunitt-ttimee tastaskss scscheduedulingg （（有限期作业调度有限期作业调度）） 1616 GreedyGreedyAlgorithmsAlgorithms The ggreedyy method is qquite ppowerful and works well for a wide range of problems: minimumminimum--spanningspanning--treetree algorithmsalgorithms (Chap(Chap 23)23) 4 （最小生成图） shhorttestt pathths ffrom a siinglle source (Ch(Chap 24)24) （最短路径） set-covering heuristic (Chap 35). （集合覆盖） … FirstFirst example:example: ActivityActivity SelectionSelection Horseback Riding (骑马) Canoeing (独木舟) Surfing (冲浪) Driving 5 Swimming Rock Climbing (攀岩) 99 1010 1111 1212 1313 1414 1515 1616 1717 How to make an arrangement to have the more activities?