找不到群体匹配算法：90名学生分班最大化愉悦值问题求解思路

这个问题属于带约束的组合优化问题，本质等价于带权无向图的3划分问题，目标是将90个节点划分为3个子集，最大化子集内部的边权重总和，以下是几种不同复杂度的可行方案：

1. 精确求解方案（可得到全局最优解） #

你可以直接建立整数线性规划模型求解，建模逻辑如下：

• 决策变量：定义x[i,c]为0-1变量，取值为1时代表学生i被分到班级c（学生编号1_{90，班级编号1}3）
• 约束条件：
  • 每个学生只能属于一个班级：对任意学生i，满足sum(x[i,1], x[i,2], x[i,3]) = 1
  • 班级人数约束（默认均分3个班各30人，可根据实际要求调整）：对任意班级c，满足sum(x[1,c], x[2,c], ..., x[90,c]) = 30
• 目标函数：最大化全体总愉悦值，即对每个学生i的四个好友，按优先级权重计算同班的得分总和
  90个变量的规模极小，用任意开源求解器（如CBC、PuLP自带的求解器）或者商用求解器（Gurobi、CPLEX）都可以在几秒内得到全局最优解。

2. 启发式求解方案（实现简单，效果接近最优） #

如果不想引入专业求解器，用简单的启发式算法就能得到非常接近最优的结果：

• 模拟退火算法 #

  1. 初始化：随机把90个学生分到3个班，每个班30人，计算当前总愉悦值
  2. 迭代优化：每次随机挑选2个不同班级的学生，计算交换两人班级后的总愉悦值变化
  3. 接受规则：如果交换后得分提升就直接接受交换；如果得分下降，按随迭代次数降低的概率接受这个较差的交换，避免陷入局部最优
  4. 迭代足够多的次数后收敛，输出当前的分班方案
     这个方案代码实现不超过100行，90个学生的规模跑1万次迭代只需要几秒，最终结果和全局最优解的差距通常在1%以内。

• 多起点爬山法 #

  1. 随机生成N个初始分班方案（N建议取10~20）
  2. 对每个初始方案，不断尝试交换任意两个不同班的学生，只要交换能提升总得分就保留交换，直到没有可以提升得分的交换为止
  3. 从N个收敛后的方案中选得分最高的作为最终结果
     实现比模拟退火更简单，多跑几个初始点也能拿到很不错的结果。

3. 现成工具方案 #

这个问题完全匹配经典的图划分问题：把每个学生看作节点，两个学生之间的边权重设为两人同班时贡献的总得分之和（即A给B的权重加B给A的权重），目标是把图划分为3个大小相等的子图，最大化子图内部的边权重总和。你可以直接用开源图划分工具METIS，传入节点、边和权重参数，设置划分数量为3，一秒就能得到高质量的划分结果。

• 计算总愉悦值时可以提前预处理好所有两两学生的权重和，不用每次都遍历每个学生的好友列表，能大幅提升计算速度
• 如果没有强制要求班级人数完全相等，可以去掉人数约束，求解会更简单

内容的提问来源于stack exchange，提问作者qsan