tree in some cases we avoid processing many potential solutionsor find solution quickly in otherswe end up visiting large portion of the possible solutions banch-and-bounds is an extension of backtracking that applies to optimization problems such as traveling salesman where we are trying to find the shortest tour through the cities we traverse the solution tree as with backtracking howeverwe remember the best value found so far proceeding down given branch is equivalent to deciding which order to visit cities so any node in the solution tree represents some collection of cities visited so far if the sum of these distances exceeds the best tour found so farthen we know to stop pursuing this branch of the tree at this point we can immediately back up and take another branch if we have quick method for finding good (but not necessarilybest solutionwe can use this as an initial bound value to effectively prune portions of the tree third approach is to find an approximate solution to the problem there are many approaches to finding approximate solutions one way is to use heuristic to solve the problemthat isan algorithm based on "rule of thumbthat does not always give the best answer for examplethe traveling salesman problem can be solved approximately by using the heuristic that we start at an arbitrary city and then always proceed to the next unvisited city that is closest this rarely gives the shortest pathbut the solution might be good enough there are many other heuristics for traveling salesman that do better job some approximation algorithms have guaranteed performancesuch that the answer will be within certain percentage of the best possible answer for exampleconsider this simple heuristic for the vertex cover problemlet be maximal (not necessarily maximummatching in matching pairs vertices (with connecting edgesso that no vertex is paired with more than one partner maximal means to pick as many pairs as possibleselecting them in some order until there are no more available pairs to select maximum means the matching that gives the most pairs possible for given graph if opt is the size of minimum vertex coverthen | < opt because at least one endpoint of every matched edge must be in any vertex cover better example of guaranteed bound on solution comes from simple heuristics to solve the bin packing problem