寻求最小化组内Mean absolute deviation的通用分组算法

问题背景 #

给定一组按weight排序的关联cost数据（weight与cost无直接决定关系），需将其划分为指定数量（示例场景为7组，需通用方案）的weight区间分组，满足以下要求：

• 最小化所有组内cost的**平均绝对偏差（Mean Absolute Deviation, MAD）**总和
• 每组不能仅含单个成员，且组内成员的cost不能完全相同

示例：将数据集分为两组时，最优分组为{15,17}和{23,24,31,37}

现有算法困境 #

初步采用的启发式算法思路：

1. 先创建任意初始分组
2. 检查各组间的分界点，判断调整分界点是否能显著降低总MAD（设置最小降幅阈值）
3. 若无法调整或出现重复调整，则固定该分界点

但该算法存在以下问题：

• 当cost相似度较高时，易陷入局部最优停滞
• 倾向生成少量小分组，不确定是测试数据集特性还是算法固有缺陷

优化方案 #

1. 改进初始分组策略，避免偏向性 #

抛弃随机初始分组，改用均匀分段初始化：

• 按weight排序后的总数据量，平均分配到指定组数中作为初始分组
• 若无法平均分配，将剩余数据依次追加到前几个组，保证初始分组的规模相对均衡，避免一开始就出现小分组

2. 引入多轮随机重启+邻域搜索突破局部最优 #

• 当单次搜索陷入停滞时，随机重置1-2个分界点的位置，重新开始邻域搜索
• 每次重启后记录当前最优的总MAD值，保留全局最优解，避免被局部最优困住

3. 调整分界点的评估逻辑，细化优化方向 #

• 不再仅评估单个分界点的左右移动，而是同时考虑相邻两个分界点的联动调整：比如将组A的尾部元素移到组B，同时将组B的尾部元素移到组C，评估这种联动操作对总MAD的影响
• 取消固定的最小降幅阈值，改为动态阈值：根据当前总MAD的大小，设置相对降幅（比如要求降幅达到当前总MAD的0.5%），避免因cost相似度高导致的微小变化被忽略

4. 增加分组约束的前置检查 #

• 在每次调整分界点前，先预判调整后是否会出现单成员组或全相同cost组，若会则直接跳过该调整方案
• 可以预先计算所有连续子序列的cost MAD值，存储为二维数组，后续调整时直接查表，提升计算效率

5. 采用模拟退火算法跳出局部最优 #

• 引入模拟退火的概率接受机制：即使某次调整会导致总MAD上升，也以一定概率接受该调整，避免过早收敛到局部最优
• 随着迭代次数增加，逐渐降低接受劣解的概率，最终收敛到全局最优附近

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