Hi forum! A fun challenge for you guys. How do you find a pair of closest points, without producing sub optimal results?
A point can be used only once to create a pair.
Correct solution, it computes distances to all points within max distance, and uses 2opt to solve sub optimal cases. But i am not 100% sure its fully correct, and it is exponentially slower with amount of points.
I know the best approach would probably be to use delaunay connectivity for candidate pairs, and blossom method on top of it, but i do not know how to implement blossom algorithm.
Hi Jospeh, thank you for your attempt!
I made those components instead of original ones, because they work a lot faster when i needed to make few thousand points. Standard components do not populate completely randomly, they populate in a way that avoids cluttering points too close together, i do not need that for this example.
The problem on your screenshot is the exact suboptimal case, because the algorithm does not see “the whole picture”, it is left with those lonely points in the end, that connect together because they have no choice, even though they are clearly not a match for each other.
It was a mistake, the algorithm in the post uses 2 opt refinement, not hungarian matrix (it was my previous attempt). It finds a list of candidates for each point within a max distance, and swaps used points until it gets the shortest solution.
nice attempt - you find candidates in a range of distances to the point, take the first one and delete it from initial set. the limitation is that you need a loop within a loop to store and later compare those candidates for optimization. And that is what implemented in the c# in the original post.. Or you can record all candidates instead of one, and compare the branches somehow..
