For Optimization Problems Alexandra Stefan

2y ago
13 Views
3 Downloads
1.05 MB
28 Pages
Last View : 1m ago
Last Download : 2m ago
Upload by : Nixon Dill
Transcription

Greedy Algorithmsfor Optimization ProblemsAlexandra Stefan4/20/20211

Optimization Problems Knapsack problem:– Thief in a store has a backpack. Can only steal as much as fits in hisbackpack. What objects should he pick to make the most money? Givendata: W-knapsack capacity, N – number of different types of items; valueand weight (vi,wi) of each item.– Versions – see next page Job Scheduling (a.k.a. Interval Scheduling)– Given N jobs with (start time, end time, value) pick a set of jobs that donot overlap and give the most money. Variation: all jobs have the same value Hufmann coding– File compression: encode symbols in a text file s.t. the file has thesmallest size possible. Graphs – Minimum Spanning Tree (MST-Prim’s Algorithm) Terminology:– Problem - general– Variations of a problem – additional specification to the general problem– Instance of a problem – specific data (what I use in examples areinstances of the problem being discussed problem)2

Greedy Method for Optimization Problems Optimization problem – multiple possible solutions, pick the one that gives themost value (or lowest cost) Greedy:– Method: Pick a criterion that reflects the measure you are optimizing for (value or cost)E.g. for Huffman minimize the storage (cost), for Knapsack maximize the money (value) take the action that is best now (out of the current options) according to your criterion(i.e. pick a local optimal). You commit to it, it may limit your future choices and causeyou to not find the global optimum.– It may cause you to miss the optimal solution– You build the solution as you go. No need to back trace it. Examples:– Knapsack Optimal answer for the easy (fractional) version using ratio, but not for the others.– Interval scheduling Optimal answer for the easy (same value jobs) version (using job that finishes first) , butnot for the others.– Huffman codes Optimal solution: pick the two smallest weight trees. Used for file compression. Prefix codes: no code is also a prefix of another code. Huffman tree to decode (the code for a character, x, takes you to the leaf with x)3

The Knapsack Problem A thief breaks into a store.The maximum total weight that he can carry is W.There are N types of items at the store.Each type ti has a value vi and a weight wi.What is the maximum total value that he can carry out? What items should he pick to obtain this maximum value?Image from WikipediaAll versions have:Typical version:0/1(only one of each object)Nnumber of different types of objectsWthe maximum capacity (kg)v1, v2, ,vNValue for each object. ( )Can either pick object i,or not pick it.w1, w1, ,wN, Weight of each object. (kg)Unbounded(unlimited number ofeach object)Can pick any object,any number of times.Bounded(limited number of each object)Can pick object i, at most ci times.(Not covered in this class)FractionalFor each item can take thewhole quantity, or a fraction ofthe quantity.The only variationthat Greedy cansolve optimallyVariations we will discuss here:0/1 non-fractional0/1 fractionalUnbounded non-fractional Unbounded fractional4

All four versions example – NOT optimalItemABCDEValue ( )45111415Weight (kg)34789W 21 (i.e. the Knapsack capacity is 21)Price per kilogram value/weight.E.g. for B we have 5 /4kg 1.25 /kg .(Useful for the fractional version in calculating themoney made from using a fraction of an item. See theexamples for the fractional problems below.)C (11 )A (4 , 3kg)B (5 , 4kg)C (11 , 7kg)D (14 , 8kg)E (15 , 9kg)A (4 )E (15 )0/1, NF30D (14 )C (11 )C (11 )W 21 (knapsack capacity is 21)B (5 )C (11 )E (15 , 9kg)B (5 )B (5 )inf, NF29Fraction of E ( 7kg*15 /9kg)A (4 , 3kg)Fraction ofB (2*5/4)inf, F33.750/1, F32.55

Knapsack – Greedy solution What would a greedy thief do?– Criterion: value/weight ratio– Method: Sort in decreasing order of value/weight ratio. Pick as many of the largest ratio as possible. After that, try to take as many ofthe next ratio as possible and so on.– Does NOT give an optimal solution. See next page. Would any of the 4 variations be solved optimally using Greedy?(Prove or give counter-example)– Yes. The fractional version.6

Worksheet (make copies)ItemABCDEValue45111415Weight34789Ratio4/3 1.35/4 1.2511/7 1.5714/8 1.7515/9 1.67Reordered decreasing by ratio:D, E, C, A, B1.75, 1.67, 1.57, 1.3, 1.25D (1.75 14/8)E (1.67 15/9)C (1.57 11/7)A (1.3 4/3)B (1.25 5/4)W 21 (knapsack capacity is 21)7

0/1 Not Fractional, RatioItemABCDEValue45111415Weight34789Ratio4/3 1.35/4 1.2511/7 1.5714/8 1.7515/9 1.67Reordered decreasing by ratio:D (1.75 14/8)E (1.67 15/9)D, E, C, A, B1.75, 1.67, 1.57, 1.3, 1.25C (1.57 11/7)A (1.3 4/3)We can only pick entire objects, mustskip those that do not fit. We have onlyone of each object.D (1.75 14/8)B (1.25 5/4)E (1.67 15/9)A (1.3 4/3)W 21 (knapsack capacity is 21)Total value value(D) value(E) value(A) 14 15 4 338

Unbounded Not Fractional, RATIOItemABCDEValue45111415Weight34789Ratio4/3 1.35/4 1.2511/7 1.5714/8 1.7515/9 1.67Reordered decreasing by ratio:D, E, C, A, B1.75, 1.67, 1.57, 1.3, 1.25D (1.75 14/8)E (1.67 15/9)C (1.57 11/7)A (1.3 4/3)We can only pick entire objects, mustskip those that do not fit. We haveunlimited number of objects, thus we canpick as many of D as we can fit in.D (1.75 14/8)B (1.25 5/4)D (1.75 14/8)A (1.3 4/3)W 21 (knapsack capacity is 21)Total value value(D) value(D) value(A) 14 14 4 32(D was selected twice)9

Unbounded Fractional, RATIO - SolutionItemABCDEValue45111415Weight34789Ratio4/3 1.35/4 1.2511/7 1.5714/8 1.7515/9 1.67Reordered decreasing by ratio:D, E, C, A, B1.75, 1.67, 1.57, 1.3, 1.25D (1.75 14/8)E (1.67 15/9)C (1.57 11/7)A (1.3 4/3)We can pick a fraction of an object, mustskip those that do not fit. We haveunlimited number of objects, thus we canpick only D (entire objects and a fraction).D (1.75 14/8)B (1.25 5/4)D (1.75 14/8)Fraction of D (1.75 14/8)W 21 (knapsack capacity is 21)Total value value(D) value(D) remining weight*(value(D)/weight(D)) capacity kg* ( /kg for D) 21kg*(14 /8kg) 36.75 10

0/1 Fractional, RATIO - SolutionItemABCDEValue45111415Weight34789Ratio4/3 1.35/4 1.2511/7 1.5714/8 1.7515/9 1.67Reordered decreasing by ratio:D (1.75 14/8)E (1.67 15/9)D, E, C, A, B1.75, 1.67, 1.57, 1.3, 1.25C (1.57 11/7)A (1.3 4/3)We can pick a fraction of an object, mustskip those that do not fit. We have onlyONE of each object.D (1.75 14/8)E (1.67 15/9)B (1.25 5/4)Fraction of CW 21 (knapsack capacity is 21)Total value value(D) value(E) remining weight*(value(C)/weight(C)) 14 15 4kg* (11 /7kg) 35.28 11

All four versions, RatioItemABCDEValue45111415Weight34789Ratio4/3 1.35/4 1.2511/7 1.5714/8 1.7515/9 1.67Reordered decreasing by ratio:D, E, C, A, BD (1.75 14/8)E (1.67 15/9)C (1.57 11/7)A (1.3 4/3)B (1.25 5/4)1.75, 1.67, 1.57, 1.3, 1.25D (1.75 14/8)E (1.67 15/9)A (1.3 4/3)0/1, NF33D (1.75 14/8)D (1.75 14/8)A (1.3 4/3)D (1.75 14/8)D (1.75 14/8)Fraction of DD (1.75 14/8)W 21 (knapsack capacity is 21)E (1.67 15/9)Fraction of Cinf, NF32inf, F36.750/1, F35.2812

Greedy for Knapsack – Criterion: RatioItemABCDEValue45111415Weight34789Ratio4/3 1.35/4 1.2511/7 1.5714/8 1.7515/9 1.67Reordered decreasing by ratio:Unbounded, fractionalPickedDDARemainingweight13( 21-8)5( 13-8)2( 5-3)Value: 14 14 4 32PickedDDFraction ofof DRemainingweight13( 21-8)5( 13-8)0( 5-5)Value: 14 14 5*(14/8) 36.750/1, not fractionalPickedDEARemainingweight1( 4-3)Value: 14 15 4 33Best available item now: C, weight of C: 7Remaining weight: 4Want to use all remaining space with afraction of D or C Value calculation:Remaining weight*(value/kg)D, E, C, A, BUnbounded, not fractional13( 21-8)W 21 (Knapsack capacity: 21)4( 13-9)0/1, fractionalPickedDEFraction ofRemainingweight4( 13-9)0( 4-4)13( 21-8)Value: 14 15 4*(11/7) 35.28C13

All four versions, VALUEItemABCDEValue45111415Weight34789Reordered decreasing by value:E (15 )D (14 )C (11 )E, D, C, B, AB (5 )E (15 )E (15 )D (14 )E (15 )A (4 )B (5 )0/1NFA (4 )infNFE (15 )E (15 )E (1.67 15/9)D (14 )W 21 (knapsack capacity is 21)Fraction of EinfFFraction of C0/1F14

Greedy for Knapsack – Criterion: ValueItemABCDEValue45111415Weight34789Reordered decreasing by value:W 21 (Knapsack capacity: 21)Best item: E, weight of E: 9Remaining weight: 3Want to use all remaining space with afraction of D or C Value calculation:Remaining weight*(value/kg)E, D, C, B, AUnbounded , not fractionalUnbounded, fractionalPickedEEAPickedEE1/3 of ERemainingweight12( 21-9)3( 12-9)0( 3-3)Remainingweight12( 21-9)3( 12-9)0 3(1/3)*9Value: 15 15 4 34Value: 15 15 (1/3)*15 350/1 , not fractionalPickedEDRemainingweight12( 21-9)4( 12-8)B0/1, fractionalPickedED4/7 of C0( 4-4)Remainingweight4( 12-8)0 4(4/7)*712( 21-9)Value: 15 14 5 34Value: 15 14 (4/7)*11 35.2815

Greedy may NOT find the optimumsolution for Unbounded and 0/1 Knapsack- Proof by counter example Goal: construct an Unbounded Knapsack instance where Greedy(with the ratio) does not give the optimal answer. Intuition: We want Greedy to pick only one item, when in fact twoother items can be picked and together give a higher value:––––Item A: 3kg, 5 total value 5Item B: 2kg (can fit 2), 3 total value 6Knapsack max weight: 4!!! You must double-check that Greedy would pick item A checkthe ratios: 5/3 3/2 (1.66 1.5). If item A had value 4, Greedy would also have picked B.Same example can be modified to work for 0/1 Knapsack:– Item A: 3kg, 5– Item B: 2kg, 3– Item C: 2kg, 3Item A ( 5, 3kg)Item B ( 3, 2kg)W 4, Greedy (Non-optimal)W 4, DP (Optimal)Item A ( 5, 3kg)Item B ( 3, 2kg)Item C ( 3, 2kg)W 4, GreedyW 4, DP:16

Weighted Interval Scheduling(a.k.a. Job Scheduling)17

Weighted Interval Scheduling(a.k.a. Job Scheduling)Problem - Version 1 - jobs with different valuesGiven n jobs where each job has a start time, finish time andvalue, (si,fi,vi) select a subset of them that do not overlap andgive the largest total value. What would be a greedy criterion? Greedy algorithm? (Is it optimal?)Problem - Version 2 - jobs with same value All jobs have the same value (e.g. 10).– The job value will be just a multiplication factor– Only start and finish time, (si,fi), will affect the solutionmaximize number of non-overlapping jobsWhat would be a greedy criterion?Greedy algorithm? (Is it optimal?)Which of the 2 versions is harder?Greedy gives an optimal solution to one of them. Canyou guess which one?E.g.:(start, end, value)(6, 8, 2)(2, 5, 6)(3, 11, 5)(5, 6, 3)(1, 4, 5)(4, 7, 2)E.g.:(start, end)(6, 8)(2, 5)(3, 11)(5, 6)(1, 4)(4, 7)18

Weighted Interval Scheduling(a.k.a. Job Scheduling)Preprocessing: Sort jobs in increasing order of their finish time (andgive them an ID for easy reference). Possible criteria:–––––Ratio: value/durationLargest valueShortest durationStarts firstFinishes last– Finishes first– Starts lastE.g.:(start, end, value)(6, 8, 2)(2, 5, 6)(3, 11, 5)(5, 6, 3)(1, 4, 5)(4, 7, 2)After preprocessing:JobId (start, end)1 (1, 4, 5 )2 (2, 5, 6 )3 (5, 6, 3 )4 (4, 7, 2 )5 (6, 8, 2 )6 (3, 11, 5 )19

Class work – Applying Greedy Both problem version Version 1:After preprocessing:JobId (start, end)Criterion: job that finishes first1 (1, 4, 5 ) - pickedalgorithm,2 (2, 5, 6 )3 (5, 6, 3 )-picked– Sort by finish time - O(NlgN)4 (4, 7, 2 )– Repeat as long as there are still jobs available - (Θ(N))5 (6, 8, 2 ) - picked Pick the one that finishes first, J, and6 (3, 11, 5 ) X Remove the ones it overlaps with - Go though all remaining jobs optimal or not (if not, can we build a counterexample?)– For VERSION 1 ( different values) – not optimal– For VERSION 2 (same value) – Yes, optimalVersion 2After preprocessing:JobId (start, end)1 (1, 4) - picked2 (2, 5)3 (5, 6)-picked4 (4, 7)5 (6, 8) - picked6 (3, 11) X20

Interval Scheduling Greedy Criteria Problem version: All jobs have the SAME value. maximize number of jobs you can pick.5186712 Criteria that gives optimal solution:– job that finishes first– job that starts last– (See book for proof if interested – proof bycontradiction, CLRS page 415) Criteria that gives non-optimal solution:––––Shortest durationLeast overlapsStarts firstFinishes last21

Summary and Counter Examples With values ( job (start, finish, value) ):– Greedy solution – none optimal– DP - optimal Without values (or same values) ( job (start, end) ):– Greedy solution – Some optimal, some not (based on criterion used) (CLRS proof at page 418, proof of Theorem 16.1) Which of the two versions is more general?––Is one a special case (or special instance) of the other?If you have a program to solve problems of one type, can you easily use it to solve problems of the other type?Which type should the program solve (with value, or without value)?Jobs with the same valueJobs with valuesExample showing that Greedy with largest valuedoes not give an optimal solution.9 15 10 8 9 6 7Example showing that Shortest durationDoes not give an optimal solution.512Greedy will pick the red job. Nothing else fits.Better (optimal): the 2 blue jobs.186712Greedy will pick the red job. Nothing else fits.Better (optimal): the 2 blue jobs.22

Huffman code23

Huffman code Application: file compression Example from CLRS:––––File with 100,000 characters.Characters: a,b,c,d,e,fFrequency in thousands (e.g. the frequency of b is 13000):Goal: binary encoding that requires less memory.abcdefFile size ord01011001111101110024

Huffman codes Internal nodes contain the sum of probabilities of the leavesin that subtree.Optimal prefix codeword tree(Huffman tree) – optimal encodingFixed-length codeword treea- 0b- 101c- 100d- 111e- 1101f- 1100Compute the number of bits needed for the whole file using each of these encodings.Number of bits in code45,000*1 13,000 * 3 12,000*3 16,000*3 9,000 * 4 5,000 * 4 224,000100,000 * 3 300,000(Images from CLRS.)25

Building the Huffman Tree1.2.Make ‘leaves’ with letters and their frequency and arrange them in increasing order offrequency.Repeat until there is only one tree:1.2.Create a new tree from the two leftmost trees (with the smallest frequencies) andPut it in its place (in increasing order of frequency).3. Label left/right branches with 0/1Encoding of char path from root to leaf that has that charTree property: Every internal node has two childrenSee book or lecture video for the step-by-step solution.In exam or hw, you must use this method. Make sure that you always put the smallest child node to the left.Frequency(thousands)abcdef451312169526

Glancing at implementation issues and options Good reference: https://www2.cs.duke.edu/csed/poop/huff/info/File Compression with Huffman coding - Practical Issues– Given an encoded file, how will you know when it ended? Typically files are stored by the OS in sizes that are multiples of a specific value, so eventhough your actual file takes 121 bits, on disk 128 bits are written and all that will be readwhen you open the file. You need to know that after 121 you are done.a) encode length of useful data in the file orb) need a new symbol to indicate end of file. Note that you must add this symbol (withcount 1) to your set of distinct symbols used in building the Huffman tree, because youmust be able to recognize it (decode it from bits into the symbol).File formatDecodinginfoUseful data– Given an encoded file, how will you know how to decode it? The encoding tree is not standard, but it depends on the given file Must record some information to know how to decode the file along with the file (at thebeginning) – Store the Huffman tree (0- inner node, 1-leaf, after 1 read 8 bits and decode tosymbol)– Store enough info to regenerate the tree (e.g. char and frequency pairs).ExtraBuild the tree efficiently– Using a heap: Heaps are efficient (lgN) for finding min,removing min, inserting new item– With heap: O(NlgN) With sort and reinsert (like on paper): O(N2)Using 2 sorted queues (https://en.wikipedia.org/wiki/Huffman coding)27

Greedy Algorithms Greedy algorithms do not always guarantee optimal solution.It depends on the problem. Difference between Greedy and Dynamic Programming:– In DP typically you solve all the problems and then make your choice.You will compute two or more answers for the current problem (entireproblem) and pick the best of those.– In greedy, you make the greedy choice and you are left with only oneproblem.Problem/Greedyoptimal or notGreedy gives optimal solutionGreedy does NOT give theoptimal solutionKnapsack- 0/1 fractional,- unbounded fractionalCriterion: value/weight ratio- 0/1 Not fractional- Unbounded not fractionalJob Scheduling- All jobs have the SAME VALUECriterion: job that finishes first- Jobs have different valuesHufmannPick the two trees with smallestweight.28

(unlimited number of each object) Can pick any object, any number of times. Bounded (limited number of each object) Can pick object i, at most c i times. (Not covered in this class) Typical version: 0/1 (only one of each object) Can either pick object i, or not pick it. All versions have:

Related Documents:

Bruksanvisning för bilstereo . Bruksanvisning for bilstereo . Instrukcja obsługi samochodowego odtwarzacza stereo . Operating Instructions for Car Stereo . 610-104 . SV . Bruksanvisning i original

10 tips och tricks för att lyckas med ert sap-projekt 20 SAPSANYTT 2/2015 De flesta projektledare känner säkert till Cobb’s paradox. Martin Cobb verkade som CIO för sekretariatet för Treasury Board of Canada 1995 då han ställde frågan

service i Norge och Finland drivs inom ramen för ett enskilt företag (NRK. 1 och Yleisradio), fin ns det i Sverige tre: Ett för tv (Sveriges Television , SVT ), ett för radio (Sveriges Radio , SR ) och ett för utbildnings program (Sveriges Utbildningsradio, UR, vilket till följd av sin begränsade storlek inte återfinns bland de 25 största

Hotell För hotell anges de tre klasserna A/B, C och D. Det betyder att den "normala" standarden C är acceptabel men att motiven för en högre standard är starka. Ljudklass C motsvarar de tidigare normkraven för hotell, ljudklass A/B motsvarar kraven för moderna hotell med hög standard och ljudklass D kan användas vid

LÄS NOGGRANT FÖLJANDE VILLKOR FÖR APPLE DEVELOPER PROGRAM LICENCE . Apple Developer Program License Agreement Syfte Du vill använda Apple-mjukvara (enligt definitionen nedan) för att utveckla en eller flera Applikationer (enligt definitionen nedan) för Apple-märkta produkter. . Applikationer som utvecklas för iOS-produkter, Apple .

Since the eld { also referred to as black-box optimization, gradient-free optimization, optimization without derivatives, simulation-based optimization and zeroth-order optimization { is now far too expansive for a single survey, we focus on methods for local optimization of continuous-valued, single-objective problems.

112 STEFAN PROBLEMS John van der Hoek §O. Introduction In 1899 STEFAN [1] posed the following problem: A heat conducting material occupies the space _co x 00 Initially (t 0), the liquid phase occupies _co x 0 at temperature TI 0 and the solid phase occupies 0 x 00 at temperature T2 O. It is required to determine

och krav. Maskinerna skriver ut upp till fyra tum breda etiketter med direkt termoteknik och termotransferteknik och är lämpliga för en lång rad användningsområden på vertikala marknader. TD-seriens professionella etikettskrivare för . skrivbordet. Brothers nya avancerade 4-tums etikettskrivare för skrivbordet är effektiva och enkla att