Find Minimum Difference between consecutive values by reordering

Hello, I just have a question where I cannot get my head around. Let's say I do have a Matrix containing the x and y coordinates of points. The coordinates as well as the order are random. So the dimension of the Matrix is [Number of Points,2]. What I would like to do is reorder this matrix under the constraint that the distance between subsequent points is minimum. Up to now I calculated the difference between subsequent points. However I have no idea how to find the optimal reordering to achieve the minimum distance between subsequent coordinates. Also my starting point is fixed to a specific value. Hopefully this is clear to you. I would be extremely grateful if any of you guys does have an idea how to tackle this problem. Thank you so much in advance.

[per isakson]

See Pairwise Distance Matrix

Answer 1

[Image Analyst]

There is a function in the Statistics and Machine Learning Toolbox that can give you the distance of every point to every other point. It's called pdist2(). You can then sort the distances. However I agree with Alan that it's more like a TSP problem. With pdist2() you might find point 3 and 24 have the shortest distance, but points 14 and 38 have the next shortest distance. But you can't just go in the order 2,24,14,38 because the distance from 24 to 14 might be really long, so your final path constructed that way won't necessarily be the shortest of all possible paths, in fact it almost certainly won't be. So you need some kind of heuristic thing like TSP or A*, the Floyd Washall alogrithm, or similar algorithms. There is tons of stuff on Wikipedia about all kinds of flavors of shortest path algorithms. One place to start is here.

[Pat90]

Thank you very much and also for your extensive explanation. This helped a lot! I will look into the TSP.

[Image Analyst]

Pat, if you can turn your points into an image, you can use bwgeodesic(). See Steve's 5 part blog series on the topic: http://blogs.mathworks.com/steve/2011/11/01/exploring-shortest-paths-part-1/

Answer 2

[Alan Weiss]

I think that this might be the Travelling Salesman Problem. I mean, you say that you want to minimize each individual distance, but maybe you want to minimize the total distance.

Alan Weiss

MATLAB mathematical toolbox documentation

[Pat90]

Thank you! It is exactly like that I will have a look into it!