|
Backtracking
|
Branch-Bound
|
|
(i)
Backtracking
is one of the most general techniques for searching a set of solutions or for
searching an optimal solution.
|
(i)
Branch-Bound
is rather general optimization technique that applies where the greedy method
and dynamic programming fail.
|
|
(ii)
It
is used to find all possible solutions available to the problem.
|
(ii)
It
is used to solve optimization problem.
|
|
(iii)
It
traverse tree by DFS.
|
(iii)
It
may traverse the tree in any manner, DFS or BFS.
|
|
(iv)
It
realizes that it has made a lead choice & undoes the last choice by
backing up.
|
(iv)
It
realizes that it already has a better optimal solution that the pre-solution
leads to so it abandons that pre-solution.
|
|
(v)
It
searches the state space tree until if found a solution.
|
(v)
It
completely searches the state space tree to get optimal solution.
|
|
(vi)
It
involves feasibility function.
|
(vi)
It
involves bounding function.
|
|
(vii)
Application
of back-tracking are knapsack, sum of subset.
|
(vii)
Application
of branch and bound are sob sequencing, TSP.
|
10 March 2018
What is the difference between backtracking and Branch-Bound method
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment