[go: up one dir, main page]
Scribd
Upload
50 views17 pages

18CS42 - Module-5

Uploaded by

Nikhil Djn
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF or read online on Scribd
50 views17 pages

18CS42 - Module-5

Uploaded by

Nikhil Djn
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF or read online on Scribd
You are on page 1/ 17
% Module 5 Back Tracks a Backtrackin vA 4g Adinsadte method of searching for th solubion fe o combinafersal problem 6 aioe 4 or algorsthwr. Seme of th problems that have 2xpm nical Aime complorty can be solved wring badkkracking wethed. The main ile. cA‘ create ry LAN AN xt 8 “Is = a ch Q 8, ee IE 2& shale as vo, ,Wr-- a Gren Wn Pm wk xe subsets of 09; chore n Pp osttive nu mers required to find all Igugn wt Se Stn ws. Consider a set S: 45,10, 12,13, 15,18} 4 ds30 ae re ee ear: Enitooldy Run. 5 = 5,10 15 <30 o S07 n= ay cdo 510,12 13 Go>3o0.hine , backbracks 59107127! Ye730 backtyacka Sto he Us5>30 NA deasible , backtrads 5,10 5,10,13 2e<30 . 510,138,105 33730 NF, backtracks co 5,0 | 5,10, 15 Selutiin Suoseds are TTS > Sr ,13 ' t2,12 Graph. Coloring tk 2 a pwhlenmr of colors tack verbix an graph tn duch a vsoy that no Moo acy acenb vertices have Zane color 4 yet ee colar) used. thy Blink £4 ots oid «1... Preblcas pre Xx ° cs M-colot < Color tt qivew graph wrth colors Roda, > Green. 9 ; Bhar -3 oiler tte given graph csitk colers Red), Green-a) Bhadi 3 (A @) oe Bes Handllonian cycdes Ik ws a path sn a undireckd graph that vasite zach vertix zxackly meeaud relums ls the starting vertex Find a Hanclbeutan cireuit easing lcceleteacking method the ctretke are - @ -b-e-$-d-c-0 | Branch aud Bound a It 2s a method od system ahical ly Searché for a solutim in state space bree. IL as used be dard Me optimal sollions. IL consists of eucraditng Lhe partial solution b addin aw en f¢ discarding ta ows that cannot posstbhy dead te ‘Basatle or Opeimo, colution basecl on aon Saad. ~ Lower bound for ruining alii prolly - Upper bound -for mar frtaa tien probleme Various problens can be solved are ~ knapsack problem - Travels salisucan prodlenr ; e “Assan mcut problems. Knapsack Problewr - - Solve tte following bknapsack problen usi branch and bouao os “th fe lowing tobe Capacity ey knepsack Ms to Iev hOdght Vodue t 4 to 2 bi ya 3 7 as 4 3 re Given, wr- 4% ,Vv,=40 , vifrors woly = 10 WO 24,Voe 42, Vafeos 4219 = 6 gr 5, Vgad Vs /40s zas|o=5 Lo,=12, VA eleo tole a4 Capacity sf bnapsack M=10 othe ubber' bound sa coled ated usm ube vt (M- wo) Wigs [Oz viz prdit of all chosen objects vo: vo ugh of all chosen cbjects slept - stem L-0 vi lw, 10 Wo, Veo, M-ws lo-0710 ub= O+10 A'10= 100 hepa - Vy |eo, = 6 , dim a (roth ikem ') Crottkouk dre 1) vo atte We wlo waght q item | tes v cpret J shot + v a 2 eee vee whe prdik dilemtty oe = 0o+0 M- ws 1O-G =G =o ub> Yor 6x6 = 26 M-wo2 10-0 =10 ub=>o4t0X6 = 60 slep, > adi fea, wfeoy es f Cuottly tina’) Cuoithoud itr 2) w= werght q ites +09 wos esto voeaght df dea ges > ++ =11 = O+h 2h Ve prot qd (Gua tw ve volo probe f atmatv + r+ ho ont 2 2 Mews 19-u sé Meu = lo-lis-l ube bos 6 x Se%0 No feasible Stepy- athens Cvoith alien 3) hor savight 5+ -q ve profit of abs 4v = gst = 65 M-us = 10-4 =1 ob: 65+1K 4 -6q steps - tBu £24 (wit oti 4) o> woeaght of vbw G+ to § B+q =1a ve prod of abut = 124+ Gd" + We 33 M-w =lo-12=72 NA Ae asibl Shab Spau Te as P.T.0, Va) dy = & (slo claw a) toe wlo wee, | ibaa + oo OF4u =y Vs wile prt stm 3s4v = O+4o0=40 Mod = 10-4 =6 Ub- Loree Gy =6y VelwSexe (wlo nti 4) v9: wlo weight Guy +e = 044-4 ve wlo pow of ttmy tv = O+65 M— v= to-de] ub=E54 1x0 =65 fees Qe Ue en teu Meese a alia knapaack — usith prdak 6s Hresignasnt Prob ber . Given on qe ond persons 3, —- co Lek ats coste g eos a . Te \ - 4 48 ah bE @ 4 Lb=a0 To Ie cles. Va Assign variout Aes b ob Lele ib —>1, cok © DTCs se cone = 3 a a 2.2 @o0 ae © wi a 4 -@Q*-3 ©. {2 -¢ | 1O- * Ot Ste dbetG Le b> coak = % : a 6 3@. a 5 @ () 4 ee stepy ~ Assign vartous 4s dec det or coals | Dek tu, costes = aa ae " 2 a © Me 7 * ‘ +6 -§ 44 -y ah 4 Lo=as~ Lb-B steps. Assigning feu te db y a | So, the chtwol solution os | a | A->2, b-s1, C33, d 54 Ce 2 He 4 | th 23 Peraara aradiguid jroo Person b assiqnsel jb Pewnmn ¢ assigned jes Persad assiguad jeu Droveling Salesnon Probl Crtereseted tn fincling db- _s- He luask st lour cz aun of Moo smalls distances fim tack th auwournt of work sn cons beuck! space Pree, Let us take advank Lhe ust Pbservations ~~ 4 + “t ~- “teu abuso slark fame a a corThe node b 2s wiadlid bedove mode c! Ey the tour, the first & dask tty remains other tutte muidktate nodes must be Te reduc sawe , dastinck. Apply branch aud bound algorithns to sdve “the TSP to oll owing avers “ b c d e S = (Ut8) + (y+eyr Cor) + C448) + (a+) by th-S 2. os 33 pS Sta Computing dower bound by comridering yarns edge q a 6 c (a,b) = .% ; A c 5. (4ta)t(ut 6) + (640) 4(a+8) +(444) ib: =: a. 33 (a,c) = Nek feasible (ad) = a 5 e d e s = (atu)4(4+e)+ (642) +(942)4(4+4) tbe 5. 69. ay (aeye a Gb ¢ d s= (1244) 4(ute)+ (ees +(e a0 244) e db-s 2. au. ol oy eee Computing — lower bound for edges dq nde b a b c doe oe (use) 4 (o4ur(ere)+ 48) +49) dbs & > 6% _ 32 z a iB ic d e (bd) = co owes (e42)4 (949) th= 3 . ae a4 = 34 (bee a b 52 (448) +(q4u)4 (se) -t6s48) 449) Le = — = +0 aD cas Lo wh at boacae ede thus te TsP path a haan coab 35 . (caney t+ C144

You might also like