or = vatlr. iv = Intropveran % Bacerenckin, & Beancy aw Bounp a a — oe ome Backtracking ak Ls sme af Ahe problem aalving approach Ao ausign algoxcthns Jo dolve Problees ¥ Or follows Arte - forct opproak. gb dues out alt possible tolubons fr a problem and selects the deated —doluhon the -disied olubon wilt Le chosen Jbaxd on the Constraint queen Zalled as rounding function s Assume 3 persons Pi, Py and Pg to te arvianged in 3 cheins Possible ways do oooange 4s 312 6 Nop. ¥ Solubon 4s mepresented as a Aree called cu State - Space fee dt Constrids state spon tree fottewing Depth Fist Seaxch (Drs). atts eee + Assume a Constraint. Pr should not be placed in the [middie Thin ads on a bounding furor Pe Kiled Boun. Condithon; : s [Branch and Bound i | ae wae i ce As that Yt se similar to backtracking © only yen ath Ent Scanca ler’ at Cconstrucls the Atale Apa Faw sing Brea N- Queens Problem - +The problem is do place h. queen on two queens cittak each other dy berg dn on the same an Nxn chessboard 4o that no Aho same Aow or An Abe ame column or pe # Sina each ef dhe jou qpens Bos do te phaud in ib sum now, alt ave nud to do is tb omign der cack queen a column < queen | @ 1 flee queen 2a [Te queens 4 ft 1d fe queen A Stont with empty boord and than plan qpen | dn te Fint possible position of ils wow, which i in column | & mol, 4 ohen pla qpeen 2, aftr douying ansucussfalty column | £2 in te ae accessible posihen fay ik, ushich is squam (2,3), th Aqua row 2 and column 3. This proves Jo te a dead end ‘becouse Hux i No acceptable posihan for queen 3. | * Hen, the abgorithn harktyads and pubs queen 2 in the next | posse posibion ot (a,4). Than queen 3 is placed at (3,2), which proves to be another dead end. ae algorithm then backtvacks Ot te way + gpeen | roves it to (2). Quen Q thin goes to [aiy) queen 3 bo (3,1) Land quee oe | queen 4 to (4.3), thick is a adlutin to the Problem . | 1 GndNS re x faa) Solubon the State - spac bes # The diagram represents by backtracking « xX denotes an oF solving He H-queent problem unsuccessful attempt to place & queen in the unditated Column. The Numbers above the nodis Anclicete Ame ordea in which the nodes re qervretil Sve Of Sveser Feostem: ihe Sum of Subse problm ay Jo faa O subset of a gen | ate A= Sars: On} of nm posihie dakegoe Or dar de Lan (whose Aum ds 2qpok do 4 given positive antag. ad FEvampk - for A=f1,2,6,6,84 and A=, thee on 2 _ dolubons stp aby and fie).| * She Abate, Apae fa: can Le constructed as a binoy bud [The most of ie tus Supsusents the staking point , with no [decisions about the Ger elements made os yet * Os Dep and ought children reprusent , suspectivelyy , in Lusion | Qnd exclusion ot a: vn oh dee Ateing sought. Simikerty ry b | te Lee from Q node of the fist ie Corresponds do inclusion M2 while gorhg to Aight Corresponds Jo ih xctusion and Som FThus, a path rem the Root lo @ node on the it level Hake hee uhdlicates soho of te pout numbos shave been indded in the subsets Aaprisentied by that node * Recovd tre vals of S, tre Sum of the numbis ,io the node SF 2 43 equal do A, we hare a solehin fp dhe problim Ne Con either xpos Abis resubl and stop tor) if oll adhe solubdns need to pe found, Conbinue doy te bacrtraucing do the node's parent - SP gs is not equal fo a, we con terminate the node as neon Promising \f either of the Following 2 ineyraditics hold : Sr Oy, >A (te gum sis tvo large) StB aj <4 (the Sum Sis too Smal) Jen gorithm £ Time Complexity of Sum & subsel ie 4s 0a") Suma Subsets (6k, a) ‘ T cteyet; AL (At Wigs =m) then waite (x tik) ; abe if (St WTRLE Ws Teer yes) Hen Sumefsubsits ($4 WER], kel, A- WIRD)! 4 (Catn—-ulk J >= m) ond (o+Htkricrm)) tren 1 xtki-0; Sumafsubsets (A, +1, A- WEI);Rempe A=TBS TY at dig ae = - with 5 Ne with, wlo x b 6 Oriacls | \* WHT IS win ee Mas BIe uae Bee eo Solubon x B RAjaceney matrix of Graph . O—D 3 @ &) ase 0) -/ P/O us DAdjaeney dist oF raph © 7 CB-LTEES ER?6EPrasany ED-ary Harattoninnt Creer: RHamitboruan ceveush lor) Hamiltonian cgcle | - Given a | greph, Atak o vertex , visit all Other vechies Un the | Graph 2x0 Utly ent and Aetum back to the Alek verter | # Diver graph , Can Le etther olivected or undirected but [ib must be Connected This is NP head problem. gt tates exponential hme to fend out | Geample | Cycle | — A,B,C,D, 6, F,.8 | oy J Cycle 2 - A,B, F,E,D, 1A E © iS (yde B- A, F,B,€,D, 017 B,C, D,€,F,A, B- Similar to tych I * Graphs sith axtiudabin pot and pandank verbirs | sill not contain Hamiftonion cycle Aamiltonian cycle in grreph .| Solubon 5 Consider He problem of Finding a Hamilkomdn circuit in [HR teen graph. Nithouk on ot gennalily, coe Can omums | that ah w Hromilboruan vault ais , ik starts at vetlen o , vortex a 4s made as the root of the State -Space i | accordingly | | 1 Using He alphabet ordi fo break the Hae way tis emong| Ahe vabius adjaunk to A, +e pelece vertex b. From b, the [algorithm procuds de ¢, ten fo A, then to @ and Soaly & 4 which pwres te be a dead and | | 4+ So, tne al gorithm batktrads fom £ ay e, then tod, | and thin 40 6, awhich prondss Ene fist alkanabive for tu | Odgorithry fo pursur - | | ’ Going From ¢ 40 @ gventually proves ules, and Ue | | elgorthm has to backtrack Bom 2 bc ond thin bb, | || | Sey cromichea pik goes, ee ues hye, 2 and a aohch ib can depitimatily rebum to a, -yielcling Hariltond Cirust a,b, 4,¢,0)d,a. T And obher Hamiltonian Greuit , Continue this prow at by backtracking fom tra Leaf to the Aoluhn found Algosithm « | Hamiltonian CR) Nentvertex (k) | 4 do t ‘ : | Noxtvertex (k)> xfkj= x Tea} mod CnH); i >} (atk) =-0,) +f (xIk}]=-0) aban } ns # COT ACR-D, xf&) L=o) 4 Ck==n) ea k-1 Prink (xTh-n3); iP Cxtjd =2xTh)) than break, else woe ' tyee8) Hamiltonian (h+1); | ee MP (ken) oxlee=n) ond io y3 G[xtn} xt 1-0) | vohum | 3 | Brance Awp Boon: | * Branch ond bound is a Aystematie method for solving | optimization pproblims - Branch and bound vis a rath genual | opheriaahin Fechnique Arak applies aohorr the qnedy wmethod [and dynamic programming oils | & However , dk is muck slower. Andeed , at after ceeds to a stir, Comp Rexibies in the wont com: On te ofr tsaund 2h applied Larfully , ik ean dead to Algovithms that ren veosonably fost on average » * The genral 2820 ee branch ancl bound 48 a BPS peer | Aeon for ew ®pkmal Soluhen , Aout nok okt nodes got CxpandadRather, © Cosehully aActeced Coerion datauminus which node # | pond and when, end anotha writeion tells dhe algouitn | ae an ophmeal solubim has been gound | [knapsack Peostem : | Grier items of Rnown sweights wy and values Viv | ja eua. yh Gnd oO knapsack of capacity W, find the most | [votuabl Aubset of the items sthak fib in the heapsack. | le JE Convenient to order the iems of a given instane | Jin descending ordin by than Value fy wait abies Thin the | fink tem gre the bok Paget per sought sunk and tu | [ost one gives dhe avons payott pe vasight unit, with des | resolved arbitrarily : i Vilwi & Yalwe 2 - = Va] vin i Each mode on the ith Lwel of Ahn bee , 0 Si polar D> | | pliky + Dik JD ths ot the Shorlst paths | Long te vertices) with No intermedial vata. Vertices numboud jntermecial not hugher than oie, gust @ Lengins ot he Shortest paths ial intermediate vations numbered er ugh than 2. legis @ and & | Gece al ; a ‘ to 3 P| Lengths Ah the Shotlest paths with Soleo s \6 intermestiale vertices numbered nok e| 4 ot 4 te) Ob and © A\ le ale 2 = } 4 4) bongtts BP the chrtot paths with 6 | intermedia verbiets num bated” nate 1 high Hon 4, @) a,b, cand d. Se oop esa pos °