1Backtracking and Branch and BoundModule 11CSE5311 Fall 2008Kumar CSE5311Backtracking Using BacktrackingLarge instances of difficult combinatorial problems can be solvedWorst case complexity of Backtracking can be exponential Typically, a path is taken to check if a solution can be reachedIf not, the path is abandoned and another path takenThe process is repeated until the solution is arrived at2Kumar CSE5311N-Queens problem Place n-queens on an n × n chess board so that no two queens attack each other.A queen can attack another if the latter is on the same row, column or diagonalQ1Q2Q3Q4Kumar CSE5311Q013Kumar CSE5311Q01QQ2Kumar CSE5311Q01QQ2QQ24Kumar CSE5311Q01QQ2QQ2Kumar CSE5311QQQQQQQQQQQQQQQQQQ0123456785Kumar CSE5311Hamiltonian Circuit Problemad ebfcabcdefStart at a vertex and visit all the other vertices in the graph exactly once and return to the start vertexKumar CSE5311Hamiltonian Circuit Problemad ebfcabcdefed f6Kumar CSE5311Hamiltonian Circuit Problemad ebfcabcdefeedd ffca12345678910111213Kumar CSE5311Subset Sum Problem Given a Set S ={s1,s2, … Sn} and a posiitiveinteger ‘d’ find a subset of the given set S such that the sum of the positive integers in the subset is equal to ‘d’.  Let S = {3,7,9,13,26,41}; d = 51.  Note – the list should be sorted.7Kumar CSE5311Subset problemLet S = {3,7,9,13,26,41}; d = 510w3w/o 3310193258327319451960 19w7w9w13w26w/o 26w41w/o 26w/o 41w/o 13w26w/o 41w41w41w/o 41Kumar CSE5311Subset problemLet S = {3,7,9,13,26,41}; d = 510w3w/o 3310193258327319451960 19w7w9w13w26w/o 26w41w/o 26w/o 41w/o 13w26w/o 41w41w41w/o 4133w/o 9w/o 7w/o 131212w/o 1325w13w951w26w/o 268Kumar CSE5311Branch and Bound With backtrackingThe search space is can be very largeIt is an exhaustive search Worst case complexity is exponential Branch and bound techniqueLimits the search spaceThrough an estimate of the  Upper bound or Lower boundKumar CSE5311Scheduling problem The problem of assigning n people to n jobs such that the total cost is as small as possible4967D8185C7346B8729AJ4J3J2J1JobPerson9Kumar CSE5311Branch and Bound Find a Lower Bound on the cost of the solution The lower bound is only an estimateThis is only an estimate The LB may not be a legitimate solution In this case, consider the lowest cost from each row 2 +3+1+4 =10This is our LB4967D8185C7346B8729AJ4J3J2J1JobPersonKumar CSE5311StartLB= 2+3+1+4 = 10A→J1LB= 9+3+1+4 = 17A→J2LB= 2+3+1+4 = 10A→J3LB= 7+4+5+4 = 20A→J4LB= 8+3+1+6 = 1814324967D8185C7346B8729AJ4J3J2J1JobPersonB→J1LB= 2+6+1+4 = 13B→J3LB= 2+3+5+4 = 14B→J4LB= 2+7+1+7 = 10C→J3, D→J42+6+1+4 = 13C→J4, D→J32+6+8+9 = 255678910Kumar CSE5311StartLB= 2+3+1+4 = 10A→J1LB= 9+3+1+4 = 17A→J2LB= 2+3+1+4 = 10A→J3LB= 7+4+5+4 = 20A→J4LB= 8+3+1+6 = 1814324967D8185C7346B8729AJ4J3J2J1JobPersonKumar CSE5311StartLB= 2+3+1+4 = 10A→J1LB= 9+3+1+4 = 17A→J2LB= 2+3+1+4 = 10A→J3LB= 7+4+5+4 = 20A→J4LB= 8+3+1+6 = 1014324967D8185C7346B8729AJ4J3J2J1JobPersonB→J1LB= 2+6+1+4 = 13B→J3LB= 2+3+5+4 = 14B→J4LB= 2+7+1+7 = 1756711Kumar CSE5311StartLB= 2+3+1+4 = 10A→J1LB= 9+3+1+4 = 17A→J2LB= 2+3+1+4 = 10A→J3LB= 7+4+5+4 = 20A→J4LB= 8+3+1+6 = 1014324967D8185C7346B8729AJ4J3J2J1JobPersonB→J1LB= 2+6+1+4 = 13B→J3LB= 2+3+5+4 = 14B→J4LB= 2+7+1+7 = 10C→J3, D→J42+6+1+4 = 13C→J4, D→J32+6+8+9 = 2556789Kumar CSE5311Knapsack Problem We wish the maximize the profit in the knapsack Maximization  Use Upper bound UB = v+ (W-v)(vi+1/wi+1) When we start v = 04$123D5$255C6$427B10$404AValue/weightValueWeightItemW = 1012Kumar CSE5311KnapsackStartW=0, v=0UB = 100UB = v+ (W-v)(vi+1/wi+1)W=4 v=4UB = 76W=0, v=0UB = 60With AW/o AWhich is better? W=11InvalidW=4 v=40UB = 70With CW/o BW=4 v=40UB = 64W=9 v=65UB = 69With BW/o CW=12InvalidW/o DWith DW=9, v=65UB =65Kumar CSE5311Traveling Salesperson Problem LB = ∑ (distance to two nearest cities)/2 ∑ over all cities83aec db1567942313Kumar CSE5311Problems$124D$568C$637B$10010AValue/weightValueWeightItemac