基于R语言的好友组内最优饼干分配方案实现咨询

一、基础实现思路与代码框架 #

先从易落地的贪心逻辑入手，结合你已有的邻居总饼干计算函数，核心是优先处理饼干不足的用户，从近邻开始尝试合并，直到满足约束。以下是可直接扩展的代码框架（假设你已用igraph生成好友网络图g，饼干数据存储在命名向量cookies中，names(cookies)对应用户ID）：

library(igraph)

# 初始化变量：存储分组结果、标记已使用用户
group_list <- list()
used_users <- character(0)

# 按饼干数升序遍历用户（优先处理最缺饼干的，避免后期无法合并）
sorted_users <- names(cookies)[order(cookies)]

for (user in setdiff(sorted_users, used_users)) {
  # 单个用户已满足条件，直接单独成组
  if (cookies[user] >= 12) {
    group_list[[length(group_list) + 1]] <- user
    used_users <- c(used_users, user)
    next
  }

  current_group <- user
  total_cookies <- cookies[user]
  degree <- 1

  # 从1度邻居开始尝试合并，直到满足下限或遍历到3度邻居（避免过度搜索）
  while (total_cookies < 12 && degree <= 3) {
    # 获取当前度数的未使用邻居，按饼干数从小到大排序（优先加饼干少的，避免总和超上限）
    neighbors_degree <- neighbors(g, user, order = degree) %>% as.character()
    neighbors_degree <- setdiff(neighbors_degree, used_users)
    neighbors_degree <- neighbors_degree[order(cookies[neighbors_degree])]

    # 逐个尝试添加邻居
    for (n in neighbors_degree) {
      if (total_cookies + cookies[n] <= 20) {
        current_group <- c(current_group, n)
        total_cookies <- total_cookies + cookies[n]
        if (total_cookies >= 12) break
      }
    }

    if (total_cookies >= 12) break
    degree <- degree + 1
  }

  # 验证合并后的组是否符合约束，符合则记录
  if (total_cookies >= 12 && total_cookies <= 20) {
    group_list[[length(group_list) + 1]] <- current_group
    used_users <- c(used_users, current_group)
  } else {
    warning(paste("用户", user, "无法找到符合条件的合并组合，请检查数据或调整搜索度数"))
  }
}

# 输出最终分组
print(group_list)

二、能否使用动态规划？ #

不适合用标准动态规划，原因如下：

• 问题不满足动态规划的核心前提：无后效性。用户的分组选择会直接影响其邻居的可用状态，子问题之间高度依赖。
• 状态空间爆炸：100个用户的状态组合数为2^100，完全无法计算。
  如果硬要尝试，只能针对极小的局部连通子图做动态规划，但实际落地价值极低，远不如贪心或启发式算法实用。

三、进阶算法实现与适配 #

1. 贪心算法优化 #

基础贪心可从两个方向优化：

• 合并策略优化：在满足≥12的前提下，优先选择能让组总和最接近20的邻居组合，减少资源浪费。
• 处理顺序优化：按用户饼干数升序处理，优先解决最容易出现合并困难的低饼干用户。

2. 遗传算法实现 #

遗传算法适合这类带约束的组合优化问题，核心是通过模拟进化找到最优分组：

library(GA)

# 适应度函数：惩罚违反约束的情况，奖励符合约束且总和接近20的分组
fitness_func <- function(individual) {
  score <- 0
  groups <- split(names(cookies), individual)
  
  for (group in groups) {
    total <- sum(cookies[group])
    if (total < 12) score <- score - 100  # 惩罚未达下限
    if (total > 20) score <- score - 100  # 惩罚超出上限
    score <- score + (20 - abs(total - 20))  # 奖励总和接近20
  }
  return(score)
}

# 运行遗传算法：整数编码表示用户所属组ID
ga_result <- ga(
  type = "integer",
  fitness = fitness_func,
  lower = rep(1, 100),  # 最小组ID
  upper = rep(50, 100), # 最大组ID（假设最多50个组）
  popSize = 50,
  maxiter = 100
)

# 提取最优分组
best_groups <- split(names(cookies), ga_result@solution[1,])

3. Louvain社区检测适配 #

Louvain算法本身是最大化模块度，无法直接满足你的约束，但可以先得到初始社区，再调整至符合要求：

# 第一步：用Louvain得到初始社区
louvain_comm <- cluster_louvain(g)
initial_groups <- split(names(cookies), membership(louvain_comm))

adjusted_groups <- list()
used_users <- character(0)

# 第二步：调整初始社区
for (group in initial_groups) {
  total <- sum(cookies[group])
  
  # 已符合约束，直接保留
  if (total >= 12 && total <= 20) {
    adjusted_groups[[length(adjusted_groups) + 1]] <- group
    used_users <- c(used_users, group)
    next
  }
  
  # 总和超20：贪心拆分出符合约束的子集
  if (total > 20) {
    remaining <- group
    while (length(remaining) > 0) {
      subset <- character(0)
      sub_total <- 0
      for (u in remaining) {
        if (sub_total + cookies[u] <= 20) {
          subset <- c(subset, u)
          sub_total <- sub_total + cookies[u]
          if (sub_total >= 12) break
        }
      }
      adjusted_groups[[length(adjusted_groups) + 1]] <- subset
      remaining <- setdiff(remaining, subset)
    }
  }
  
  # 总和<12：寻找相邻未使用社区合并
  if (total < 12) {
    # 获取当前组的邻居用户，找到对应的未处理社区
    neighbor_users <- unique(unlist(neighbors(g, group)))
    neighbor_groups <- Filter(function(g) any(g %in% neighbor_users), adjusted_groups)
    
    # 找到第一个可合并后符合约束的社区
    for (ng in neighbor_groups) {
      if (sum(cookies[c(group, ng)]) <= 20) {
        idx <- which(sapply(adjusted_groups, function(x) all(x == ng)))
        adjusted_groups[[idx]] <- c(group, ng)
        used_users <- c(used_users, group)
        break
      }
    }
  }
}

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