《浙江大学DS05Ch10aA高级数据结构.ppt》由会员分享，可在线阅读，更多相关《浙江大学DS05Ch10aA高级数据结构.ppt（12页珍藏版）》请在金锄头文库上搜索。
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 Cod
4、es 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/12Discussion 9:Discussion 9:Discussion 9:Discussion
7、 9: In what case that there are not likely to In what case that there are not likely to be any savings even using Huffman codes? be any savings even using Huffman codes? 1 Greedy AlgorithmsaxuzRepresentation of the original code in a binary tree /* trie */000111 If character Ci is at depth di and oc
8、curs 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 + 2 2 + 3 1 = 14 The answer is aaaxuaxz (with a = 0, u = 110, x = 10, z = 111). W
9、hat 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/12Discussion 10:Discussion 10:Discussion 10:Discussion 10: What must the tree look like if we are What must the tree look like
10、if we are to decode unambiguously? to decode unambiguously? 1 Greedy Algorithms Huffmans Algorithm (1952)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 he
11、re */ delete root from min heap and attach it to left_child of node; delete root from min heap and attach 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
12、 AlgorithmsExampleCifiaeis1015123tspnl4131a10e15i12s3t4sp13nl1a10e15i12s3t4sp13nl1nl1s3t44i12e15sp13a10nl1s3t44i12e15sp13a108nl1s3t44i12e15sp13a10818nl1s3t44i12e15sp13a1081825nl1s3t44i12e15sp13a108182533nl1s3t44i12e15sp13a10818253358000000111111aeistspnl: 111: 10: 00: 11011: 1100: 01: 11010Cost = 3
13、10 + 2 15 + 2 12 + 5 3 + 4 4 + 2 13 + 5 1 = 1466/12Research Project 4Huffman Codes (30) As a professor 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 t
14、o help me determine which ones are correct and which ones are not. Detailed requirements can be downloaded 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 nonpr
15、eemptive scheduling */ The Single Processor Case1 Greedy Algorithms8/121 Greedy AlgorithmsExamplejobtimej1j2j3j4158310Schedule 1j1015j223j326j436Tavg = ( 15 + 23 + 26 + 36 ) / 4 = 25Schedule 2j136j2110j33j421Tavg = ( 3 + 11 + 21 + 36 ) / 4 = 17.75In general:0ji1ti1ji2ti1 + ti2ji3ti1 + ti2 + ti3 9/12
16、Best scheduling is to make tik nondecreasing.1 Greedy Algorithms The Multiprocessor Case N jobs on P processorsExampleP = 3jobtimej1j2j3j435610j5j6j7j811141518j920An Optimal Solutionj13j25j360j413j516j620j728j834j940Another Optimal Solutionj13j25j360j415j514j620j730j838j934 Minimizing the Final Comp
17、letion TimeNP HardAn Optimal Solutionj13j25j39j419j516j614j7j834j9010/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 t
18、asks ji1 and ji2 . A schedule is an assignment of jobs to time 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
19、schedule for a given set of N jobs.Let ai = ti1 0, and bi = ti2 .Example Given N = 4, T1234 = ?4011/12Discussion 11:Discussion 11:Discussion 11:Discussion 11: What if What if a ai i = 0? = 0? 1 Greedy Algorithms【Proposition】 An optimal schedule exists if min bi , aj min bj , ai for any pair of adjac
20、ent 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 ) ) Place Ji at the left-most empty position ; else if ( ( m = bj ) & ( Jj is not in the schedule ) ) Place Jj at the right-most empty position ; m = next minimum element ; while ( m );Example Given N = 4, T = O( N log N )12/12Sorting b2 a1 a2 b1 a3 b3 a4 b4 J2J1J3J4T1342 = ?38
