World's most popular travel blog for travel bloggers.

[Solved]: Minimising sum of consecutive points distances Manhattan metric

, , No Comments
Problem Detail: 

I have two sets $X$ and $Y$ of 2-dimensional points. The points are floating point numbers. The objective is to sort them in such way that sum of differences in distances of consecutive sorted points is minimal.

I tried to solve this problem by localisation (dividing the plane by smaller grids of sorted points) and then connecting clusters - but this is a greedy and an approximate approach - the problem here is in setting grid size, but this is not guaranteed to give any bounds on how optimal the solution is, and it is rather time consuming (without a well-defined objective function).

Another attempt was to sort them by the x-coordinate, then find the minimum. But this approach fails. Normal sorting by two coordinates fails and is highly unstable.

The problem resembles the TSP problem, but the "path" is not closed and metric used is L1 (Manhattan, TaxiCab).

The solution I am looking for will probably be approximate. Finding the minimal and the second minimal distance from every point and connecting them gives good but for sure not minimal sum.

The problem I am having is with giving the objective function.

Asked By : Evil

Answered By : Evil

It turns out that it is indeed the Traveling Salesman Path Problem (TSPP). There are well suited approximation algorithms:

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/45823

3.2K people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback