UNITE Ovrecdy Meothod and. Ayramic ‘Programming Grasecy Method: Gintedy methocl is used to solu athe eplinugalon problem Optimzakion problem: Problem roharch meguure man (on) min acdult - : i. * oplimisaitin problem omits of mulleple Aolulior’s % Solutlions thal Soilesty the gtven constraint lar) condi lion ave known a4 Feasible Soltilions : Among all feastble solulions a solutions which sality the | chyzelive alto is known aS optimal soluilton | | Algoatthm for Grveedy Method : | | Crveedy Method Carn) £ a ALYY] | feasible Ca) £ | Feewtble = Feastble unton (x); i velurn Feastble | Krop Sack: Contatner Loading) Knop Back always eapects lhe maninum pool: | Constratnt: Object weights swm should not exceed , the vapact of wontather ie. 2xtwi 2 seopactly Objedkive: man C2rxipi) profit should be rrantmum « ‘Example : objut® o> 1 2 3 A FS 6 F Profits Ps: 10 s Is 4 6 18 3 wulghisw: a 3 5 47 + w# ? | | | © scanned with OKEN Scannera a | >A bag ox knopsak is given capactty n and n olyech ave given + Cach obec has woe ght wi and profit pr Frackon of object 1s consi‘cleed as Xi (he)ozenize) » Of Sachon 15 | 1 thon put wwrilive object uinlo sack» When we place this frackon inlo the sak we fe wir! and pit nee 4 | mis Cdolal we'ght) D> obyect wan also be as trackions | 3 Plw + Proltt /wa'ght SS ie | ‘ Ghee |S ake one whith V's hating high Piw hat shoulel be Jake jor Kept first. total te Sb eS eth Bore ne \ OD. we HH ae te we 19-11 1y 9-12 19-428 6-873 3-178 = | Sik dolal objet vo include we represnt ab “1 4 if no objet wa included we represent wo sntvol = 1xQ+ 2/3 xBAIXTH OXFA IRE ALKA Xt 2 Q481S4O4 14H Ate IF AClolal weeght of bye) | 2ntPi= UX1OFE SHIRT A 6A IRIE TERS FOL AMV 311 S4 G1IGAS = 54 -GoC toll Polit obtained) © scanned with OKEN Scanner4 i | goat thm ) |e Algcatthm Crveedy Knap Sack (mn) e IP Cin] and the wlisn] conlatn the profit & N& wetght res? of the n object oaclered 4 Ul Such that PLéJIweiy >: pliiwlad \s- I on is the knapsack size and x Lien] is the golution vertex | jo ¢ \7- for 24 to ndo alty=o0; 8 Den; ie for @-1 to ndo jo £ ly. T€ Cwiqou) then break; 1a XCVT =F 5 Usu-wer] 13.9 up if Cie=n) then xCiJ= Uwe] ise] Job Sequencing with ckad lines | Feasible solution with maninwm proftt is aptinat solution for job v sequuenctg with clad UWhes | Constraint + Completing. jobs with in the ceaellines | objective: Senevaing Maximum Prof't [3 fo complete job one has to process the Job or a athlon. for one untt of dime. | |-> Feastble solulion er 3 problem 1s a subset of T at j al such that each job in this subject can be compleled by | | this deadline- | © scanned with OKEN ScannerExample: | Jobs Tre 3 oh Ts Jo Je Pofils 36 39 oF a IF 12 g Reaches 3 4 4 2 3 1 Vv | | ot 1m g BH 3Ch oe | BG ee et —~— as 3 30 (%4 > 31> k) > Stince one jeb van be processed fn a single mic - The olher Job has to be in its wating stale nlll the fob is Completed > % the wating tme and proce sting time should be | less thum or edyual to the dead line of the [em Ls when we have .timrtecl fob- slots and more jobs than we howe to select the Jobs such that the “ profrt i's mootimum - : Adgouithm Algoatthm IS Cdsjn) II The job axe ovdeved such that plil>ptad...>pln4 W{CiT & the ith job fn the opttinal solution j | Il Also at terminal ACTLije dl Tia leiek { dloJ=T fo] =o; Todt, kon For 9:1 40 ndo rk while Ud CT Crd ]>a0 (1 and © scanned with OKEN Scanner____ (d CTOI=¥) do ¥ =¥-15 1 CAT EyJ] ed Pe Joma (CJS) then { for ak lot Dstep-1 dot (qT = lq] | TCs ei; | Keke; 3 | | return k; | j Minimum Cost Spannting Tree st Spanning dace of a graph iS an undirected tree | Consisting of only those edge that are necessary to connect all the vertites in the original graph cA spanning tree has a prepesty that for aw per of vertices there exist only one path between -thim and the fnsevtton of an wdge oa Spanning tree form a wahue eye > No-of edges should be one ess than roof vertices (v-1) for Le: Gyanh Cv’ © ceo no-of vertices + 3) no of edges: 7% \ \ aS I \ a 1 @{ th \ Ye ON Spanning tree | o— ‘a 9 no of vertites -5 ho-of edges = S-1=y | > Spanning vee fsa graph of a gion graph hae as dhs —verliées without any cycles —> Wullipd goanniing trees ean be constructed trom one yaph that ty “melliple solutions for a problem So these ave feast solutions © scanned with OKEN Scanner> (n"?) numba of spanntng trees can be constructed ex: ay | | | | | | tee. there are two me thoes Ww prims algorithm (@) KruskalS algorithm These two | we greedy Example: Prima's Algor tum pick the minimum tost edge y 0 fo construed a Spanning tree accovel’ eu Hoof vertices in St<4 a No-of edges in ST -y-1=3 tnt) = 4"? =u? = 6ST’s fo solve the gin graph into minfmum cost spanning | as follows: rclh ods | (a) ‘The next edge should be minimum connect witty the allaeacly taken dye vertices » ng bo pins algorithm test -amd should: © scanned with OKEN Scanner@ . [fe * The oblatred tee fs te spannihg ] bee fl he minimum cost g Mgositiom: aAlgosithm prims(e, cost 5,4) Al (4) be an sidge of minimum cost in €; Min cost += cost CK, 1); TUN ks tC Jeeh; for @:=1 to ndo OF Ceost C1, Ade cost C0kI) Ahem rear CV J:245 Clse re Ci k; Neov [kI: = rca lJJ == 0 For (z= wo n-ido { kel JF be am incbe such thal nar £y'J40 fost Chnegr CFI] 1's minimum ; Gey FJ5 trad := nearly Ty; Near [jJ:+05 © scanned with OKEN ScannerFox k:=0 oe. 4 veux Cwsat [kJ 40) onrel CcostE ks New [k]:=j; j J utr (KIT> tal Ck, f)) then | | | Rebun — mincost 5 | Kruskals Algoaithm ae Wirt coat eelge should be picked von 1 10r / isoleded componaucd ca. | | | constyosnb: Cages shoulel be of minimum cost omel 10 o4 shoulel be formed }> Kruskals algor ttm dees nol consicler se edges vohith ‘orms a oyele @) Ww | FA @) © scanned with OKEN ScannerAdgoaithm | vAlgoxilham Kruskal Cé, cost ynyt ) ‘ | { for {21 lo n do parent [99-15 | = 0 5 mincont = 0.0, while (Pena) amd Cheap non wmply do j= find Cn) 5 ke find (W5 ik qj not equal k) thon { Teta c Gi. =u; 1 (hadev; menco 2min Corts cont Cuyvds union (bj | y i : if Cinot equal n-1) tn write ("No spanning tree) abe yeturn = minim cost ; | 5 | Optimal Storage on Tapes ' | 4 torage on apes i one of the application of the | optimal 8 Jape ° | Greedy utethod. The objective Ts to find -ity optimal vetrival | atme ov accesstng programs thal ave store on Tepe —> Qt us used in Aineling in short path | { | i | © scanned with OKEN ScannerRecord dongth ave arranged Cramp: 1 22 a3 16 20 9 S 10 vise oda: 1 3 5 6 10 IS 20 9 23 Ts 1 6 99 ie ey | 10) oe Ts 5 is aa > we have to avramge them on the p pes in ovde- T= 1 446 D4 C146 490) -3¢ T2= $4 (340) 4 (3410192) 241 MT 2 54 (O45) + (5415493) 58 act). SSAMI6E = 1 gg h 3 Shortest slongth Coy) Atint’mum dength = 28 Algoxithamn: Algorithm Storage (mn) : hong AUT 4“ n-noef programs # m- no. of programs T0 for fz1 to n do port ( pregiam Ton Tope J t= (ti) mod m © scanned with OKEN ScannerSingle Souvee Shoatest path : ¥ ijestras Algorithm a qrepn algorttam that Anes Rijkstia sigerithm Is hat finds lhe shovtesh path from @ lo all othey vertices in the graph ; DO wy a ‘ype of Giveedy Algorithm thal only works on woeighted heuwtng positive toedyhts | source verter | [fs d Lud > cont Cu,wr J oe ey us sown valor bys) = ys (101 18180 ) Sees Wee ¥ > dualinabion verre | 1,293 20 | 442)3 Das by 3 SS uy S58)3 96S a samp acu2d scost Ch4,2] Rataralion S0> 1loANS =2S ata de aln23) a | ae secs lyr] scostlirw dy | apy sTscomt lias) | co SAS cont lt, 6] =cost roars] © scanned with OKEN Scanner} i | | yo ow vy, wy Sued 2 8 eT “$0 45 1 0 = sc 4s 16 95 co “AS ys ty as co “ous 4s 18 as “ous 4S 10 as wo Sind dhe adjacency matric toy he gen gr? Consicler vi to be the source and choose the minimum antry \ in the vow | and owt the Column iin vohich & & that has 10 be visite next wo the node che matrix by alintnaabing verkex columns | present Hence that compute Find lle minimum in cach column -Now select the minum fom vesulling now . “Rypeal Me step Ae all te — yeylites are lovereel or sigh column 3 left © scanned with OKEN ScannerDynam Ic Frogrammng 3 Tht fda of cuynamit programming ts thus quile siopt: avor' calulaking the Same thsg _— rsaly by keeping a table of known result that frills up a cb instance ave Solved ~> Rynamit Programming on the eller hard is betlem-up technique. >on clgnami'e programming many deadton sequences moy he generated flowevey sequences contauinting sub- qplimal — sub- Sequucnce cannot be gpeimal ancl 40 will not be generated | Mut Sdage Graph | valli stage geeph a: (ve) ad a clivected gry fn whith Ake verlices ave por tioned into k>= path fiom source (5) to deslinalion 5 The cost of | Me sum ob the Costs ef the apr an the path The mull. stage praph probum bb thd a mirumum tost poth - min (¢ (pA) 4 cost rut) 4)) (ost (hj) > © scanned with OKEN ScannerVy Ve Ve a Pela |e] sis [ref fifa fie jm [| Stage vertex YoY cost (5,12) =0 tost Cy a) = | (ost (4110) = 2 cosk (yoni y= min f 9) + cost ot fests eae (yo) min fea 1 S4ah oy es cost C4) = (44) + c08F (ya) (C10) 4 cost Cy 10) Gt 342 Fe © scanned with OKEN Scannermin { caro) 4 cost (10) -> cost (3%) - } C(t 4 test Cant) . | {is te) > east (2) = (C26) 4 coat Ce) get Gand (@,%)4 C38) | airy > aR =F 1 os { | \ [> Cost (24)-(cyr%) + cost (34) | N4T = 16 cost Cys) = COS 4) 4 coat 63,3), COS 8) + e0st i) (4S, gaa) | 1 | | — > cost Gin) 2 [Ce Cnr) 4 cost@nd 5 C(ns xotl2>3)) 23 : . wert arusts \C Cid Acoat (24) 1 CLIC) 4 cst (5) 5 ora . ‘i ste verter £449) FF y FAG DIE = 16 Alt a) 22 qiryr)e% > ont — shortest poh. | A (33 )=10 A Ly to)> 12 for=3 Abu) 23 a (2,3)*6 A[3)6)= lo d (4 )lo)2 12> anothu shortest path “hae ae ‘2 paths © scanned with OKEN ScannerAll pus Shor test path | >> caltulale the dngih of the shortest path behvecn tach par of nodes | > The principle of eplimality apples: Ot Kk us the node { on the — hortest path. trom ° to / thin the part | of he poh from ito kK and the part tom k | to j must also be eptimal thal 1 shorter | | Jiyst eveale & aagjacency nutric tor the given guph a Copy lle ahove —-matréx — to-mattx@ whith will qe The cvect clislance between ‘nodes © > we have to perform N ftevalion after tlevaton k the mati 0 votll Ge you che debtance belo — necles voile. only 01,2,--.k) as inteemectate mo [es | > yt tle Hleratlion k we have 10 check fr cach pair | of nedes Ch) whethe oy not thee tatsle a pall — from iby peaing through node k- abjeckive : Shor test path b Example : fs CP «The taken qreph i a bicliection rr consideed as follows : > Adyauent modrtie should be | 1] 90 \ | L y a: 0 0 or 2] 6 3{ > © scanned with OKEN Scanner1 Soura veytex 5s consideyrd as intermedia le. ver lor Now fan’ ronsieley 4 an intermediate veylen a 0 yoo : od 4 6 | 6 0 2 a 6 02 | 2 70 3 ao cost (23) Can} Ln3) (2d G2) Cre7 | | a eam: 3 ® yar -6 | | | 46,2) Cat.) fa) C3agto) | he .. 3 mAb 13 a E ° | fs the optimal soluk’on for the > 20 ane gueph | fd Cus) fs) | uy 649 213 fx G23) oJ 6 24se . | 1 > aktiyfle min fait sae Te fds ak cyl} a Ceademr {a [aay , Ale A eT | omin f2, bent | | | | | © scanned with OKEN Scanner> by making b& Séyuum on Knap Sick voblom ; wned Ee knapsack problem be cblacra | so oe 7 le variable | pa * involves alelamninig be assignedl bit | The solukon . * J dectsion on vara yy H2---- An 13 to whith of te valu @ anc | ket Aly) be the value of am epimal + Sine colle prine’ple of cpoma Ssolulion 0 WY holds we | KNAP ( ijry) | obla'n | folm) = mart Sna Cm)? fa-itm von )4 Pry for ovbflaay fy) pido, | tity) smox Vier ty), fier Cyouot)4 or} P: fi lye) s FOO} oe can compute Aine St by. first computing St §(p,0 II P- Prt yyo-wr ti) ES' 3 Example: Conartig tht nap Sack tnslamce n= 3y CUO W? 105) =(28a)) (PrsPosPs) = (12,3) amet mee S* Flood}, se-$2)4 8! > $ (0,0) 1012.) 35 81 = € 3) C35)3 F = $100) C2) (2, GOI ST = Le Gu) CHO. Gat 8° +f lo) Cyr.) (23 C594) (616 C9) (0,43 Note that thepair (35) har beom shinhated from $? asa result of purging ault Started above © scanned with OKEN ScannerThe eee dales Person Problem: The Thaweldcng sales Person problem lo find a touy of mintnwm fost “the bavelbing sales person problem find applitation using thon vanity of svluabon: | Suppose we hawt 10 Youle a postal van to pick Fup mail from matl bores loreatedl at nelifferent sctes on ; mi Cm be used to represent the stlualion - One vertex Apresents post office from whith the postal van Stars aml to whith it return i The _fesnchon gO vey) wo tbe longi | cf om optimal sales person tour - dG. VED mn cus gCg¥-f 4K) OO Peep : we oblatn (Jor vgs) | 98) amin Foi a g¢1,8-8Y3O jes | porectecl graph amd edge longa matric C | | | | | T © 10 IF 20 i | | i 5 6 4 | 6 1 oO Y | & eo © scanned with OKEN Scanner~—. oy 9.02 $)? Cave $90€3,0) * CatG_ and 946) — wing VEY = Gs ag¢s.ph 9 (2sfay ers 4 C3 ifa4)- 1s 4 fy) 20 4 (arfa3iis g la S908 compulr gloss wtth (sl=2,741 5195 amar ds J Cy Land) min toy 4 903s Sud) » Cay 194 F335 25 9 Cr fauh)= mM fer igs $u4)s Cu gc BY -as 4 Cay {2,33} > rnin $eurtgeay 33), C49 (3435 )b23 9, Cty $253)43) eimin§ Ca rgq(2y fo3) 10919 fut 704 gad 23,43 smin Sas yoy dt #35 Keb N be the no-ef gers) that chawe to be tonpsted, pefore com be ustel 10 compute J Cnv-Say)-° The aaa of distinc sets 8 of size k rot inclucling tamd = | Ck) «Hence N= a Crek-1) Ce-4) = (ne? | \ | | | | | | | © scanned with OKEN ScannerGrady Me tho Muhod | Problem — | Constraint Objective | Oweedsy latme | Grvenddy (8? kre Sack Chjece wig Gunes “ Et feed Should wot " | prot shoul sre AW | he oblatned contatner, topacty Gyudy | Tob Complelang jobs i Soa mi eng [mB] enraing [manag | hott, cleccling monn profits cGn), cuad Wns | profit ‘aosunding | : onc : Minimum | Ati | eatmue | glint | ! aes at an 2 | cont at a |o@cloqe) ouleh | | \ selected sho | + i ) optimal i an a nate of swore in ‘cbr | on (a) auton wh | | one a 5) Siw Mirunwn | ehoy bat | | I" Syed path should | ath should tao) pe colecte |" pe oblainedt | | | | | © scanned with OKEN ScannerAyre Progaarnm tng veachicl snl —_—1- Probl | Constratnt objective | Feng ypunily Mullstage Fogo ihe = | Go yeach the nt a | | vetex te deattvaion wilh] coy gestinabow | OCM les coat : | \ | 6 All pis | chucelcn all [4 veach call pall. | shovtert pall postbilibe, to pith lew coxt | oln®) (ad ew coat | 7 = a TT oly knapsack oloesnot ‘end 0 a | oan) Capac man prod | pacity p | — Pag the pason alt porond should) ott) cal powon | Shou iM trawel with maar | fae aga fo out to all Ah | closlinactio ns || © scanned with OKEN Scannerand mame / Program 4 AN comes between greely muthod Dynamnt'e Aggra ment | | i) AL cach steps ube adeee fs delermened fascel ove cotutions of sulo propums » Greudy swathed | sat uacle Step, we quickly make Fa chotee that curverttly looks best it) Poeedy choite com be made | tt) Subd problums ae sowed | | fist Vefore solving futha fst: || Suo- problems it) Bottom up apprecel iwi) Gp ~ dewh approach 2 Com be stove mere iv) paneelly faater compln | simple: | | oo Abaut dunarate pregiaamentng Yawning follows prénetple of optima tty | Qn cynomue programm Alar will be Seqpumee 4 dlectstons at cury sage: “the deadfors ta fs taken al evry stage | solution avid tls "5 known ad ane aclected decisions should be stovedl be used OF Ryman Po should produce optimal prrkuple of pra ty « Bol aeeussive andl Pevalive funclons cam junthon 1S wed Won tee nel momortgalion and fleration function » metheel wee ACCURSIVE dada vs ts Jabulation “ruthad © scanned with OKEN Scar hod weed to stove | | nner