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.
采纳的回答
Image Analyst
2016-12-2
0 个投票
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.
2 个评论
Pat90
2016-12-2
Image Analyst
2016-12-2
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/
更多回答（1 个）
Alan Weiss
2016-12-2
1 个投票
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
类别
在 帮助中心 和 File Exchange 中查找有关 Nearest Neighbors 的更多信息
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!
Translated by 
