非相交线段，同时最小化累积长度
我想find一个更好的algorithm来解决以下问题：
2D中有N个起点（紫色）和N个目标点（绿色）。 我想要一个algorithm，通过一个线段（棕色）连接起点到目标点，而没有任何这些线段相交（红色），同时最小化所有线段的累积长度。
我在C ++中的第一次努力是排列所有可能的状态，find无交叉状态，并且在那些最小总长度为O（n！）的状态中 。 但我认为还有更好的办法。
任何想法？ 或者用于search的好关键字？
这是2D中的最小欧几里德匹配 。 该链接包含有关此问题的已知信息的参考书目。 考虑到要最小化总长度，非交叉约束是多余的，因为交叉的任何一对分段的长度可以通过不交叉来减less。
您可以select随机连接，然后每次删除一个十字（实际上改变它们的端点的连接），该algorithm工作并以有限的步骤完成。 可能是你说换十字造成新的十字，不pipe怎么说，每次换一个十字，你都要尽量减less你答案的总长度，这种方式不能是无限的（因为线的总长度是有限的）。 实际上在O（F * n ^ 2）中工作，其中F= sum of all line segments * power of 10 （使其为整数）。 这个O很乐观，我想如果你尝试这个简单的algorithm，它会正常工作。 一般来说，这肯定比蛮力更好。
看起来像你可以使用BSPtypes的algorithm。
按照O（n 3 ）的顺序使用此algorithm：
匈牙利algorithm是解决多项式时间分配问题的组合优化algorithm。
它如何帮助？ 那么，它会find最小的累计长度。 但…
当总长度最小时，没有交叉。
因此，@ qq3表示交集约束是多余的，并且在消除这个约束之后，它可以减less从O（n！）到O（n 3 ）的顺序。
