给定平面上的n个点（n为偶数），是否有一种有效的算法来生成从每个点到全局距离最小的k个点的k（k例如，当N=4和k=2时，此optimal result优于此non-optimal result。
全局距离是连接距离的总和。节点不需要完全连接（孤岛可以）。
最佳答案
您描述的问题称为Graph Factorization，您要寻找的是图的最小成本k-匹配。您可以通过读取Richard P. Anstee, A polynomial algorithm for b-matchings: An alternative approach, 1987继续，它提供了一个强多项式时间算法来求解它。
关于algorithm - 最小化总距离，飞机上N个点各有k个链接，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/39920888/