浙江大学DS05Ch10aA高级数据结构课件_第1页
浙江大学DS05Ch10aA高级数据结构课件_第2页
浙江大学DS05Ch10aA高级数据结构课件_第3页
浙江大学DS05Ch10aA高级数据结构课件_第4页
浙江大学DS05Ch10aA高级数据结构课件_第5页
已阅读5页,还剩7页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

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 )

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论