The General Backtracking Method (1)If vrepresents a final solution to the problem,the algorithm records it as a solution and either terminates in case only one solution is desired or continues to find other solutions. (2)If vrepresents a partial solution,the algorithm advances by choosing the least element in the set X2. (3)If vis neither a final nor a partial solution,we have two subcases: (a)If there are still more elements to choose from in the set X1,the algorithm sets 1 to the next member of X1. (b)If there are no more elements to choose from in the set X1,the algorithm backtracks by setting x,to the next member of X,.If again there are no more elements to choose from in the set the algorithm backtracks by setting x1 to the next member of Xi1,and so on
The General Backtracking Method (1) If v represents a final solution to the problem, the algorithm records it as a solution and either terminates in case only one solution is desired or continues to find other solutions. (2) If v represents a partial solution, the algorithm advances by choosing the least element in the set Xj+2. (3) If v is neither a final nor a partial solution, we have two subcases: (a) If there are still more elements to choose from in the set Xj+1, the algorithm sets xj+1 to the next member of Xj+1. (b) If there are no more elements to choose from in the set Xj+1, the algorithm backtracks by setting xj to the next member of Xj . If again there are no more elements to choose from in the set Xj , the algorithm backtracks by setting xj-1 to the next member of Xj-1 , and so on
Branch and Bound Branch and bound design technique is similar to backtracking in the sense that it generates a search tree and looks for one or more solutions. However,while backtracking searches for a solution or a set of solutions that satisfy certain properties(including maximization or minimization),branch-and-bound algorithms are typically concerned with only maximization or minimization of a given function. Moreover,in branch-and-bound algorithms,a bound is calculated at each node x on the possible value of any solution given by nodes that may later be generated in the subtree rooted at x.If the bound calculated is worse than the previous bound,the subtree rooted at xis blocked
◼ Branch and bound design technique is similar to backtracking in the sense that it generates a search tree and looks for one or more solutions. ◼ However, while backtracking searches for a solution or a set of solutions that satisfy certain properties (including maximization or minimization), branch-and-bound algorithms are typically concerned with only maximization or minimization of a given function. ◼ Moreover, in branch-and-bound algorithms, a bound is calculated at each node x on the possible value of any solution given by nodes that may later be generated in the subtree rooted at x. If the bound calculated is worse than the previous bound, the subtree rooted at x is blocked. Branch and Bound