2
$\begingroup$

I got this question in an interview recently. I was given a bunch of points (for eg.- Start(88, 81), Dest(85,80), P1(19, 22), P2(31, 15), P3(27, 29), P4(30, 10), P5(20, 26), P6(5, 14)) on a 2D plane and any two of them were Source and Destination. I was asked to calculate the least cost to travel all the points starting from the source and ending on Destination point. The cost to travel between any two points is |x1 - x2| + |y1 - y2|.

So, what I thought of doing was construct a cost matrix and apply Dijkstra since I thought constructing the shortest path tree must be the solution.

But I couldn't think on how to construct this cost matrix. What is the best approach for this?

$\endgroup$
2
$\begingroup$

This is the Traveling Salesman Problem with the $L_1$ metric (also known as the Manhattan distance).

Unfortunately, this version of the TSP is also NP-hard. Therefore, there is no algorithm that always produces the optimal solution, is efficient, and works for all inputs. Instead, you'll have to use a heuristic or approximation, or accept a solution that can take exponential time in the worst case. Dijkstra's algorithm won't suffice.

Strictly speaking, the standard formulation of the TSP doesn't allow you to visit any point more than once. However, in this situation allowing you to visit a point more than once doesn't make the problem any easier, since visiting a point more than once will never help you find a shorter solution.

Perhaps the following paper will be useful:

The L1 Traveling Salesman Problem. Donald C.S. Allison, M.T. Noga, Information Processing Letters, vol 18, 1984, pp.195-199.

$\endgroup$
  • $\begingroup$ so, what is the easiest implementation exists for this? $\endgroup$ – Mayank Baiswar Jun 25 '18 at 18:01
  • $\begingroup$ @MayankBaiswar, try looking for an existing library that solves metric TSP (maybe TSPLIB?). $\endgroup$ – D.W. Jun 25 '18 at 18:35
  • $\begingroup$ I want to implement the solution myself using backtracking. at least for small cases. This is possible, right? $\endgroup$ – Mayank Baiswar Jun 26 '18 at 4:27
1
$\begingroup$

As D.W. mentioned, this is a version of the Travelling Salesman Problem.

TSP is (in general) NP-hard, which is unfortunate. For small enough numbers of points (10-ish) you could try all the permutations by brute force, but the $O(n!)$ complexity is nasty.

Since your method of computing the cost of travel is the $L_1$ metric (once again, as D.W. pointed out before me), you can use Christofides algorithm, which guarantees a $3\over 2$ approximation ratio.

Note that TSP is usually concerned with closed tours (source = destination), so you might need to make some modifications. This will be simple for the brute-force approach, but I'm not aware of an elegant modification for Christofides.

$\endgroup$
  • $\begingroup$ In the OP there are 6 points to be arranged. $6!$ is small - in fact, smaller than almost all natural numbers! $\endgroup$ – Reinstate Monica Jun 25 '18 at 20:10

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.