CODEWITHSUNDEEP
algorithmcoordinatesdistance
Sankalp
Sankalp

Reputation: 2824

Least cumulative distance for plotter to plot 'n' points

There is given a plotter which can plot points provided to it in the form of 'x' and 'y' coordinates. The plotter hand can move horizontally or vertically only. Input will be provided in the form of a list of 'n' coordinates: {(x1,y1), (x2,y2} ... (xn,yn)}. Initially, the plotter would be at origin.

It's required to provide an algo to return a list of all 'n' points that would represent the least cumulative distance for the plotter hand to plot all 'n' points in the exact order provided in the output list.

With some initial reminisce, I am tempted to think that the output would a list of 'n' points sorted with increasing 'x' and 'y' co-ordinates.

For instance,

Input- (3, 5), (1, 2), (4, 3)

Output- (1, 2), (3, 5), (4, 3)

But, I am afraid that this would be the correct algorithm.

So, the question is: derive an algorithm to solve this problem and if the above is correct, then prove it.

Also, what changes will the derived algorithm observe if the plotter were also allowed to move diagonally!

Upvotes: 1

Views: 160

Answers (2)

Patricia Shanahan
Patricia Shanahan

Reputation: 26185

This problem is an NP-hard variant of the Traveling Salesman Problem, so exact solution is practical only for small problems. See Traveling Salesman Problem for a general description. Software has links to some programs that may be helpful.

Upvotes: 2

Antti Huima
Antti Huima

Reputation: 25522

As Patricia already wrote in her comment, this is equivalent to the metric Traveling Salesman problem with Manhattan distance. It is an NP-complete optimization problem and is best solved with an approximation or heuristic algorithm for real-life problems (say more than 10 points to plot). Any deterministic algorithm that always produces an optimal solution is likely going to scale extremely badly to larger problem sizes.

Upvotes: 0

Related Questions