FREE E LEARNING PLATFORM
☰ HOMEEXCEPTIONSOOPSJVMINTRO
SYLLABUS TUTORIALS FORUM
 

Travelling Salesman Problem



Introduction

The Travelling Salesman Problem (TSP) is one of the most well-known optimization problems in computer science. A salesman has to visit every city exactly once and return to the starting city while minimizing the total travelling cost or distance.

Unlike the Hamiltonian Cycle Problem, which only checks whether such a cycle exists, the Travelling Salesman Problem finds the minimum cost Hamiltonian Cycle. Since every possible tour may need to be examined, the Backtracking algorithm systematically explores different routes and rejects paths that cannot produce a better solution.

Problem Statement

Given a set of cities and the travelling cost between every pair of cities, determine the shortest possible tour that visits every city exactly once and returns to the starting city.

Real-Life Example

A courier company must deliver parcels to several cities. The delivery vehicle starts from the warehouse, visits each customer exactly once and returns to the warehouse. The objective is to minimize fuel consumption, travelling distance and delivery time.

Why Backtracking?

Backtracking generates all possible tours recursively. If the current partial tour becomes more expensive than the best solution found so far, that branch can be abandoned, thereby reducing unnecessary computation.

Example Cost Matrix

City A B C D
A 0 10 15 20
B 10 0 35 25
C 15 35 0 30
D 20 25 30 0

Solved Example

Assume the salesman starts from City A.

Possible Tour Total Cost
A → B → C → D → A 95
A → B → D → C → A 80 (Minimum)
A → C → B → D → A 95
A → D → B → C → A 95

Optimal Tour: A → B → D → C → A

Minimum Cost = 80

Weighted Graph


          A

      10 / \15

       /   \

      B-----C

       \25 /30

        \ /

         D

20 between A and D

Figure 1 : Weighted Graph for TSP

State Space Tree


             A

        /     |     \

       B      C      D

      / \

     C   D

    ...

Explore all possible tours

Choose Minimum Cost Tour

Figure 2 : State Space Tree for Travelling Salesman Problem

Travelling Salesman Algorithm (Backtracking)

TravellingSalesman(CurrentCity) Step 1 : Mark the current city as visited. Step 2 : Add its travelling cost to the current tour. Step 3 : If all cities have been visited, Return to the starting city. Step 4 : Compute the total travelling cost. Step 5 : Update the minimum cost if the current tour is better. Step 6 : Otherwise, Visit every unvisited neighbouring city recursively. Step 7 : Remove the last city from the current tour (Backtrack).

Dry Run

Using the previous cost matrix, the salesman starts from City A.

Step Current Tour Cost Status
1 A 0 Start
2 A → B 10 Continue
3 A → B → D 35 Continue
4 A → B → D → C 65 Continue
5 A → B → D → C → A 80 Minimum Tour Found

Complexity Analysis

Parameter Complexity Explanation
Best Case O(n) Rare situation where the optimal tour is found immediately.
Average Case Problem Dependent Depends upon pruning and graph structure.
Worst Case O(n!) Every possible tour may need to be explored.
Space Complexity O(n) Recursive call stack and visited array.

Advantages of Travelling Salesman Problem

  • Produces the optimal travelling route.
  • Suitable for optimization problems.
  • Backtracking reduces unnecessary exploration using pruning.
  • Can be extended using Dynamic Programming and Branch & Bound.
  • Useful in logistics and transportation planning.

Limitations of Travelling Salesman Problem

  • Worst-case time complexity is factorial.
  • Execution time increases rapidly with the number of cities.
  • Backtracking is inefficient for very large datasets.
  • Practical applications generally require optimization techniques.

Applications of Travelling Salesman Problem

Application Description
Courier Services Finding minimum delivery routes.
GPS Navigation Computing efficient travelling routes.
Airline Scheduling Planning aircraft routes.
Robot Path Planning Finding shortest movement paths.
VLSI Circuit Design Optimizing wire routing.
Warehouse Automation Efficient picking and delivery paths.

Travelling Salesman Problem vs Hamiltonian Cycle

Travelling Salesman Problem Hamiltonian Cycle
Finds the minimum cost tour. Checks whether a valid cycle exists.
Edge weights are mandatory. Edge weights are optional.
Optimization Problem. Decision Problem.
Minimum travelling cost is required. Cost is not considered.
Uses Backtracking, DP or Branch & Bound. Commonly solved using Backtracking.

💡 Remember This

Hamiltonian Cycle = Visit Every Vertex Once

Travelling Salesman Problem = Visit Every Vertex Once + Minimum Cost

Important Points

  • TSP is an optimization problem.
  • The salesman visits every city exactly once.
  • The journey must end at the starting city.
  • The objective is to minimize the total travelling cost.
  • Worst-case complexity of Backtracking is O(n!).
  • Branch & Bound provides a more efficient solution for larger instances.

💼 Interview Corner

  • What is the Travelling Salesman Problem?
  • Why is TSP considered an optimization problem?
  • Differentiate between Hamiltonian Cycle and TSP.
  • Why does Backtracking require factorial time in the worst case?
  • Which techniques are commonly used to solve TSP?

🎓 AKTU Examination Tip

AKTU examinations frequently ask students to explain the Travelling Salesman Problem with a cost matrix, solve a small numerical example, write the Backtracking algorithm, compare it with the Hamiltonian Cycle Problem and discuss its applications.

Summary

The Travelling Salesman Problem is one of the most important optimization problems in computer science. It aims to determine the minimum-cost tour that visits every city exactly once and returns to the starting city. The Backtracking approach explores all possible tours while pruning unnecessary paths whenever possible. Although its worst-case time complexity is O(n!), it provides the exact optimal solution for small and medium-sized problems.







Copyright 2020 by Noidatut. All Rights Reserved.

Noidatut.com