双参数差值约束下4列最大分组数求解算法设计

问题说明 #

现有26组二元数值元组，对应下表中26列数据，两行分别为各列对应的Parameter 1、Parameter 2取值，需要按规则完成分组，最终输出可划分的最大合法分组数量，以及所有分组包含的列集合。

分组规则 #

• 每个分组固定包含4列，不允许出现多列、少列的情况
• 合法分组必须同时满足两个阈值要求：
  • 组内所有列的Parameter 1取值最大差值 小于1
  • 组内所有列的Parameter 2取值最大差值 小于0.5
• 参考合法分组示例：列4、5、6、7满足上述要求，属于合法分组
• 划分目标：得到数量最多的合法分组，无法归入任何合法分组的列直接舍弃
• 已知该数据集最多可划分出6个合法分组，剩余2列无法分组，算法输出需要匹配该结果

算法思路 #

该问题属于固定规模子集的最大匹配问题，总数据量仅26列，用带剪枝的回溯搜索即可快速得到最优解，实现逻辑简单且不易出错：

• 预处理阶段：枚举所有可能的4列组合，提前校验每个组合是否满足两个参数的差值要求，将所有合法组合存入候选集，避免后续搜索过程中重复计算最大最小值，减少冗余计算
• 回溯搜索阶段：按列序号从小到大遍历，每一步有两种选择：
  • 跳过当前列，直接处理下一列
  • 如果当前列未被分组，从候选集中筛选出所有包含当前列、且组内其余3列均未被使用的合法组合，标记组内所有列为已使用，累加分组数后递归搜索后续列，递归完成后回溯状态
• 剪枝优化：如果当前已获得的分组数 + 剩余未处理列数//4（剩余列理论上能凑出的最大组数）小于当前已找到的最大分组数，直接终止当前分支搜索，避免无效遍历

代码实现（Python） #

from itertools import combinations

# 原始数据，索引i对应列号i+1
p1 = [22.95,23.46,22.71,23.41,23.36,23.18,23.52,23.35,22.86,22.47,
      22.63,23.72,23.22,23.17,22.8,23.18,23.15,23.12,23.16,23.22,
      23.58,23.68,23.33,23.52,23.54,23.48]
p2 = [19.97,20.83,19.22,20.39,20.33,20.44,20.62,20.26,21.22,20.31,
      20.53,20.62,20.65,20.14,19.43,20.66,20.09,20.52,20.41,20.63,
      20.98,21.15,19.97,20.72,20.71,20.32]
total_cols = 26

# 预处理所有合法4列组合
valid_candidates = []
for combo in combinations(range(total_cols), 4):
    group_p1 = [p1[i] for i in combo]
    group_p2 = [p2[i] for i in combo]
    if max(group_p1) - min(group_p1) < 1 and max(group_p2) - min(group_p2) < 0.5:
        valid_candidates.append(set(combo))

max_group_num = 0
best_groups = []
used_flag = [False] * total_cols

def backtrack(start_idx, current_count, current_groups):
    global max_group_num, best_groups
    # 剪枝：当前分支不可能得到更优解，直接返回
    if current_count + (total_cols - start_idx) // 4 <= max_group_num:
        return
    # 遍历到末尾，更新最优解
    if start_idx >= total_cols:
        if current_count > max_group_num:
            max_group_num = current_count
            best_groups = [sorted([i+1 for i in g]) for g in current_groups]
        return
    # 选择1：跳过当前列
    backtrack(start_idx + 1, current_count, current_groups)
    # 选择2：当前列未使用时，尝试选包含它的合法组
    if not used_flag[start_idx]:
        for group in valid_candidates:
            if start_idx in group and all(not used_flag[i] for i in group):
                # 标记占用
                for idx in group:
                    used_flag[idx] = True
                current_groups.append(group)
                backtrack(start_idx + 1, current_count + 1, current_groups)
                # 回溯状态
                current_groups.pop()
                for idx in group:
                    used_flag[idx] = False

backtrack(0, 0, [])

# 输出结果
print(f"最大合法分组数量：{max_group_num}")
print("各分组列号：")
for idx, g in enumerate(best_groups, 1):
    print(f"第{idx}组：{g}")

运行结果 #

代码执行后输出结果与已知结论完全匹配：

• 最大合法分组数量：6，累计覆盖24列，剩余2列无法满足分组规则被舍弃
• 输出的分组集合包含题目给出的示例分组（列4、5、6、7），所有分组均满足两项参数的差值约束

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