浙江大学DS05_Ch10a_A高级数据结构课件.ppt

CHAPTER 10 ALGORITHM DESIGN TECHNIQUES § 1 Greedy Algorithms ? Optimization Problems: Given a set of constrains and an optimization function . Solutions that satisfy the constrains are called feasible solutions . A feasible solution for which the optimization function has the best possible value is called an optimal solution .? The Greedy Method: Make the best decision at each stage, under some greedy criterion . A decision made in one stage is not changed in a later stage, so each decision should assure feasibility . 1/12 § 1 Greedy Algorithms 2/12 Note: ? 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. Note: ? 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. § 1 Greedy Algorithms 1. Huffman Codes – for pression 〖 Example 〗 Suppose our text is a string of length 1000 that comprises the characters a, u, x , and z . Then it will take ? bits to store the string as 1000 one-byte characters. 8000 Notice that we have only 4 distinct characters in that string. Hence we need only 2 bits to identify them. We may encode the symbols as a = 00 , u = 01 , x = 10 , z = 11 . For example, aaa xuaxz is encoded as 000000 1001001011 . Then the space taken by the string with length 1000 will be 2000 bits + space for code table. /*? log C ? bits are needed in a standard encoding where C is the size of the charac