第05章基本技术FundamentalTechniques.ppt
《第05章基本技术FundamentalTechniques.ppt》由会员分享,可在线阅读,更多相关《第05章基本技术FundamentalTechniques.ppt(45页珍藏版)》请在三一办公上搜索。
1、Chapter 5:Techniques,1,Fundamental Techniques,Chapter 5:Techniques,2,Outline and Reading,The Greedy Method Technique(5.1)Fractional Knapsack Problem(5.1.1)Task Scheduling(5.1.2)Divide-and-conquer paradigm(5.2)Recurrence Equations(5.2.1)Integer Multiplication(5.2.2)Optional:Matrix Multiplication(5.2.
2、3)Dynamic Programming(5.3)Matrix Chain-Product(5.3.1)The General Technique(5.3.2)0-1 Knapsack Problem(5.3.3),Chapter 5:Techniques,3,The Greedy Method Technique,The greedy method is a general algorithm design paradigm,built on the following elements:configurations:different choices,collections,or val
3、ues to findobjective function:a score assigned to configurations,which we want to either maximize or minimizeIt works best when applied to problems with the greedy-choice property:a globally-optimal solution can always be found by a series of local improvements from a starting configuration.,Chapter
4、 5:Techniques,4,Making Change,Problem:A dollar amount to reach and a collection of coin amounts to use to get there.Configuration:A dollar amount yet to return to a customer plus the coins already returnedObjective function:Minimize number of coins returned.Greedy solution:Always return the largest
5、coin you canExample 1:Coins are valued$.32,$.08,$.01Has the greedy-choice property,since no amount over$.32 can be made with a minimum number of coins by omitting a$.32 coin(similarly for amounts over$.08,but under$.32).Example 2:Coins are valued$.30,$.20,$.05,$.01Does not have greedy-choice propert
6、y,since$.40 is best made with two$.20s,but the greedy solution will pick three coins(which ones?),Chapter 5:Techniques,5,The Fractional Knapsack Problem,Given:A set S of n items,with each item i havingbi-a positive benefitwi-a positive weightGoal:Choose items with maximum total benefit but with weig
7、ht at most W.If we are allowed to take fractional amounts,then this is the fractional knapsack problem.In this case,we let xi denote the amount we take of item iObjective:maximizeConstraint:,Chapter 5:Techniques,6,Example,Given:A set S of n items,with each item i havingbi-a positive benefitwi-a posi
8、tive weightGoal:Choose items with maximum total benefit but with weight at most W.,Weight:,Benefit:,1,2,3,4,5,4 ml,8 ml,2 ml,6 ml,1 ml,$12,$32,$40,$30,$50,Items:,Value:,3,($per ml),4,20,5,50,Solution:1 ml of 5 2 ml of 3 6 ml of 4 1 ml of 2,“knapsack”,Chapter 5:Techniques,7,The Fractional Knapsack Al
9、gorithm,Greedy choice:Keep taking item with highest value(benefit to weight ratio)Since Run time:O(n log n).See P.260Knapsack satisfies Greedy-Choice Property:there is an item i with higher value than a chosen item j(i.e.,vivj)but xi0 If we substitute some i with j,we get a better solutionHow much o
10、f i:y=minwi-xi,xj.Thus we can replace y of item j with an equal amount of item I,which is the greedy choice property.,Algorithm fractionalKnapsack(S,W)Input:set S of items w/benefit bi and weight wi;max.weight WOutput:amount xi of each item i to maximize benefit with weight at most Wfor each item i
11、in Sxi 0vi bi/wi valuew 0total weightwhile w W remove item i with highest vixi minwi,W-ww w+minwi,W-w,Chapter 5:Techniques,8,Task Scheduling,Given:a set T of n tasks,each having:A start time,siA finish time,fi(where si fi)Goal:Perform all the tasks using a minimum number of“machines.”Note only one t
12、ask per machine at atime.,1,9,8,7,6,5,4,3,2,Machine 1,Machine 3,Machine 2,Chapter 5:Techniques,9,Task Scheduling Algorithm,Greedy choice:consider tasks by their start time and use as few machines as possible with this order.Run time:O(n log n).Why?Correctness:Suppose there is a better schedule.We ca
13、n use k-1 machinesThe algorithm uses kLet i be first task scheduled on machine kMachine i must conflict with k-1 other tasksBut that means there is no non-conflicting schedule using k-1 machines,Algorithm taskSchedule(T)Input:set T of tasks w/start time si and finish time fiOutput:non-conflicting sc
14、hedule with minimum number of machinesm 0no.of machineswhile T is not emptyremove task i w/smallest siif theres a machine j for i thenschedule i on machine j else m m+1schedule i on machine m,Chapter 5:Techniques,10,Example,Given:a set T of n tasks,each having:A start time,siA finish time,fi(where s
15、i fi)1,4,1,3,2,5,3,7,4,7,6,9,7,8(ordered by start)Goal:Perform all tasks on min.number of machines,1,9,8,7,6,5,4,3,2,Machine 1,Machine 3,Machine 2,Chapter 5:Techniques,11,Divide-and-Conquer,Chapter 5:Techniques,12,Divide-and-Conquer,Divide-and conquer is a general algorithm design paradigm:Divide:di
16、vide the input data S in two or more disjoint subsets S1,S2,Recur:solve the subproblems recursivelyConquer:combine the solutions for S1,S2,into a solution for SThe base case for the recursion are subproblems of constant sizeAnalysis can be done using recurrence equations,Chapter 5:Techniques,13,Merg
17、e-Sort Review,Merge-sort on an input sequence S with n elements consists of three steps:Divide:partition S into two sequences S1 and S2 of about n/2 elements eachRecur:recursively sort S1 and S2Conquer:merge S1 and S2 into a unique sorted sequence,Algorithm mergeSort(S,C)Input sequence S with n elem
18、ents,comparator C Output sequence S sortedaccording to Cif S.size()1(S1,S2)partition(S,n/2)mergeSort(S1,C)mergeSort(S2,C)S merge(S1,S2),Chapter 5:Techniques,14,Recurrence Equation Analysis,The conquer step of merge-sort consists of merging two sorted sequences,each with n/2 elements and implemented
19、by means of a doubly linked list,takes at most bn steps,for some constant b.Likewise,the basis case(n 2)will take at b most steps.Therefore,if we let T(n)denote the running time of merge-sort:We can therefore analyze the running time of merge-sort by finding a closed form solution to the above equat
20、ion.That is,a solution that has T(n)only on the left-hand side.,Chapter 5:Techniques,15,Iterative Substitution,In the iterative substitution,or“plug-and-chug,”technique,we iteratively apply the recurrence equation to itself and see if we can find a pattern:Note that base,T(n)=b,case occurs when 2i=n
21、.That is,i=log n.So,Thus,T(n)is O(n log n).,Chapter 5:Techniques,16,The Recursion Tree,Draw the recursion tree for the recurrence relation and look for a pattern:,Total time=bn+bn log n,(last level plus all previous levels),Chapter 5:Techniques,17,Guess-and-Test Method,In the guess-and-test method,w
22、e guess a closed form solution and then try to prove it is true by induction:Guess:T(n)cn log n.Wrong:we cannot make this last line be less than cn log n,Chapter 5:Techniques,18,Guess-and-Test Method,Part 2,Recall the recurrence equation:Guess#2:T(n)b.So,T(n)is O(n log2 n).In general,to use this met
23、hod,you need to have a good guess and you need to be good at induction proofs.,Chapter 5:Techniques,19,Master Method,Many divide-and-conquer recurrence equations have the form:The Master Theorem:,Chapter 5:Techniques,20,Master Method,Example 1,The form:The Master Theorem:Example:,Solution:logba=2,so
24、 case 1 says T(n)is O(n2).,Chapter 5:Techniques,21,Master Method,Example 2,The form:The Master Theorem:Example:,Solution:logba=1,so case 2 says T(n)is O(n log2 n).,Chapter 5:Techniques,22,Master Method,Example 3,The form:The Master Theorem:Example:,Solution:logba=0,so case 3 says T(n)is O(n log n).,
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 05 基本 技术 FundamentalTechniques
链接地址:https://www.31ppt.com/p-6614730.html