我说，我已经做了我的数据集集群和有10个集群。 这些簇是不重叠的。 但现在假设我改变了我的所有数据点的一些特点，也再次聚集。 现在我有10多个集群。 如果我再说一遍说3次以上，最后我将有50个集群。 每个集群具有与其相关联的分值，其从它的成分的数据点来计算。
这些簇50现在具有重叠的数据点。 我想选择所有可能的非重叠的集群这些50个集群但总分最高。
一种方法是我根据得分从最高到最小集群排序贪心方法。 然后，选择得分最高的集群。 然后从那里保持选择具有与已经选择的集群非重叠的数据点簇。 但它似乎并没有成为最佳的解决方案，虽然它的速度很快。
例如：说我有5个簇具有以下成绩：
C1 =（A，B，C，d，E，F）得分= 10
C2 =（A，B，C）得分= 6
C3 =（d，E，F）得分= 6
C4 =（G，H，I，J）得分= 5
C5 =（K，L）分数= 7
贪婪方法将返回{C1，C4，C5}为10 + 5 + 7 = 22的总成绩，而更好的选择是{C2，C3，C4，C5}，总得分6 + 6 + 5 + 7 = 24。
我在寻找一个可以给除上述贪婪方法的最佳解决方案或更好的解决方案的另一种方法。
你可以解决这个使用运筹学技术。
模拟这个问题就像一个集分割问题
Objective function: maximize score
Constraints: each data point is covered exactly once
然后使用解算器MIP或任何其它技术解决它（如山登山，遗传算法等）。 你的问题的规模非常小，因此可以解决任何优化算法。 我也正在研究类似的问题，但在航空公司机组人员调度域。 我的问题的规模是如此巨大，可能的船员安排（相当于你的集群）是>为〜4500个航班航班调度数不胜数的组合（相当于你的数据点）;）
我已经编写你的例子在Python和我用从Gurobi一个MIP求解器，提供免费学术使用成本。 您可以使用其他MIP求解器了。
下面是Python代码：
from gurobipy import *
import string
data_points = string.ascii_uppercase[:12]
clusters = []
clusters.append(string.ascii_uppercase[:6])
clusters.append(string.ascii_uppercase[:3])
clusters.append(string.ascii_uppercase[3:6])
clusters.append(string.ascii_uppercase[6:10])
clusters.append(string.ascii_uppercase[10:12])
matrix = {}
for dp in string.ascii_uppercase[:12]:
matrix[dp] = [0]*5
for i in range(0, len(clusters)):
for dp in clusters[i]:
matrix[dp][i] = 1
cost = [10, 6, 6, 5, 7]
# Gurobi MIP model
m = Model("Jitin's cluster optimization problem")
m.params.outputflag = 1
x = m.addVars(len(clusters), vtype=GRB.INTEGER, name='x')
indices = range(0, len(clusters))
coef_x = dict()
obj = 0.0
for i in indices:
coef_x[i] = cost[i]
obj += coef_x[i] * x[i]
m.setObjective(obj, GRB.MAXIMIZE)
flight_in_pairings = [[] for i in range(0, 4228)]
for dp,j in zip(data_points, range(0, len(data_points))):
m.addConstr(sum([x[i]*matrix[dp][i] for i in range(0, len(matrix[dp]))]) == 1, "C"+str(j))
m.optimize()
print('Final Obj:', m.objVal)
m.write('results.sol')
代码的输出：
# Solution for model Jitin's cluster optimization problem
# Objective value = 24
x[0] 0
x[1] 1
x[2] 1
x[3] 1
x[4] 1
