Books Online Courses
Free Tutorials  Go to Your University  Placement Preparation 
Latest:- Important tips to get an Off Campus Placements
0 like 0 dislike
870 views
in Examples, Exercises and Projects by (562 points)
edited by
  1.  What is Backtacking? 
  • what do you mean by backtracking? 
  • Its characteristics
  • Figure
  • Various method involved in it. 
  • Various terminologies used. 
  • Travelling salesman problem
  • What is it? 
  • Examples with figure. 
  • Various steps involved to solve it. 
  • What is Hamiltonian Cycle? 
  • Answer with figure. 
  1. What is Branch and Bound? 
  • ​​​​​​What do you mean by Branch and Bound? 
  • Its definition
  • Its characteristics
  • Difference between backtracking and branch and bound. 

1 Answer

0 like 0 dislike
by (562 points)
edited by
 
Best answer

  Backtracking

Fig:Backtracking

Source:https://images.app.goo.gl/crPADhEDXUAuGsGaA

Travelling salesman problem

Procedure for solving travelling salesman problem(TSP) :

Step 1:

Find out the reduced cost matrix from a given cost matrix . This can be obtained through by following ways,

  • Row Reduction
  • Column Reduction

Row Reduction

  • Take minimum elements from first row and subtract that elements from first row(including that element), next take minimum elements from second row and substract. Similarly, apply some procedure for all rows.
  • Later, apply row reduction on resultant matrix is obtained from this, apply column reduction.

Column Reduction:

  • Take minimum element from first column, then substract that element from first column.
  • Similarly, apply some process for the remaining columns. Now, find row-wise relation sum and column wise reduction wise.

Row wise reduction sum

  • Sum of elements substracted from rows. 

Column wise Reduction Sum

  • Sum of elements substracted from columns.

Cumulative reduction=Row wise reduction sum+column wise reduction sum

Step 2:

For starting node, take cumulative reduction as lower bound and infinity as a upper bound.

  •  If path (i, j) is considered, then change all entries in row i and column j of A top.
  •  Set A(j, 1) to 8 /* assume starting node is 1*/
  • Applying row and column reduction except for rows and column contating infinity.
  • Also find cumulative reduction.

Hamilton Cycle

  • Hamilton cycle is a round trip path along n edges that visits every vertex once and return back to starting position.

Fig:Hamiltonian Cycle

Source:https://images.app.goo.gl/XNiiGsiYHqPfDH3d9

Branch and Bound

  • Branch and Bound technique is an algorithm design technique used to solve difficult combinational problems. Branch and bound constructs state space tree in such a manner that nodes specify . The choices used for the solution. This technique is used for optimization problems.
  • Branch and bound techniques needs two additional values when compared to backtracking.
  • They are as follows:
  •  A bound value of the objective function for every node of state space tree.
  • The value of best solution . So, for is compared with a nodes bound and if the nodes bound value is not better than the value of best solution set. So, for then that node is terminated.
  • This is key concept of branch and bound technique.
  • Three types of search strategies are used techniques:
  •  FIFO or BFS
  • LC search
  • LIFO or DFS
  • Bounding is a fast way of finding upper and lower bonds for the optimal solution with solution space. Branch and
  • Bound technique can be classified based on the bounding method and the way in which the search tree nodes are created or inspected.
  • Branch and Bound is a general search method, which starts by considering the root problem. Then, the lower bounding and upper bounding procedures are applied to the root problem. And if the bound match then an optimal solution has been found and the procedure terminals.
  • Otherwise the feasible region is divided into two or more regions. And then the algorithm is applied recursively to the sub problems. If an optimal solution is found to a sub problem. It is a feasible solution to the full problem but not necessarily globally optimal.
  • Bounding may play an important role in this technique. Since it increase the speed of finding the bounds.

3.3k questions

7.1k answers

395 comments

4.6k users

 Goeduhub:

About Us | Contact Us || Terms & Conditions | Privacy Policy || Youtube Channel || Telegram Channel © goeduhub.com Social::   |  | 
...