algorithm - 基于好恶匹配人的算法

我有一个大约 75 人的团队。每个用户都喜欢或不喜欢其他 74 个用户。这些人需要分成大约 15 个不同大小的组（4 到 8 人）。需要将它们分组在一起，以便这些组仅由彼此喜欢的人组成，或者至少由彼此喜欢的人组成。

我不确定解决这个问题的最佳算法是什么。非常感谢任何指针或伪代码！

标签： algorithm

这还不够好，不足以建议特定的算法。我建议使用聚类和“集团”算法，但您仍然需要定义“最佳分组”指标。面对取舍和未定义的欲望，“尽可能地”是没有意义的。您的聚类算法将需要此指标来形成您的组。

数据表示很简单：你需要一个有向图。从 A 到 B 的边表示 A 喜欢 B；缺少优势意味着 A 不喜欢 B。这会将“喜欢”信息编码为适合您的算法的形式。您有 75 个节点和每个“喜欢”的一条边。

从研究派系算法开始；“集团”是一个集合，其中每个成员都喜欢其他每个成员。这些可能会构成您的聚类的基础。

但是请注意，您必须定义权衡取舍。例如，考虑 13 个节点的情况，其中包括 4 人和 8 人的两个不同的小团体，加上一个喜欢 8 小团体中的一名成员的人。图中没有其他“喜欢”。

你如何安置第 13 个人？您是否拆分 8 派系并将他们与他们喜欢的人一起添加到组中？如果是这样，您是否将 3 或 4 人从 8 人中拆分出来？打破 15 或 16 个“喜欢”，让那个人和他们喜欢的人在一起——谁不喜欢他们？公平吗？将第 13 个人添加到相互对立的 4 集团中会更好吗？

您的 eval 函数必须为所有这些情况返回一个有序的度量。它将需要支持添加到一个组，拆分一个大组等。