BacktrackingSum of SubsetsandKnapsackBacktracking• Two versions of backtracking algorithmsTwo versions of backtracking algorithmsTwo versions of backtracking algorithmsTwo versions of backtracking algorithms– Solution only needs to be Solution only needs to be Solution only needs to be Solution only needs to be feasiblefeasiblefeasiblefeasible (satisfy (satisfy (satisfy (satisfy problemproblemproblemproblem’s constraints) s constraints) s constraints) s constraints) •sum of subsetssum of subsetssum of subsetssum of subsets– Solution needs also to be Solution needs also to be Solution needs also to be Solution needs also to be optimaloptimaloptimaloptimal•knapsackknapsackknapsackknapsackThe backtracking method• A given A given A given A given problemproblemproblemproblem has a set of constraints and has a set of constraints and has a set of constraints and has a set of constraints and possibly an objective functionpossibly an objective functionpossibly an objective functionpossibly an objective function• The The The The solution must be feasible and it may must be feasible and it may must be feasible and it may must be feasible and it may optimize an objective functionoptimize an objective functionoptimize an objective functionoptimize an objective function• We can represent the We can represent the We can represent the We can represent the solution spacesolution spacesolution spacesolution space for the for the for the for the problem using a problem using a problem using a problem using a state space treestate space treestate space treestate space tree–The The The The rootrootrootroot of the tree represents of the tree represents of the tree represents of the tree represents 0 choice0 choice0 choice0 choice, , , , –Nodes at depth 1 represent Nodes at depth 1 represent Nodes at depth 1 represent Nodes at depth 1 represent first choicefirst choicefirst choicefirst choice–Nodes at depth 2 represent the Nodes at depth 2 represent the Nodes at depth 2 represent the Nodes at depth 2 represent the second choicesecond choicesecond choicesecond choice, etc. , etc. , etc. , etc. –In this tree In this tree In this tree In this tree a a a a pathpathpathpath from a root to a leaffrom a root to a leaffrom a root to a leaffrom a root to a leaf represents a represents a represents a represents a candidate solutioncandidate solutioncandidate solutioncandidate solutionSum of subsets• Problem: Given : Given : Given : Given nnnn positive integers positive integers positive integers positive integers wwww1,... wwwwnand a positive integer S. and a positive integer S. and a positive integer S. and a positive integer S. Find all subsets of Find all subsets of Find all subsets of Find all subsets of wwww1,... wwwwnthat sum that sum that sum that sum to S. to S. to S. to S. • Example: : : : n=3, S=6, and wn=3, S=6, and wn=3, S=6, and wn=3, S=6, and w1111=2, w=2, w=2, w=2, w2222=4, w=4, w=4, w=4, w3333=6=6=6=6• Solutions::::{2,4} and {6}{2,4} and {6}{2,4} and {6}{2,4} and {6}Sum of subsets• We will assume a We will assume a We will assume a We will assume a binary state space treebinary state space treebinary state space treebinary state space tree. . . . • The nodes at depth 1 are for including (The nodes at depth 1 are for including (The nodes at depth 1 are for including (The nodes at depth 1 are for including (yes, yes, yes, yes, nononono) item 1, the nodes at depth 2 are for ) item 1, the nodes at depth 2 are for ) item 1, the nodes at depth 2 are for ) item 1, the nodes at depth 2 are for item 2, etc. item 2, etc. item 2, etc. item 2, etc. • The The The The left branchleft branchleft branchleft branch includesincludesincludesincludes wwwwiiii, and the , and the , and the , and the right right right right branch excludesbranch excludesbranch excludesbranch excludes wwwwiiii....• The nodes contain the The nodes contain the The nodes contain the The nodes contain the sum of the weightssum of the weightssum of the weightssum of the weightsincluded so farincluded so farincluded so farincluded so farSum of subset Problem:State SpaceTree for 3 items: w1= 2, w2= 4, w3= 6 and S= 6i1i2i3yesno00002226612844106yesyesnonononononoThe sum of the included integers is stored at the node.yesyesyesyesA Depth First Search solution• Problems can be solved using depth first Problems can be solved using depth first Problems can be solved using depth first Problems can be solved using depth first search of the (implicit) state space tree. search of the (implicit) state space tree. search of the (implicit) state space tree. search of the (implicit) state space tree. • Each node will save its depth and its (possibly Each node will save its depth and its (possibly Each node will save its depth and its (possibly Each node will save its depth and its (possibly partial) current solutionpartial) current solutionpartial) current solutionpartial) current solution• DFS can check whether node v is a leaf. DFS can check whether node v is a leaf. DFS can check whether node v is a leaf. DFS can check whether node v is a leaf. –If it is a leaf then check if the current solution If it is a leaf then check if the current solution If it is a leaf then check if the current solution If it is a leaf then check if the current solution satisfies the constraintssatisfies the constraintssatisfies the constraintssatisfies the constraints–Code can be added to find the optimal solutionCode can be added to find the optimal solutionCode can be added to find the optimal solutionCode can be added to find the optimal solutionA DFS solution• Such a DFS algorithm will be very slow. Such a DFS algorithm will be very slow. Such a DFS algorithm will be very slow. Such a DFS algorithm will be very slow. • It does not check for every It does not check for every It does not check for every It does not check for every solution statesolution statesolution statesolution state((((nodenodenodenode) whether a solution has been ) whether a solution has been ) whether a solution has been ) whether a solution has been reached, or whether a reached, or whether a reached, or whether a reached, or whether a partialpartialpartialpartial solution solution solution solution can lead to a can lead to a can lead to a can lead to a feasiblefeasiblefeasiblefeasible solution solution solution solution • Is there a more efficient solution?Is there a more efficient solution?Is there a more efficient solution?Is there a more