What are some good resources for learning backtracking, branch-and-bound and dynamic programming algorithms? [closed]

Question

As it currently stands, this question is not a good fit for our Q&A format. We expect answers to be supported by facts, references, or expertise, but this question will likely solicit debate, arguments, polling, or extended discussion. If you feel that this question can be improved and possibly reopened, visit the help center for guidance.

Closed 8 years ago.

CLRS doesn't seem to cover bactracking/branch-and-bound. I tried several resources online, though I get the idead behind these, I am unable to write code for, let's say, Knapsack problem. So, I want something that, may be, takes a problem and solves it with these 3 approaches and at least gives pseudo-code. Or any resources that you thing will be helpful.

Answer 1

In algorithms which use backtracking, branch/bound etc. there is typically the concept of the solution space, and the search space. The goal of the algorithm is to traverse the search space to reach a point in the solution space, and often a point which is considered optimal by some metric, or establish that the solution space is empty (without visiting every element in the search space).

The first step is to define a mechanism to express an element in the search space in an efficient format. The representation should allow you to express what elements form a solution space, a way to evaluate the quality of element by the metric used to measure, a way to determine the neighboring elements you can reach from a current state and so on.

Typically these algorithms will traverse the search space till the find a solution, or will exit if no solution will exist. The traversal happens by visiting a series of points, often in parallel to explore the search space. This is the branch aspect; you are making decisions to visit certain parts of the search space.

During the traversal of the search space they may determine that a particular path is not worth it so they may decide that they would not explore the part of the search space reachable from the path. This is very bounding aspect.

Very often the traversal of the space is done by using partial solutions. For example if you have a search space represented by eight bits, you might assign fixed values to two specific bits out of the eight bits, and then search for a desirable solution for the space represented by the remaining six bits. You might discover that a particular assignment of the two bits to a fixed value leads to a situation where no solution can exist (or the quality of the solution is very poor). You can then bound the search space so that the algorithm does not explore any more elements in that sub-space defined by assigning a particular fixed value to those two bits.

For backtracking based systems the pseudo code is trivial. The challenge lies in finding efficient representation to represent the search space, representing partial solutions, finding out the validity of a particular solution, coming up with rules to determine which path to take up front, developing metrics to measure the quality of solution, figuring out when to backtrack, or how far to backtrack and so on...

StateStack.push(StartState)
loop{
  curState = StateStack.top
  nextState = calculateNextState(curState)
  StateStack.push(nextState)
  if(reachedFinalGoal(nextState)){
     break;
  }
  if(needToBackTrack(StateStack)){
     curState = nextState
     stateToBackTrackTo = calculateStateToBackTrackTo(stateStack)
     while(curState != stateToBackTrackTo){
       stateToGoBackTo = stateStack.pop
       curState = RollBackToState(stateToGoBackTo)
  }
}

Answer 2

These are search techniques, rather than algorithms. To start with, you should clearly understand what the search space is. E.g. in the case of a Knapsack problem that would consist of all the possible subsets of available objects. Sometimes there are constraints that define which solutions are valid and which are not, for example those sets of objects that exceed the total volume of the knapsack are not valid. You also should have the clearly defined objective (the total worth of the selected objects here).

Wikipedia contains a pretty accurate description of the Branch and Bound, actually. It's rather high-level, but any description that is more detailed will require assumptions about the structure of the search space. For backtracking there's even some pseudo-code, but again very general.

An alternative (and probably better) approach is to find example applications of these techniques and study those. There's at least a couple of algorithms involving DP in CLRS and you can surely google up more if you need.