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

1、2/12 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 c

2、alled 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 Note: Greedy algorithm works only if the local optimum i

3、s equal to the global optimum. Greedy algorithm does not guarantee optimal solutionse Howevei; 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 4/12

4、1 Huffman Codes 一 for file compression K Example) Suppose our text is a string of length 1000 that comprises the characters a,心 x, and z. Then it will take 8000 bits to store the string as 1000 one-byte characters. We may encode the symbols as a = 00, = 01, x = 10, z = 11. For example, aaaxuaxz isen

5、喇駅鍵屮擁删卩11Then the space taken by the strin驹脚gpg曲胸酿得用异轴哋2 + space for code table. /* I log Cl 丐桎來总 奶皆題护 andard encoding where C is the size ofthe Cha邓御闕虚ntlfy them. frequency:= number of occurrences of a symbol. In string aaaxuaxz, f(a) = 4, f(u)- 1, f(x)- 2, jz) = 1 The size of the coded string can

6、be reduced using variable-length codes,for example, = = ll()x= 10,z =111. 00010110010111 BISCBSSlM In what case that there are not likely to be any savings even using Huffman codes? BISCKSlM 1ft： What must the tree look like if we are to decode unambiguously?3/12 1 Greedy Algorithms Representation o

7、f the original code in a binary tree /* trie */ If character Cf is at depth d and occurs f： times, then the cost of the cod J & 001011) Now, with a = 0, w = 110, x = 10, z = 111 and the string 00010110010111, can you decode it? 1 Greedy Algorithms 6/12 A Huffman/Mgorithm (1952) void Huffman ( Pr

8、iorityQueue heap, int C) consider the C characters as C single node binary trees, and initialize them into a min heap; for(i = 1;i The Single Processor Case Given jobs j j2 ,JN，their running times , t2, , tN , and one processor Schedule jobs to minimize the average completion time. /* assume non pre

9、emptive scheduling */ 1 Greedy Algorithms 10/12 Minimizing the Final Completion Time 9/12 K Example Ji 1 Greedy Algorithms The Multiprocessor Case - N jobs on P processors Example) P=3 job Jl it 4 J5 6 jl Ja 9 time 3 5 6 10 11 14 15 18 20 An Optimal Solution Another Optimal Solution jl J5 J3 6 13 、2

10、 ) 284 71 J5 1 9 2 4 Jl J? 6 jfi ()3 56 1415 2 ) 30 34 An Optimal Solution job j 4 Jl J4 7 () 35 9 1416 19 34 1 Greedy Algorithms 12/12 Flow Shop Scheduling 一 a simple case with 2 processors Consider a machine shop that has 2 identical processors Px and P2. We have N jobs 儿JN that need to be process

11、ed. Each job can be broken into 2 tasks j“ and ji2 A schedule is an assignment of jobs to time intervals on machines such that 甘甘 jq must be processed by Pj and the processing time is 甘甘 No machine processes more than one job at any time. may not be started beforeJit is finished. 3 4 8 IO KExample)

12、GivenN = 4, j = 卩皿=40 6 2 9 15 3 Construct a minimum-completion-tinie 2 machine schedule for a given set of N jobs. Let a = ta 丰丰 0, and bt =切It What if a( = 0? 1 Greedy Algorithms 【Proposition An optimal schedule exists if min b, cij n min bt y a for any pair of adjacent jobs and Jy. 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 = a|) & ( J)is not in the schedule ) Place J| at the leftmost empty position ; else if ( m = bj) & ( Jj i