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.
| 
| 
