0
$\begingroup$

We are studying the Travelling Salesman problem in my high school class, and I am wondering what the Big O complexity of the TSP is when you MUST start and end at the same city. For example, given 4 cities labelled A,B,C,D and you MUST start and end at A, what is the big O notation for this? Is ((n-1)!)/2 for both symmetrical and asymmetric cases?

Thanks

|cite|improve this question
$\endgroup$
  • 1
    $\begingroup$ It doesn't really make a difference as the solution is a cycle through the cities. You can start anywhere on the cycle. $\endgroup$ – Pontus Jul 13 '19 at 9:45
1
$\begingroup$

The start city makes no difference. You're constructing a tour through all the cities, so it doesn't matter if you do ABCDEA or CDEABC.

Held–Karp solves TSP in time $O(n^22^n)$, which is much faster than $\Theta(n!)$.

|cite|improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.