Design § Analysis & aleorithens unity — &9D © Dynaeric Pro reaming + 4 DRA | | 2All-pairs Shartest paths, | > Single-Sovrce shertist Paths General weights ice String Edition | > Of knapsack |? Reliauillty Design | | Dynamic Programming ts an algorithen design wnathed -that | Gan be used when the” Solittion -16 a Problem ean be Viewed ag | the gesulr of Sequena, 6f decision. 5 Opttinal Soldtion 1s sequence of- decisions |> Tk is nat Possible fo all the Problems. other method is fo -hy all -the possible, decision Sequences | >in dynamic Prgramming on éplima Sequence af.decisions is | obtained by Principle 2 optimality, | > Principle of Opltmality — : | Principle of Splinsality slates -thet an Splimal sequerce.| has a Properly that hes ever Intlial shite & decisions are sthe ‘remeining decisions ‘ust satisfy an oplimal decision Sequence | with reper, ste result Prom She Bist decision. : > th greedy nrethod onl one decision Sequence, generatad.. >in Dynamic rend mari decision Sequences ave. Genera eee =e, sfe Wo 1s 2 eo eee alo 5 & 13 ee 4{& 8°49 6“the shovel path by sing dynamic Prog rernmingts l-o-4z | Balin greedy miathed the Shortest path is 1-2-3-U) | | Difference patween Dynamic Prgrmming y Greedy cae Dynamic Prygramming Gre wrathed | | | Dp ts used to obtain sptimum GM is alsp used —fo obtain gololion- Optimum Ssofation. [oP considers all possible : Bn Gy the, ophimem saldtion 1s | sequences in order-o ovtain Selected withoat revisin | the optimum soto Previously generated solSttons | | “there ts no special set of ee - | Beasible sel of soldtions ‘in ee ae imum sol ton is) | this wiethed sblained from aset of feasible & ts guarartteed shat PP In GM there is no Sach will generate aplirnal solition guarantee of efting | using Principle of oplionali ty opHmum Tsahdvors Dirtrodvetion te Dynamfc’ Prograrmin pe Steps for Dynamic Programming —Develop a raathemadical nokation that can eapress any S\itton & sub- Solotton Br the given protden | — Reevrsvely define the Value of an aptimal Soliton:ee eee ee ef. | —compite an aptinal solitiin Porn dampitid inPorinatiiny ~ By eng gotten up “technique Compile the value oP Spire | Solition: | Dynamic Programnting is Lased onthe. Principle oF apt | the principle, 67. crlimality slates thet fer an ptine| Sequence of decisions ar choices each Sebsequencs op | decisions | choices must also be 6Ptimal- - Dynamic Programming . —uSes Bottom up Approach. —Mbny Decision seqienes are, generated gal] over lapping | Sub-inilanes Qrve considered. . —Duplization of Solition is avoided, —splits all tts inpsls at every possible split Poirtt rather than a Particular Point: | — Pékzrmines the Optimal split prinls only abter-lying all | spht points. d “bong —There is no spedal sct-of Peasible solitions. | | Be considers all possible sequences in order to abtain | the optimal golstion. ; —PE uss Patnciple, of SPlimality te get all solctang | || of 1 knapsack problem: o-! knapsack problem Cable method) | Ovjedive~ —we are given 1 objects * 1 Xar-— Xn —with weight Wy )Wayb——Wo 8 ProRt Pi ,Prr>---Pn respialively, —the knapsack has Capacity y. — De an objert twtr wei gt bj is placed inthe knapsack, a Preit ps is | earned, =the objettive 4oFill the -knapseck so tral the otal prof eqmed. is maaimized ‘Manimizing the profit | Spine | gubjed to coment Srp ey xr 15 0 orl. | | Where, wi isthe weight of thither. | Lis the. probit of th tem. Oe ier ie ht inthe knapsack Sraproft of pr | Acoit we decide moto place ti inthe knapsack: | teen = weight cost ‘oke] i | “ a ae 30 | B 3 50 = 50 c 6 to= ID j Bor 20 ATE GHB=B Botsor 60 wee, S46=1I Nor psssible AD Stl=6 Boted = uothem Welght Cost ae ° @) Bee B46=9 SDH = 60 B+D Ste Sd+80= B30 Atstc SH3+6=1y Nor Possible, elke Shaq 3otsdteo= 160 AtCHD S4Gthel2 NoT Possible, BEctD 3464 Islo Not Passible PvBICt D SHB+6 Hele Not Possible. Of, knapsack Problem: ~ ve are n-objecls § knapsack: The objetti has aweight wet 14 f 9, i Q end ob the bag. fim greedy wrathod the xf —iLaCilet when objerh is placed th beg — T£ xCqeo When ro abject s placed tn he Solation to’ the kn, problem a0 lcined by making Sequence of decisions on %,%.-—40 =the decision on Varlable x01] involves determine hich oPthe values 0 Gol. —The decisions ate reas in arder Aniknj-—-& —the decision of ulmi) has 2. possible states Wy ined The Capacity remaining tn knapsack m and no Profit is occurs. CID Anal the capacity Yemairing in lerapsack 1s meh & PAL Pts occurs: ~ 8 Is clear tbat the Yemeining de eigions of Xn-trhn-2-—y most be ophonad optimal with vespéctto the Problem slate Tesuling an vin! fr lmde= manf in. (on), Prealin-ton) +Pr} ~ Generally Fity) = max £6. Cy) Ppa (yew -t pit ~ Brim) Can be Solved by begining wih, Krowsbedge, faye.for all 4 values: -tilp=- oF yxo A . - nes ave Using order ct Sie EP Cys) Ys tohere, peal ~ Loch member of Sits pair (Pie) Where Pfs) wey — note that 5% foyer -be Can Compube git! from an ~ stl can be Compated by merging atx gush , where 31-{lnw/Cp- Pig =i) Est Od e U o SV f sia lorntydt Domains Rules - th) When genzrating Sf! we can disowd all the pairs Cry) with wy 7m. ud gitostains Pairs Cpp isp § CPx with Properly py ty cetatel shavtest pathieY Post required cectsin righest inden. intermediate Vertea k. a a ane this deasion %s made +o shevlest path j'4o'k' k-to§ getng through vertex «kel aE CD te vepraseaib the length of shortest Pact Fem ie) getng -lo no yerlea of Ihe rs . y| zlAlide Mf min CAR CyE sah (kph cook UD} A= cost (hi) : ak tan be Calalated by teonden AlaiPeAl -- the shorkesk path from ‘iteg geing theo gh No intermediate, verter vk. ARg ) Aki =n : By Combining we ge aka ‘d= min Ll ket ke De min LG wy eatCegre ah Codd ~All_pavs shortest paths: cost lipo LDEE cost Cijl=o Cty) ¢e Shotesk pact, from ito j val a Aete,jerin [mince ci AME tost Gh we ap ~ Algor. Al paths (cost ai) t If west Ci: 1s the ost adjacent wialvin of grhs widthn nvettes A(ysJ is the cost of. Shortest Wpath from verter He verben J UL cosk Crgleo, 7 hes bly Hen. for. izt ton for je = ton do ati ide cost GD aH Il opy CastACijI= ost ij] -for ke1-on do -for i=! ton for jel4on AC Jde min CAC ACHE ACD q os BCnie mingled 1 ACIDE LD) = min (0)04+0)=0 TE AUDemin(a lud/AU0+ ALDD= (eu roaud=4 E35 aledeminerlid, 410+ AUBd= (more ter Fa (ai= min (alana Captaluidi= min (6)640)—6 he 4&8) = pin (lad 4 La 4 aud) emin (0/644) =0 A (ape min (ALT) ACAD ACY) = min Cay eg yer te} Jel Alsi)= min (4 (3,) 14(30) alg) =min (33+8)=3 vis demin (43,0) AB Dra Liad=emin (ot O=4 Afs:3)= min (asda G+anD = MiN(Co0, 341) =o \ t » 3 wet foaqau 2/6 0 2 3l3 4 of ker Ary De mio Ca CD) AL0d +AC2iD) } Zz min (0, U+46)=d jee jee AOD = min Ca yD. ALD +a dD = Min yto)=y A> GrQemin (46.0, H+ AGT)=min (unt —6 ter jet A*LaiD = min (ata, alappacail= min (6, ores jez es Aa Je min (412.2) AC a2) 4-402,%) = (o4jote)ma 42Ca,3) = min (48:3) + 402+ 462,35) mM wart) 2Bfeaidel ar fipe AeGiT= min Go Cad,a Gd, AC aid amin (3,146)=3 n2(3,.9 =min(AC3,24 ada @aD = Min (7 40)=3 1>(313) = Min Ca (3,307 4 3.2) +4A(QBYD? =min (omta)yed Aa’ Chile [: % 76 rf{6 ° 0 kes ciate a | fet jer #3 Cue min (a0), A612) aC ee = min (6, 6t3)=? ee Ad(idemin (4 61,0) AEA BD = Min (4) 6e=Y 28 (isle min (aC) ,4 (13)44 G3) = min G, ét0)=6 ter FY pt Gagezmin (alan) Alastor , emint 6243S AB( 2a) = Min (A (a, AC 2:3) 4 4(3,2)) e Min (0, ati)=9 43(a3) = min (4 (213)! 4,3) 4038) = Min (aH) =d. toa El 43 (3,eminle (3:08, a3) +ACaiD= min (3,043) <3 43 (aad= min (4 (3:2) Al313)+ 4(3D= mins 04029 lels3x) al 3) +A(3)3) = 2 A3(3:3) = in {2 - ! 4 woo- Ife 4 3/3 + ©i | { | | OBST Terminology tn Trees | re oF One © More nodes i ‘Such that there Ww Specialty deqvee node Calied ROOT.) and remaining nodes are partitioned Grito n zo disjoine gers Tr, Tn , Where each oF these sehs ica tree | the sets ave catted “Subtrees OF WOK PTREEic A.trecisa finire Se! & | | | | | DEGREE OF NoORE:- the novor Sub trecS OF Node 7S | Caled. deqree OF node. LEAF (op TERMIMALs:- Node with re deqree are. called | Terminal (on leat node ‘Otherwise (>!) caited i i | | i | | | i j | | i | | | | | | | Non Terminals (ot) NON leat Nodes. CHLLDRE Ma The YOot Bedes OF aubtrees node yx are the children OF X PRRENTi-~ NODE x iS the. parent oF at's omidven | as ent thildven of BD are H.31T And -the parent o children of the Same parent ave cated giblings: - Hid.gare siblings. DEGREE OF TREE:~ Degree ora tree 1S the martin un degree of the nodes in the tee- ANCESTORS :— The ancestors OF G NOdE Ore eailad | +he noded ‘along athe-path from root to node. LEVELS- The evel of A Node is detined by initially anand Letting the voot be at tevel one: +Hqht (or Depthi—- ze is defined “i be the MAMaA) wn tevel of Any node in the tree. “|] FORESTi— “It iS the Set oF disjoine trees (N20) BINARY TREES:- Fintte ger of nodes that ether | empty tor) “consist of Toot and two dtsjoine binary trees Called Lett and xight subtrecs. 2 Any node can have atmate two childvens ig there % no node with Freater than wo childrens “YN | Shewed leet Binary Tree Complete binary Shewed wight are Binary tree 5 Fully binary tree [ Kis deprb roto NO-OF node Oo a _ Dyr-t BINPRY SEARCH TREE ] — aoe ae A Binary Search tree T ts binary twee ether it 7s €ach node in, the, tve.€ contod n an identitier | emp . “f fo lewing land t€ (s nor empty, then it Satisfy. the Properties. 1. All identifiers in the left Subtree oF T Ave less-than the identifier in or node T or lane all fdentifier Inthe Riqne Sublree oF T ave Gea shan the tdemtifier tn -the woot node “T” 3. Left and Right gubtree OF the T OS also binary | Search Tree & + | qe All the identifiers axe differentee qeneval, ne adentitier to be Searches Apr | coithn dtHerent Wrequency (ow Probabilfty . e Lee US Assume thar Qiven Set to Adentitiers FO, Aa... An } With ANZArZaaZ24-- Gn. * let @t) be propanitity. OF thar identtiter to being, Searched. for tn such that | QAXL Ata] OIL assume Agee and Ona : =o DOU) tS probability OF AN cinsuccesetul search, | OLIZn- >. | DD pe) + satt)= ‘Zien O4ien OBST | CAN The OBST -Or AI,Qs,..+,An are must, xnown about lot] #70 ObtGIN the cost functton by Binary earch trees. IE ts useful alot a special node In place of every. empty, | Subwee I seorth tree Such nodes are eaed. | | Externas nodes- | jr Fo Binary -wee vepresene n Identitier. willbe exvactls pay external nodes. © Every Znternal Node, vepresent a pofnt where | Successful arth = may terminal. je Every. External mode represent @ point where. | 1 unsuccessful, Search may terminate : | 1 | S then cthere. eit n anternal modes wepresent- by oO then extemal nal nodes mepresene by |To determine On ddentifiey X fs presene a binary ree, Search wee x 1S Compared with wor e Te X I$ less than adenti-ter inthe root then Starch Continue in the lett subtree - : «Tf 4% 18 equal to Iden-tter 1 THE DOr, Search | terminate sucesctul otherotge S€Arth continues | tn the Aight sustec. cn 5 a oS ic | 6 go O@ | Binary Tree. Binoy Tree - | Mota BeT | for .qiven Ser of Tdentifiers , we CAN exeare dierent | Bese ar) Gen “2 (Gb Gi = @# €do, tor, TF, ane, while) => ¢1 i | 12,3, 48 co |'-2.2,3,8 Comparisiong 1,418.4 eompartsons- | Ore require to idenit-+ty, sequired to find the tdenthfer |+or ,do, tnt tH white fox ,d0 cobt le, iD by te PH 2tRtarh — a ————_ *F | | | |ee arch terminates ot Internal of Buccessfu) Se tt | node- ar level p, Then. £ Heraxion OF while lop | needed . : | the External cost conmbibution fiom the 2nternal - Mode or ay. tn pit) # tevel (Qi) » URSUCCESStUl Starch terminal ab excitrnal Node he ‘demtifier not in 8st May’ be -PartftOn wto, ob) equiualance Chacg-e? Eo ©niafn atl tdentitrer x such that xZQr Ef contain all the ident-rer x such that atexzQia! oo ; io | En eomtoin all the identitier x guch -that Op | oe ddentHier in att¥ereo Er Search terminate at attirent | externat- nodes. : . | + DF the foilune Rode for Er at level L-tnen ony sy | | ‘heration oF chile loop are made COst combibution e& external node | | | | 4 @t1) * (level Ler) -1) Expected Cost OF BST = FF prix tevet tar) +37 ott dleverle; -y) reign oLttn i { On} to be binary cearcy |Et: (1 A205)» lde Th, stop) piy=t)= 7 Possible BeS-T:- | cay &) | e- | (A) pede reae dea) thlaayedes | (lb) B17 ce elt @) wit tel eit = I tad etedy “tree bis. optimal PUiy= OS PLA) Ol plg)=0.05 BlOd= Pts — Ql2)=00S Q)=0-05 O61)= Oy ltals 265 . . |e eg fers bs C iS OphmaQl BST 5, HS aa Gis 205 ' . Ice) = Ie_ Dynawte PrOTEOG * By applying dynamic programming OBST consistent Guch trees with sequence OF decisions ANd by principle OF optimality... a | sAny node a; can be assigned to wot node. OF the | trees Te we cheose A, hen ste 1s clear thar the. ‘rterna] ° U NOdes| nodes ov rae Ay; OS well as external Eo, Eic-+ Exiy AE tMe Lett gubtree £ Of woot 2 the remaining nodes are 9h gubtree COgg ON) LER EK) Cost CL)= JU Pt) xlevellayyy Tr act ietewer te1)-1) 12 145 og tek Cost (R= ST. Pere tevellar) + met) ¥(tevel LET )-1) Kaiten K2ten Weighr of Tree. Liz). © WLIT) tS 40 represent sum @ne sy” (OL er ey S=itt » Expected Cost of | SCAICh tte xr Y pts) 4 coselh) + COSECR aK f (0, Bout Ui, 9) eat ft 1S Optimal then expected cose tg minimum « COStLL) + cose tej tS must be minimum edt we ove using ¢€ CET) to represent the cose oF an OBST tyy OMOIN Ay )-~ Az and ey. Er Then cost (L) =Cost (O/K-1) FT cosrir)= ¢(%in) K must be choosen such -that- | cloind= PEBIFCLO KE ELE NIFOLO/K-N4 WiKi | roinimure Te we C(O iN) = min / eee tLken WOK) TN CKO) | qeneas , al | 7 | clits). min {otis Kl) teks TIFPCR) teolt Rae), tener C6 f =min ; ; . en PC Ch hws etn) tithes ) , wir) = -pcy+Qt7) +0-Cf, 7-1) For sowing ClO) first Compbbe@ all CCf, 7) suchtnat g- T t=) ectil=o wt ach) TITS Bon oy ty COMPULE the moO RUT) oF each tree tty” OBST 1S constructed trom “these RUN 7) [e The yalue rli,y) iS the uatue of &K that minim 6CCUF) \ : ; | Eust i vee nat and (Ar, A203 (04 js (old, TH Int, whe ) E ple g)= (8, 8b). -@ CO;t) = (2,811.1) PQ are, multiplied. Ane a i | Anitialy we have weti)= @¢tr) ~ tlifd=o0 THsne Algorithm tov OBST (P,Q 1A) oe i Y Given H+ Identifiers 0 La2z03;.~ an’ and probability: ect) and oe) re LirJD ts the cost OF OBST ts tndex. PY -Qyyj 1 OY Te ALO Conetuces RCUT) col I) ts weight o¢ T(4,7) dor 120 +0 nl ‘ wliAl= QLD RI Deo. eChtJeo-oll ne} 4 Optional Tree cotton ene node wo (hitl) = Qerds Qt)? elit RLaid= fel CChit)s OCf)+ @ Ltt secre) y Oo LDeNJ>= OLN -C ln njs 0-0. 8 Loin] <0 for mea to NI -tind OBST wt th. m nodes “for t=O t0 n-m 1 ; | jJsirm | widewlh dei rel ears \ Ee volue Cin wange RUIN) cazectiy)) the | minwtse f Ot M)4CC 5) | hy) = went) te Chb-laecuy | | O45) sk | | | | i i | | | wortte CeLOin),wloind loin) )N=4 GNd OF,02 G3 ag do, If, Integer, while ees) = (388, bt) O04) = 02:31Lb1) Pr@are muttpled by 16 or Our conutentence . WLOOJ=> wl i}=3 wlrar2Js wladj-) wlaa] = RLO,0J=0O Riso R fir) 20 R(3:3}=D RLBBI]=0 eCoOJ=0 cfit=O cfrz2)s0 CL8BJ=0 C33) 20 Wlortd=g MLLaet wlrsjes wlsitles R Lowel, @Cuaje2 RR Laasss ROS 4IRE elotj=g Clr2y=1 ¢ (28) 3 e[s)=3 | WLOrJ=12 wlrygjeq wlr ds R LOt! Rigs > & t214)23 © Cowy9 ¢ Lis} ¢ L214)=3 w Loddels w lied ]ett R LOgj=2 Re tray=2 C lowgjes e@af4]=19 | wo toa] ato Rtod)so eto.4} +32 PCI=3,-Pld=8, PLBI=1, PL4I=) Qlod=2, @ts3, MIst, @8)=1,@ Adar | oo wtgia) sO Lol=2 RUS] =0 | elooj=o Ole ti = @QLOl+QLiIep(i] =, 2te49 Rtowd=! [Ge Cords @tol+@ lid+Pliy = 2484358 =@. | eee beeen en eeeENNne tC eeEIEEENE eeefe @) f=} wthl=gt=3 RLiYe0 @thilso : wir}: QUIFQ (2]¢Plrz1 > Stites 7 fer wle2]=@ L2J=1 R leeds o @ f2r27=0 w L2rd)= QC 2+ CC8TFPLad = tata yng R Lands 3 C Lawes: fea | w{ 83]=@[37 =! R683] = 0 2 LR3)]<0 i Cals Qls]+QCe}x Pla) aittey RL3b)z4 C Lai4)e3 het wl4. 4) =QC4] =1 el4ia]=0 RCA] =0 -J= tem =0F252. ig idl zl J (ord) = wLlorrt PLO) e@f2] = S4stt sta |roi Hg = ZL4Rtt,2o K= ROW] 444 J Kel toe £ ten on * tet fae mintmt ge. {¢@o) te Cryo) 4 gen Onn A= minimise cose is C118) Clo#)+ ef2j2) - Ke! Clorsj= wloird+ e010) +¢ (112) * 124047219 Tloajat J=itmsito<3 wlth s)swlt,24 P(387+O03) “TRUM LEQ wlr3]=4 Ke RLU2]442R1 213] ~£aL8 ter 6 Loidteig ds O48 =3. oa C0274 C387 e429 27 422 minim ge. K=2—> minimum Cla) WLS] FeLn Jee £213) = Qtot gain Clade =2 Ptozg=2 jeitmertr =4 ola) =wlr3y+plaje@lay B B4ttl =o 2 4) 25 B12 (2,3)720zR03 4) a o4ea 223. € (2:2J+C(3 14) zot+328. ho 4 0 (263746 [4,4] = 31523 ba3 K=3 Cle: 4)= wla,s]ee (2)4 E34) = 540s = 8 fr 4]a3. M=3 feo Jes 0. 3]= olo.2] +P 13] x04) " lodteths 4 wlosl= (4 KR L027 2O2RC1,3] 42440 £=21,0 (oo) +03) 2Otle =yr 22,0 (OI) 10623) = p43 21) tar, Ke Clows)= wlos)t clot]+el2,37 | | | | | || ‘wl | = 44843 =25 s[O3J>2 = Wlh3j+Pl4y taQra) = atletstl RR 3] ete ela, 47 . 24h4 3 2 eltntace a) = OtR zg 2=8 =cCl2) te03 4) = 148 =10- Ker Clu 4sjawltes)tolut}ee Ca,a7 FUFO4+8 =19 a[t4J-K2. for m=4- f=o- jae: wolo.4)s cOlOsItPLalearay = L444) =16, / K= ROB) 2 Le R147 Bean £=2 5 cCOs tel 4a)= g+t =to, . ee os 4)t clo i+clr.4) = Otter ey v0, 4Jsa fe ———= do Jf. Integer eabtle- i3 © 4 4 ‘N ‘ ~ Tr Kel kJ (0.4 )=32 RCOM) => Tot Kee aN Tout /\ /\ = Too Ty) ayn Taye /® Keg. T3130 Tat PO°OF intemal nodes =a Cost OF binary gearth tree CCO14) =32. Root oF binary gearch ee Pp C0,4) ao 3 4ene A munistaqe araph G=(v,€) 1s a directed Qraph in whtch the vertices are partitioned fnto K22 dijoine Sets VE, 1Z1LK. Im Adattton rif (aw) ts an edge in €, then uelle and Ve Ure; Tor Some f,) 2k. the gets Vi and We ave uch thar twil= Ivyl=t. lee sand t, vespectuely, be the Werices in Vy and Uy. The vertex § t§ the gource. and t the Stnk. let cbt J) be the cose oF edge tts). | | The 0S oF O path from ¢ to tfs the sum OF the costs | OF tne edges on the path: The mutifSinge qraph Problem ts to tind GQ minimum + Coste constaine on &, every path fom Sto € Store tn singe &, Qoes to SAGE 2, then to Stoqe 3, then to Singe 4 | and uo oy, and eventually terminates in Stage K+ A mintmam-cose & to + path 18 tndtcated by the broken edqesé # dynamfe programming formulation for K-stage groph, problex Is obtained by dtrst noticing what every Ctoe | Path ig the vesutt of A Sequente of K-2 decistons . The jth dedsion involves determining which Uertex in OF optimality hold&- let pli) be A minimum -Cose Path rom verter f in Ve tO Verter t+ tet cose L3,J) be the cost oF 4nts path. Then, using the toward Opproach , we. obtain cost (9,5) = min, fees teu, fopee | | Since, cOseC HNN = ClLLO TE PLep|e€ and wae tn-1ya | | sA)* cose litt, gy} | “| wo itd Jey EE. may be sowed tor cose (1,8) by Fire | | computing eos (K-28 7) for all Je Uy, sthen eOue-LK-3,5) for all Je Vyg.g , and 40 ON, ONd nally eost (1,9). | Muvistage: Graph: Vs on | ut ~ oe | | | | i | | | i | f° | | | | * The multistage Fraph 1s a directed qraph 4 Should: hove more than 2 gages hE, KER K- norot Stages - t- present staqe + | THE. NOrOP Adjacent Scr s We. Greater than 2 KeeOT Noor dedstong 46 k- >. | NOrOb stages ts K- © To Find tne min cose tom source to destination | Path $ -eose (4,5) = minge Ch g)tcose (fti2) where belongs to Vey, | halts edge PRED tn Graph fox laste decision. COSE CO K-17) Seog (5,4) (3,4) belongs to edge. | COSECK-1,5 Jn Uct edge cost C2, 3) at ie 6 cost (36) Be ue 6s « me eta & ) + = ECB) teose (act) = aes ©(318) ceose (3.8) . x * cose (2,3) 5q d (213) =6, (Ue Edge cost (2,4) else) tose le) = aAtT jteu, =6:48 =min {ead feos 6301) we tag | el4,e) FCOOE 0318) = ae * Coste C2,4)=t¢ 4(2,4)=8. cost (21 >) ‘ OC S6) 4 cnr (8.6) ratty IG V3 =6r 3 = min [ee FCose (3). US = 16 | €CF8) tense (3,8) — ett se i “COS (215) 215 d(2s)=6 eose (3,6) 2 (ClEiT) $COSELHQ) = 644 >10 LEN, = 4,10, = rin [steno *OSt (4,10) = 542274 Clb MW tcesecay - At SK COSE (3.6) = 27 a03:6)=10 cost fst) ECA) COSC (419) = 444 28 | a min 7 CCMO) tose (4,0) = BALES LOY = Gio, = MN { Me COUN geoce tant) =o “ COs C307) =S5 de3,1) =10cost (3.8) eCRA) tCOLE L4G) Eo Lev = mt “ on 1 CBO) t COLE C4, 10) = Str =7 CCB) ¢ core C4rt) = be sey we COSE (2.8) =7 = ee d €3.8)=10 es cin _ min | CC4Qri2) 4 cost CF 112) CCQ 12) fe ea COSE (4 q)= 4h eee) cost (4,10) PEt = min q CLIO1ID I COS (5412) =C(tOrt2) 22 CSE C4, O1=2, cost (4,11) LED emtin fe(urmrdtcore (6112) = ecthin) = “” cose (4,01) =o ed(fij) ts vame of £ whtth min eff s)teose Cea, 2) uw Vs Vs, Va vs 1 mm Cao Vos dtuvi)sdtrt) 22 chom-the Fiqure- Nas dla) =dt2i2) 27 4-229 “as dC3ig)= d (81) +10 g-TsD | Ng sth 1-103 | poh 18 1n2 T= O-1 tO-Ie a> | Atotrgtra=le.Rau i Ravietting “Salesperson probler): | [et Ge (u,€) be a dlvected graph uwtth edge costs | ine Vortabte cli is defined such-that cijso for all a <1,4>0€ tet lvl =n and ascui and j and Ci = PA>t. A tour of & ig a divected simple cycle th | fndudes every Vertet in vu. whe cost of a tour | [tne sum ob the “pst of tne edges on *he *our. the raveiting Sales person problem ts to ind a tour ot, | Umntfimuny Cost. athe tour ts tO be aA Simple path, [starts and ends at vertex | every Our consists lon edge tor some Kk EVRY and a poh FO} Mertex K.to vertex | athe path fom vertex & *0 yi WH Bey : Meytex | qoes rrough each verte tne. t% IS easy t0 See that % the tour Is opera ma), nen she perth from K to} must be A Shprtest wtb t ‘posts ghirg rough atl vertices length of a shorts ‘| ||poth- skating ob Wertex % grirg Hmrough all uertice any s, ond scorminerfing vertex |. the punctton _$13) is Ahe length of an -Optirnal a al pm “whe pandpal of optimal —— iqciv— fry Ye Fouows hour: F OF | gu, y Lae min bend CNY ~neayy wml | | Generaltxing 69 20), we cotdin (fori ¢s) | | | gts) = fo Ley tas 574) wry | | | t. we Equarton 5.1 can be Solved tor 9 tuv—1t4) Fenow Ck Lk) or ati chiices of K- “the g wales | | can be obeckned by “seg C521). cleasly, gU,W= a, |_ a A , laien. hence, we can use (5:21) 40 Cbtcin oO, for aS oF Site 1 Then we con Obecin glis) tors | a so 8n. when 1s] 4N-ly the Values | ey Is) = 2, Or us ana 3 gor which 9s) 1S Needed are sudhthett | tet ¢s, and tes. | | | | | | ter, S223 | 1o 1s 20 i v i) | cnt 9125314), loutasaae minfeet EB ale 9 a w | Bere cen ly eee) (ee ee Ga | | = 10425 =35~ OE SG) | | i 2 164755 UO Dd | | = 20423243 | | = |g (2,23K8 Lin | Coax 903, i4¥), oa | seay Co £90443) = was =257 | glace) = win 5 cua *9 (2) $4y) S718 23) PHY Cee gcus}2y) = 2+ 132257 | Gey (9(4 82134) = i ae 48%) = gaige23 a + 903,224) = qaies 27 | o) Sd | | g(a,fug)s mio § Cyr Ce 2 a(t) yey 2 1249720 gli, d= Gt = Sun 9 (4/283) = — Bard 23,8 / arbald Wud ] a(n supe ee pense) |Cap +902 6) aestayeste rz 8 B os 0 tg 9S®) 2, e 9 (2,934) = Qabele 5 (3,393) = 9 fan *9 o,8) a y 1BASatd g Ct 234) = TEN C349) #2 g (483,44) > TEE ASA EY 9 64,834 = 744,334) 93 Shortest patfig 2 -Y-3-) te hi tength A ep 3 te Bs-: — vente &2) fy iO) Back TRACKING ae ye VE par “Ha eneral method : Many prodems — ceardiing for set qf solutions Cor) Searching cor pptimal solution satisfy some constraints con be successfully Solved by using bac ‘tracking. &n toany applications af bacle ‘tracking method -the solution is expressed og.'n! tuples RG ha, Ag yore selected from finite set Si The problems are: solved Hite ia Any where by! is by finding . one vector chat manimize the cfunction. The mar problems solve using back tracing ertgyirre thot ott Soluton salsty a complea set @ constraints: Por any problem these * constraints ae vided +0 te! Q categories « ‘ “ ~explicity Constrants- iy “Amplicity conttrolints « abot _vestrtclg eapltcrty constadinG + these ore “he mules ; to) taken values. for given eet oh each Ct) Due wy dG orm Ss Ut ne expiaty constraints deptnek on particalan. pl ery being solved “AU the tuples yutant of pal goefies the expliciby constrainta dedine a possiblesolukon pace. fas "> for 4 Q problem, explictty constraints are sem sy Solution Space for H@ problem ane CX) ,%,%3 4) Cy218,u) (243,84) C3, 24) C411, 2,3) C1274, 3) C2174, 3) Ct) C4245, 3) (113,2,4) G44, 1,3) (Samuraos) C4 ajay (34,2) Casa” C3, 1,4,2) (413, 2 CH4 2737 C3, C84,2419 (47> 3,1) CUM ay (2M 18,5 Cay 473,251) 28: OD tren 1 Quene — pablem u stale Space. Wee are used in PFS te; Numbering. We roof leaf nodes & ulszy a Yotal roof possible solutions in leaf nodes ule ap CD Chr du) C2, 2,49 Cau) Cay@ pati) thee are 4 elements ‘wo sum of subset problern EAL) For variable size. vepresentation ‘yi! e values fon 1 40 Y. for fined sized -represen tation ay values ye either 6 or 1. Solution space for sum of Subset problem (variable size) AOE ony, (aay Try Leap Lemay Loy Bey trasay Sat Way Via, Lay tway Lr 3,u4 Vana y Solution space for ttued Sze ~representation in sun of suboset problen, foro,o,oy {yt,oy04 Loo} SCOR Lr0,0,0% TUE 0F LHW, Lory {O1,0,04 Lueery Lattoy Lanny {o,o,1,07 Lotsey Anonry [o,0,0,14 Cd Implicity constsain te + o Trnplici Ly constraints are rules ‘that dekexming which of -the ples te sol space sabity the criteria function + + Smplicity constraints describes the way ip which ag must related to each other."The back traiking algortlhnn cletennine solution by ayctemottcalty Searching solutton space. + the searching is provided by tree Organization for Solution space. yy ~ Queen, problem, "yinaes are numloered os in des Coepth Past Search) +n=queen problem is generalization’ of queen problem. +In N-queen problem , n-queens. are placed on a chess board, *No two queens axe th same wow Same column, Saree diagonal . * The solution space consists OP nj, pewnutattons n-tuples+ “For Yy-gueen problem the total novo posstble folutions is al s24, she edger are labelled by possible values of ati) . The eclqes from — level-) tO tewel-2 nodes ane Specify she value op Ct) * The Aoluton pace defined by all paths from Foot to nod leaf node.@ dum of cubsets+ cyere are > possible formulations af Solutfons for sum of agubsetp » ‘yvariable Size Sosmuletion Ti) pined alve Prmulation. Vostlable steed formulation tne edges ore labelled 9 the edges trom level % ta the level T+) seepresen ts values of xt] sat eath node ~the -solutton Space divided into sub* Solution space tthe Solution space defined by ‘all the” paths from woot node to any yiode th the tree. she possible potths are fey teh Ueay haay 14 turzy fray ay Toy (uaz T3843 Luiruy fay Guay Wray Aur aayWy Gined sited Formulation yay paths fron root hodk —_— —"* ny TOO lode +o leaf node defines solution space. she edges from level ‘4! tp level Wa asy q ie lobetled with the value Of “CE] elthey 6 or |. tl the — path From woot rede 40 Neo? rece . cefine level ‘t to level Vr Ore Solution space The edges From labetted wtth -the value. of %Ci) etther 0 ort Probleno ctate + Each node in “ree — organization called 04 problem state Stale Space, | . All paths from rook t> other nedes He tated stale — . . Solution Stakes Solution states are problem states fem for which the path Lorn ‘ook 40 problem state defined a, tuple to solution Space.-Answeer Staten Drswer States are those Sol states the path fom ~oot do te! detined tuples be, % (no-of set of gol. of “the problem it daticfy the Up constraints. State Space tree The tree orppatzadion of atoluten space t& called Solution Apace tree. Statle ‘Tree t “he tree orgpniaation independent of problem instant being tolved Dyramic Wee } “The tree — organizabbo dlepends on problem instante being dolution * Once a state Space tree generated for. any problem , ~the problerm = Can be Solved by syptemattouty qeneratig problen states + Som problem state determine whith of “hese ave Sdution stoke and find a determun which solution states are Ongwoer states. vthere are 2 undamentake coos “to generale problem states + fies begin with woot nede and generale other nodes, tmethod=t' the neo child 'c' ap curvent E) node yi ue Generate sthe duild ‘c! loecome new ‘e! node then ‘a est be became 'g! node again when subbse 'c' has beenfatty expanded + Methad~2+ ‘gh node rremelns "ge node until tt i dead, In both methtds bounding ‘function used tm KIL. the. live node without generating childven . The depth first node qenerertton with bounding function is tatted back tracking . Ue Moder A node which har been generated and aut of those childrens thave not Yet been generated fp Called Live node. yD @® tal ig live node ) @ we mot ative nick, @ CS) BC ONE Ltve nodoy, E-nods: (Expanded Node) the live node ehoce children ore Currently betng generated & Called P-nodle a v® nsende. 1) Ow & ato enole @® © Dead Noder Dead node ts generated node which ts not edpanded further. Cord Att ap ohose children hos been qrrerated « ex, Queen Poblim.. - +I 4 Queen problem Ht tart ned voot node as ive node. thik became ‘e! node and path fe empty ."4 To generate one childven, chtldven are generated w aatending order, Node 2 generated. + Node 3 generate! and wrmediately Killed. » Alext node g ts Created path become 13 and &. be come Enede. LE quent q children, A children iy feilleck, ui node quercled ancl willed, + 18 node qunerated path is 1,4) + Repeat “the Some procedure. Hemi Hranian Cycles Let GCV,£) be a conmected graph with 'n! vertices . — Hamiltonian cycle is & wound trp path along ‘nh! edger of ‘a,’ visit every verter once and returns giarting position , —Hamiltonian cycle begin at Sone vertex Vi EQ ond vertices OF NG" vistted @in order Vi Vo Vg. Ung, then eclges (ut Meee And V,S ome dAzhotent except Vi, Vag)~Graph ‘Gi contains Hamiltontan cycle (1.2/8, 16,5,4 38,1) Po —@ we» © ‘é) ~ Graph ‘G2! Contains no Haniltonian cycle -We back tracking algorithm finds all hami ltontay DN cycle in a graph. Graph may be ckirected or undivected — Backtracking solution vector Cx, pha vs tn) ts defined so hot YG is vepresenty the ith vertex % propased cycle. TD complete the get Of possible values for tm ‘ay! Tf oe eG olveacly visited df kei then %) be any Vertex op ol vextices To avetd printing oP some cycle 'n! Himes we require that USL then Ak Gn be any vertex ogy" thar difpeient for) Ay 40 Mey ~The vettex%g ean only be one “remaining vertex tb must be connected to '4;'. CH A> M3 AU Ay Ac)© atny algorithm stort ar by firs iniHatizing adgacent watty GCN, UD) then sctting wCriny and x(a! atoen etecule tamiltonian Ce) ~The Hamiltonianck) hes one uncon neat value tw) ~We nextvalueley qenction Pind posible value Le) (® Gragh Coloring L = soluiton space cpr graph coloring fe:wet “6 be a graph and ‘mr! be a poritive ntunbes. where M=Ne-OL colors ureal. HTWe nmles Of 1G! coloved i» suth @ way thet no Too adjacent noder having some color. The WeEGEY Ad ay reqerved 98 chromate nowp graph ~ Chiomatic no 08 qreph 2 minimum Mo -af eb? colores needle +> produce proper Coloring op areph . Then ora dipecentways io whith a given qapb ton be. Colored ening atmost ‘rd colow. — BY more than one solution were using ba clebacking the Sol. represented by Com ty = A) where YU the colch of the node 'G! > State pace tree uted bo ake deqvee ee y Weight ‘na ' where n= noeef nedegs Aeqree gy node ~ Koop re edges connected, - Geyer ap aeph ~ Max. no-of nodea, Each hede ak level't’ corresponding 1D tm! chibhren to m-potible agiqn values % xCi 5! axel ~The nedeg ab level nti ar leat nodey . the qragh fe vepresentecl by 1K aclfacent matrix ACuns ur] whee AUD <1 GAB, ~ Gceyd=0, 4 Cid ge ~ Solution gpace tree 2 color in Graph Ce iy Shown herr.