爬山算法 × 模拟退火：教室排座工具的寻优之路

这个项目的起因是当班主任的朋友一句吐槽：「每次换座位都要权衡四十多个学生的关系，比写代码难多了」。我说：那就交给代码。

把愿望翻译成目标函数

寻优算法的第一步不是选算法，而是定义「好」。我们把老师的直觉拆成可计算的规则，每条规则一个权重：

function score(seats, rules) {
  let total = 0;
  for (const [a, b, w] of rules.pairs) {
    if (isNeighbor(seats, a, b)) total += w; // 想同桌 +w
  }
  return total - penalty(seats, rules.blocks);
}

爬山与退火

先试了最朴素的爬山法：随机交换两个学生，分数变高就接受。实现只要十几行，收敛飞快——但总停在「还行」的方案上。

模拟退火的洞察是：在高温阶段以概率接受更差的解，随温度下降，接受概率趋近于零。设新解与当前解的分数差为 $\Delta E$（越低越差），接受劣解的概率：

温度按几何日程衰减：$T_{k+1} = \alpha T_k$，本项目取 $\alpha = 0.95$、初始 $T_0 = 100$。同样是 3 秒预算，爬山法平均分 82，模拟退火 91，且方差明显更小。

工程上的取舍

上线一学期后，朋友的反馈是：「它给出的方案不总是我心里的最优，但从来不会离谱。」——对算法工程来说，这就是好评。