The travelling salesman problem can be solved in :
2015
The travelling salesman problem can be solved in :
- A.
Polynomial time using dynamic programming algorithm
- B.
Polynomial time using branch-and-bound algorithm
- C.
Exponential time using dynamic programming algorithm or branch-and-bound algorithm
- D.
Polynomial time using back tracking algorithm
Attempted by 47 students.
Show answer & explanation
Correct answer: C
Answer: Exponential time using dynamic programming algorithm or branch-and-bound algorithm
Explanation:
The travelling salesman problem (TSP) is NP-hard, and no polynomial-time algorithm is known for the general case. Algorithms that exactly solve TSP therefore require exponential time in the worst case.
Dynamic programming (Held–Karp): runs in about O(n^2 2^n) time and uses O(n 2^n) space, which is exponential in n.
Branch-and-bound: explores permutations but prunes branches using bounds; it can be fast on many instances but has exponential worst-case runtime.
Backtracking/exhaustive search: also exponential (examines all permutations in the worst case), so claims of polynomial time are incorrect.
Notes: special cases (e.g., small n or structured graphs) may be solved faster in practice; metric TSP admits approximation algorithms, but exact solutions remain exponential in the general case.