浙江大学DS05Ch10aA高级数据结构课件

1、chapter 10algorithm design techniques1 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 a

2、n 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/121 greedy algorithms2/12note: greedy algorithm works only if the local optimum is equa

3、l 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 algorithms1. huffman co

4、des for file compressionexample 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

5、 them. we may encode the symbols as a = 00, u = 01, x = 10, z = 11. for example, aaaxuaxz is encoded as 0000001001001011. 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 character

6、 set */ frequency := number of occurrences of a symbol.in string aaaxuaxz , f(a) = 4, f(u) = 1, f(x) = 2, f(z) = 1.the size of the coded string can be reduced using variable-length codes, for example, a = 0, u = 110, x = 10, z = 111. 000101100101113/121 greedy algorithmsaxuzrepresentation of the ori

7、ginal code in a binary tree /* trie */000111 if character ci is at depth di and occurs fi times, then the cost of the code = di fi .cost ( aaaxuaxz 0000001001001011 ) = 2 4 + 2 1 + 2 2 + 2 1 = 16representation of the optimal code in a binary treeauxz000111cost ( aaaxuaxz 00010110010111 ) = 1 4 + 3 1

8、 + 2 2 + 3 1 = 14 the answer is aaaxuaxz (with a = 0, u = 110, x = 10, z = 111). what makes this decoding method work?the trick is:no code is a prefix of another. now, with a = 0, u = 110, x = 10, z = 111 and the string 00010110010111,can you decode it?4/121 greedy algorithms huffmans algorithm (195

9、2)void huffman ( priorityqueue heap , int c ) consider the c characters as c single node binary trees, and initialize them into a min heap; for ( i = 1; i c; i+ ) create a new node; /* be greedy here */ delete root from min heap and attach it to left_child of node; delete root from min heap and atta

10、ch it to right_child of node; weight of node = sum of weights of its children; /* weight of a tree = sum of the frequencies of its leaves */ insert node into min heap; t = o( ? )c log c5/121 greedy algorithmsexamplecifiaeis1015123tspnl4131a10e15i12s3t4sp13nl1a10e15i12s3t4sp13nl1nl1s3t44i12e15sp13a10

11、nl1s3t44i12e15sp13a108nl1s3t44i12e15sp13a10818nl1s3t44i12e15sp13a1081825nl1s3t44i12e15sp13a108182533nl1s3t44i12e15sp13a10818253358000000111111aeistspnl: 111: 10: 00: 11011: 1100: 01: 11010cost = 3 10 + 2 15 + 2 12 + 5 3 + 4 4 + 2 13 + 5 1 = 1466/12research project 4huffman codes (30) as a professor

12、who gives the final exam problem on huffman codes, i am encountering a big problem: the huffman codes are not unique. the students are submitting all kinds of codes, and i need a computer program to help me determine which ones are correct and which ones are not. detailed requirements can be downloa

13、ded fromhttp:/ a simple scheduling problem given n jobs j1 , j2 , , jn , their running times t1 , t2 , , tn , and one processor.schedule jobs to minimize the average completion time./* assume nonpreemptive scheduling */ the single processor case1 greedy algorithms8/121 greedy algorithmsexamplejobtim

14、ej1j2j3j4158310schedule 1j1015j223j326j436tavg = ( 15 + 23 + 26 + 36 ) / 4 = 25schedule 2j136j2110j33j421tavg = ( 3 + 11 + 21 + 36 ) / 4 = 17.75in general:0ji1ti1ji2ti1 + ti2ji3ti1 + ti2 + ti3 9/12 nkinkinkikkktktntknc111)1()1(cost totalbest scheduling is to make tik nondecreasing.1 greedy algorithm

15、s the multiprocessor case n jobs on p processorsexamplep = 3jobtimej1j2j3j435610j5j6j7j811141518j920an optimal solutionj13j25j360j413j516j620j728j834j940another optimal solutionj13j25j360j415j514j620j730j838j934 minimizing the final completion timenp hardan optimal solutionj13j25j39j419j516j614j7j83

16、4j9010/121 greedy algorithms flow shop scheduling a simple case with 2 processors consider a machine shop that has 2 identical processors p1 and p2 . we have n jobs j1, . , jn that need to be processed. each job ji can be broken into 2 tasks ji1 and ji2 . a schedule is an assignment of jobs to time

17、intervals on machines such that jij must be processed by pj and the processing time is tij . no machine processes more than one job at any time. ji2 may not be started before ji1 is finished.construct a minimum-completion-time 2 machine schedule for a given set of n jobs.let ai = ti1 0, and bi = ti2

18、 .example given n = 4, 1592610843jt1234 = ? 4011/121 greedy algorithms【proposition】 an optimal schedule exists if min bi , aj min bj , ai for any pair of adjacent jobs ji and jj . all the schedules with this property have the same completion time.algorithm sort a1 , . , an , b1 , . , bn into non-decreasing sequence ; m = minimum element ; do if ( ( m = ai ) & ( ji is not in the schedule )