Can a backtrack and "branch and bound" problem be always solved using dynamic programming?? i.e. given a problem which can be solved using a backtrack method be also solved using dynamic programming
Add a comment
|
2 Answers
In the general case, whether dynamic programming can be applied, maybe. But whether dynamic programming will definitely lead to an efficient or a pseudo-efficient solution, no.
For example, there can be a number of NP complete Integer Linear Programming problems that need to be solve using branch & bound or through brute-force backtracking since dynamic programming formulation is not possible.
For example this question that I asked some time back, I could not form a DP formulation and I had to resort to finding a solver for my ILP problem. Strange but practical 2D bin packing optimization
5 Comments
IVlad
The TSP has a DP solution, you even linked to it. It's not an attempted solution, it's a solution, it works. In general, backtracking is meant to be used when we need all solutions to a problem. You cannot apply DP for that. It's the other way around more often than not: you can use backtracking where DP would be better.
Abhishek Bansal
The solution I linked to solves the problem, but it is not efficient in terms of time or space. There are other more general problems in the ILP class for which a DP formulation is either not possible or not useful enough. For example this question that I asked some time back, I could not form a DP formulation and I had to resort to finding a solver for my ILP problem. stackoverflow.com/questions/18537335/…
IVlad
Efficiency is relative, nothing is simply efficient or inefficient. The DP solution for the TSP is asymptotically more efficient than the brute force (backtracking) one. Regardless, you should make it clear that that the TSP is not "A well-known case" of problems that cannot be solved with DP.
j_random_hacker
I agree with IVlad -- the TSP is a bad example and makes things less clear than no example at all, hence my -1.
Abhishek Bansal
Ok, I get your point. TSP as such is a bad example for this case. Edited.
There is certainly no such comparison of backtracking and DP because in general DP is used for optimization problems where you need best of many possible solutions whereas backtracking is used to search a single solution to a problem. Whereas you may have a good DP solution to problems which can be solved using Branch and Bound but not always as some problems may not be decomposable to smaller subproblems hence DP solution may not exist.
5 Comments
j_random_hacker
Your first sentence is at best unclear and at worst wrong -- backtracking can find any solution, all solutions, the best solution, the best k solutions (using a heap), etc.
Vikram Bhat
@j_random_hacker backtracking can find all solutions to problem but it is not used to do so because then it would be brute force , we normally use branch and bound for it because it prunes out some parts of search space which certainly have less(or more) value than optimal solution hence reducing time complexity. Basically there is no point in applying backtracking to optimization problem like for example knapsack for which we use BB or DP.
Vikram Bhat
@j_random_hacker The problems where backtracking is used is Constraint Satisfaction problem like graph coloring ,N Queens,Maze where DP or BB does not make any sense because there is no optimum solution as such , we just need a solution in this case which backtracking might provide quickly.
j_random_hacker
Backtracking is brute force. If your problem could have many solutions, and you want all of them, then you will most likely use backtracking to get them (although sometimes other approaches are more efficient). Yes, B&B is more efficient if you only want the best solution, but you can still use backtracking to solve this version of the problem too. Finally, even problems like graph colouring can be modeled as B&B problems (halting recursion when we detect a partial solution that cannot be completed is equivalent to fathoming a partial solution with score > bound in B&B).
Vikram Bhat
@j_random_hacker Actually u are wrong on last part, halting recursion on detection of invalid partial solution is an essence of backtracking not BB