use*_*275 5 algorithm matching bipartite
我有K组数据点,我想制作大小为K的组,以最小化组内距离的总和.我熟悉匹配算法与二分图,但我想这两个以上.
有任何想法吗？
编辑:
每组将由每组中的一个元素组成,不允许重复.
例如:你有{a1,a2,a3},{b1,b2,b3},{c1,c2,c3}你想创建组,例如{a1,b3,c3},{a2,b1,c2}, {a3,b2,c1}最小化组内距离的总和.
即使对于 k=3，它也具有 NP 困难问题 3 维匹配的味道。（明显的减少不起作用，因为可能会创建幻影三元组，其中无效三元组的三对中的每一对单独出现在有效三元组中。）
根据实例的大小，我会尝试本地搜索或使用列生成进行整数编程（但如果没有低维度量空间的结构，内部问题似乎很困难，而且即使如此也很重要）。