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

Question

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)
  }
}