浙江大学DS05Ch10aA高级数据结构课件.ppt
CHAPTER 10ALGORITHM 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.,1 Greedy Algorithms,1.Huffman Codes for file compression,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,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 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.,3/12,Discussion 9:In what case that there are not likely to be any savings even using Huffman codes?,1 Greedy Algorithms,Representation of the original code in a binary tree/*trie*/,If character Ci is at depth di and occurs fi times,then the cost of the code=di fi.,Cost(aaaxuaxz 0000001001001011)=24+21+22+21=16,Representation of the optimal code in a binary tree,Cost(aaaxuaxz 00010110010111)=14+31+22+31=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/12,Discussion 10:What must the tree look like if we are 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 here*/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 C,5/12,1 Greedy Algorithms,Cost=310+215+212+53+44+213+51=146,6/12,Research 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 to help me determine which ones are correct and which ones are not.Detailed requirements can be downloaded fromhttp:/,7/12,2.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 Case,1 Greedy Algorithms,8/12,1 Greedy Algorithms,Example,Schedule 1,Tavg=(15+23+26+36)/4=25,Schedule 2,Tavg=(3+11+21+36)/4=17.75,In general:,9/12,Best scheduling is to make tik nondecreasing.,1 Greedy Algorithms,The Multiprocessor Case N jobs on P processors,An Optimal Solution,Minimizing the Final Completion Time,NP Hard,10/12,1 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 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.,Example Given N=4,T1234=?,40,11/12,Discussion 11:What if ai=0?,1 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),Example Given N=4,T=O(N log N),12/12,Sorting b2 a1 a2 b1 a3 b3 a4 b4,J2,J1,J3,J4,T1342=?,38,
