Travelling Salesman Problem (TSP) – Backtracking Approach

  

Travelling Salesman Problem (TSP) – Backtracking Approach

Problem Statement:

Given a set of cities and the distance between every pair of cities, the salesman must start from a city, visit every other city exactly once, and return to the starting point with the minimum travel cost. As the salesman is travelling back to his original city it is called like backtracking approach. we are solving this problem with backtracking approach. 

In order to solve complex issues, backtracking is a sophisticated algorithmic strategy that builds candidate solutions incrementally and discards incomplete candidates ("backtracking") as soon as it is evident that they cannot possibly result in a workable solution. Using a state-space tree, in which each node denotes a partial answer and branches stand for later decision points, this approach methodically investigates possible solutions. Through intelligent search space reduction, backtracking ensures optimality while drastically lowering computational complexity when compared to brute-force methods. It is especially useful for constraint satisfaction problems (like N-queens, Sudoku) and combinatorial optimization problems (like the Traveling Salesman Problem). The technique is essential for NP-hard problems where exhaustive search is not practicable because of its recursive implementation and capacity to use problem-specific heuristics for early termination. 

Backtracking Strategy

1. Start from a city.

2. Explore all possible paths recursively.

3. Track visited cities.

4. Backtrack when a route is not optimal.

5. 
   

6. Keep updating the minimum cost path.Example Problem

   Cities: A, B, C, D

   Cost Matrix (with ∞ for same city):

   
   

            A B C D

   A ∞ 10 15 20

   B 10 ∞ 35 25

   C 15 35 ∞ 30

   D 20 25 30 ∞(a) Row Reduction

   Subtract the smallest value in each row (ignoring ∞): we found row minimum and reduced minum value of row from all values of row

   Step 1:

   Row Min Reduced Matrix

   A 10 ∞, 0, 5, 10

   B 10 0, ∞, 25, 15

   C 15 0, 20, ∞, 15

   D 20 0, 5, 10, ∞

   New Matrix:

   
   

            A B C D

   A ∞ 0 5 10

   B 0 ∞ 25 15

   C 0 20 ∞ 15

   D 0 5 10 ∞

   Row Reduction Cost = 10 + 10 + 15 + 20 = 55

   
   

   (b) Column Reduction

   Subtract the smallest value in each column (ignoring ∞):

   
   

   Column Min Reduced Matrix

   A 0 ∞, 0, 0, 0

   B 0          0, ∞, 20, 5

   C 5 5, 25, ∞, 10

   D 10 10, 15, 15, ∞

   Final Reduced Matrix:

   
   

            A B C D

   A ∞ 0 0 0

   B 0 ∞ 20 5

   C 0 20 ∞ 5

   D 0 5 5 ∞

   Column Reduction Cost = 0 + 0 + 5 + 10 = 15

   
   

   Total Initial LB = 55 (Row) + 15 (Column) = 70

   (Any complete tour must cost at least 70.)

   Step 2: Force First Move A → B    Path So Far: A → B

   • Edge Cost (A→B) = 10
   • Disable Row A and Column B (since A is visited, and we can't return to B yet).

   Submatrix After A → B:

   	A	C	D
   B	0	20	5
   C	0	∞	5
   D	0	5	∞

   New Reductions on Submatrix

   (a) Row Reduction

   • Row B: Min = 0 → No change
   • Row C: Min = 0 → No change
   • Row D: Min = 0 → No change

   (b) Column Reduction

   • Column A: Min = 0 → No change
   • Column C: Min = 5 → Subtract 5 from C column
   • Column D: Min = 5 → Subtract 5 from D column

   Reduced Submatrix:

   	A	C	D
   B	0	15	0
   C	0	∞	0
   D	0	0	∞

   New LB = Parent LB (70) + Edge Cost (10) + New Reductions (5 + 5) = 90

   ---

   Step 3: From A → B, Explore Next Moves

   Now, from B, possible next cities: C or D (A is already visited).

   Option 1: A → B → C

   • Edge Cost (B→C) = 25
   • Disable Row B and Column C

   Submatrix After A → B → C:

   	A	D
   C	0	0
   D	0	∞

   • No further reductions possible.
   • New LB = 90 + 25 + 0 = 115

   Complete Path: A → B → C → D → A

   • Total Cost = 10 (A→B) + 25 (B→C) + 30 (C→D) + 20 (D→A) = 85

   (But LB was 115, which is higher than the actual cost. This means our LB was not tight enough.)

   ---

   Option 2: A → B → D

   • Edge Cost (B→D) = 15
   • Disable Row B and Column D

   Submatrix After A → B → D:

   	A	C
   C	0	∞
   D	0	5

   • Column C: Min = 5 → Subtract 5.
   • New LB = 90 + 15 + 5 = 110

   Complete Path: A → B → D → C → A

   • Total Cost = 10 (A→B) + 15 (B→D) + 30 (D→C) + 15 (C→A) = 70

   (This matches the earlier optimal solution.)

   ---

   Conclusion for Forced Path A → B

   • Best Path Starting with A → B:
     A → B → D → C → A with Total Cost = 70
   • Alternative Path Starting with A → B:
     A → B → C → D → A with Total Cost = 85

   Since we forced A → B, the best possible solution is 70.
   However, if we explored other initial moves (like A → C or A → D), we might find other paths with cost 70                                                   Final Answer:

   If we only explore paths starting with A → B, the best solution is:
   A → B → D → C → A with Total Cost = 70.

   This is one of the two optimal solutions (the other being A → C → D → B → A).

   Thus, the solution is not unique, but restricting to A → B gives one of the best paths.

   ---