So let's say i have a graph like this and salesman starts his journey at "A" enter image description here

How do i solve the TSP problem for this graph with pen and paper on exam?

  • 1
    $\begingroup$ The idea of computer science is that instead of doing things by hand, you devise an algorithm and let the computer do them for you. Ask your TA for tips, or tell your lecturer that this type of question is against the spirit of the area. $\endgroup$ – Yuval Filmus Aug 29 '16 at 15:22
  • 1
    $\begingroup$ Use any algorithm which you train a lot. Note that there are only 24 solutions in total, so you can even quickly write down all of them. (I think this is unworthy of an exams, but well.) $\endgroup$ – Raphael Aug 29 '16 at 15:30
  • $\begingroup$ @Raphael unless the point of the exercise is to introduce the 2-approximation for Euclidian TSP, as an introduction to approximation algorithms or to get some extra millage out of MST with this 'application'. Either way BE, DE and/or BD seem to be missing? $\endgroup$ – Fasermaler Aug 29 '16 at 15:52
  • $\begingroup$ @Fasermaler If the task was "Apply algorithm A to this instance", it could work as an exercise. Apparently, the OP expects to be asked to provide an optimal tour, which is a trivial task on an instance this size. $\endgroup$ – Raphael Aug 29 '16 at 15:53
  • 1
    $\begingroup$ @Raphael Agreed, I was going from my GT instructor who happened to be very clear that we're not supposed to be solving NP-hard problems on exams. If at any time we found ourselves trying to do so, we'd better check if we understood the question correctly. I guess not all instructors are this enlightened. $\endgroup$ – Fasermaler Aug 29 '16 at 16:01

Your Answer

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

Browse other questions tagged or ask your own question.