2.7 backtracing and branch and bound

• Backtracking:
  1. It is used to find all possible solutions available to the problem.
  2. It traverse tree by DFS(Depth First Search).
  3. It realizes that it has made a bad choice & undoes the last choice by backing up.
  4. It search the state space tree until it found a solution.
  5. It involves feasibility function.
• Branch-and-Bound
  1. It is used to solve optimization problem.
  2. It may traverse the tree in any manner, DFS or BFS.
  3. It realizes that it already has a better optimal solution that the pre-solution leads to so it abandons that pre-solution.
  4. It completely searches the state space tree to get optimal solution.
  5. It involves bounding function.
  6. Searches a solution space that is often organized as a tree (like backtracking)
  7. Usually searches a tree in a breadth-first / least-cost manner (unlike backtracking)
• Difference between DFS and backtracking is:
  1. Backtracking is a more general purpose algorithm. Depth-First search is a specific form of backtracking related to searching tree or graphic structures.
  2. For a problem, answer space can be described as a tree graphic structure, such as 0/1 backpack problem. at this time, backtracking use DFS to search the answer space, and use questions related condition to prune the sub-tree and com back. So in this way, you can think backtracking = DFS+prune.
  3. For mouse raze, because, prune is "no next neighbor", just like DFS, so DFS and backtracking are the totally same.
• Difference between branch-bound and backtracking is about size
  1. backtracking use stack and only add one child each time, so it use less memory compared with branch-bound
  2. branch-bound store all possible child in queue, so if answer is near root, it will find answer quickly.
  3. win in size, but lose in time. backtracking will 1) find answer slowly, 2) branch-bound will find optimal answer.
• A example can be see in ref PPT. container and ship problems.