基于Social Golfer Problem实现师生分组与任务均衡分配的技术问询

核心思路 #

你的问题是**Social Golfer Problem（社交高尔夫球手问题）**的扩展，需要同时满足「同组次数均匀」和「任务分配次数均匀」两个约束。最优解法是先生成满足同组均匀性的分组方案，再叠加任务分配的均匀性优化，而非同时解决两个问题。

算法步骤提示 #

1. 生成满足同组均匀性的分组 #

针对总人数n、每组人数m、天数z：

• 循环置换法（推荐）：当n能被m整除（即组数k = n/m）时，用循环移位生成分组，能保证每人与其他成员同组的次数尽可能一致。例如：
  • 第1天分组：[1-3], [4-6], [7-9], [10-12]（n=12, m=3）
  • 第2天分组：[2-4], [5-7], [8-10], [11-1]（每个成员循环后移一位）
  • 以此类推，直到完成z天的分组
• 回溯/贪心算法：如果人数不满足整除条件，用回溯法尝试所有可能的分组组合（适合小规模场景），或用贪心算法优先将同组次数最少的成员分到一组（适合大规模场景）。

2. 叠加任务分配的均匀性优化 #

假设任务总数为t，需保证每人每项任务的执行次数尽可能接近z/t：

• 贪心分配法：每天为每个组选择任务时，优先选该组所有成员执行次数总和最少的任务，确保组内成员的任务次数均衡。
• 循环任务置换：如果分组是循环生成的，可同步循环任务分配（第1天组1→任务A，组2→任务B；第2天组1→任务B，组2→任务C...），这种方式能天然保证任务次数均匀。
• 局部优化调整：生成初始方案后，计算「任务次数方差」和「同组次数方差」，通过随机交换两组的任务或交换组内成员，迭代降低方差，直到满足均匀性要求。

C#实现框架 #

基础数据结构定义 #

public class Person
{
    public int Id { get; set; }
    // key: 其他人员ID, value: 同组次数
    public Dictionary<int, int> PartnerCount { get; set; } = new();
    // key: 任务ID, value: 执行次数
    public Dictionary<int, int> TaskCount { get; set; } = new();
}

public class Group
{
    public List<Person> Members { get; set; } = new();
    public int AssignedTaskId { get; set; }
}

public class DailySchedule
{
    public List<Group> DailyGroups { get; set; } = new();
}

循环置换法生成分组 #

public List<DailySchedule> GenerateGolferGroups(int totalPeople, int groupSize, int days)
{
    var schedules = new List<DailySchedule>();
    var people = Enumerable.Range(1, totalPeople)
                           .Select(id => new Person { Id = id })
                           .ToList();
    int groupCount = totalPeople / groupSize;

    for (int day = 0; day < days; day++)
    {
        var daily = new DailySchedule();
        for (int groupIdx = 0; groupIdx < groupCount; groupIdx++)
        {
            var group = new Group();
            // 循环移位计算当前组成员索引
            for (int memberIdx = 0; memberIdx < groupSize; memberIdx++)
            {
                int personIndex = (day + groupIdx * groupSize + memberIdx) % totalPeople;
                group.Members.Add(people[personIndex]);
            }
            daily.DailyGroups.Add(group);
        }
        schedules.Add(daily);
        // 更新同组次数统计
        UpdatePartnerCounts(daily);
    }
    return schedules;
}

private void UpdatePartnerCounts(DailySchedule daily)
{
    foreach (var group in daily.DailyGroups)
    {
        foreach (var p1 in group.Members)
        {
            foreach (var p2 in group.Members)
            {
                if (p1.Id == p2.Id) continue;
                p1.PartnerCount.TryAdd(p2.Id, 0);
                p1.PartnerCount[p2.Id]++;
            }
        }
    }
}

贪心任务分配 #

public void AssignTasks(List<DailySchedule> schedules, int totalTasks)
{
    foreach (var daily in schedules)
    {
        foreach (var group in daily.DailyGroups)
        {
            int bestTask = -1;
            int minTotalCount = int.MaxValue;
            // 遍历所有任务，选组内成员执行次数总和最少的
            for (int taskId = 1; taskId <= totalTasks; taskId++)
            {
                int total = group.Members.Sum(p => p.TaskCount.GetValueOrDefault(taskId, 0));
                if (total < minTotalCount)
                {
                    minTotalCount = total;
                    bestTask = taskId;
                }
            }
            group.AssignedTaskId = bestTask;
            // 更新成员任务次数
            foreach (var person in group.Members)
            {
                person.TaskCount.TryAdd(bestTask, 0);
                person.TaskCount[bestTask]++;
            }
        }
    }
}

局部优化调整（降低方差） #

private double CalculateTaskVariance(List<Person> people, int totalTasks)
{
    var allTaskCounts = new List<int>();
    foreach (var person in people)
    {
        for (int taskId = 1; taskId <= totalTasks; taskId++)
        {
            allTaskCounts.Add(person.TaskCount.GetValueOrDefault(taskId, 0));
        }
    }
    double avg = allTaskCounts.Average();
    return allTaskCounts.Sum(x => Math.Pow(x - avg, 2)) / allTaskCounts.Count;
}

public void OptimizeTaskAssignments(List<DailySchedule> schedules, int totalTasks)
{
    var allPeople = schedules.SelectMany(d => d.DailyGroups)
                             .SelectMany(g => g.Members)
                             .Distinct()
                             .ToList();
    double currentVariance = CalculateTaskVariance(allPeople, totalTasks);
    Random rand = new Random();
    bool improved;

    do
    {
        improved = false;
        // 随机选择两天的两组进行任务交换
        int day1 = rand.Next(schedules.Count);
        int day2 = rand.Next(schedules.Count);
        if (day1 == day2) continue;

        int groupIdx1 = rand.Next(schedules[day1].DailyGroups.Count);
        int groupIdx2 = rand.Next(schedules[day2].DailyGroups.Count);

        var group1 = schedules[day1].DailyGroups[groupIdx1];
        var group2 = schedules[day2].DailyGroups[groupIdx2];
        int task1 = group1.AssignedTaskId;
        int task2 = group2.AssignedTaskId;

        // 交换任务并更新计数
        group1.AssignedTaskId = task2;
        group2.AssignedTaskId = task1;
        UpdateTaskCounts(group1, task1, -1);
        UpdateTaskCounts(group1, task2, 1);
        UpdateTaskCounts(group2, task2, -1);
        UpdateTaskCounts(group2, task1, 1);

        double newVariance = CalculateTaskVariance(allPeople, totalTasks);
        if (newVariance < currentVariance)
        {
            currentVariance = newVariance;
            improved = true;
        }
        else
        {
            // 恢复原任务分配
            group1.AssignedTaskId = task1;
            group2.AssignedTaskId = task2;
            UpdateTaskCounts(group1, task1, 1);
            UpdateTaskCounts(group1, task2, -1);
            UpdateTaskCounts(group2, task2, 1);
            UpdateTaskCounts(group2, task1, -1);
        }
    } while (improved);
}

private void UpdateTaskCounts(Group group, int taskId, int delta)
{
    foreach (var person in group.Members)
    {
        person.TaskCount[taskId] += delta;
    }
}

注意事项 #

• 循环置换法仅适用于人数能被每组人数整除的场景，若不满足，需改用贪心或回溯算法生成近似分组方案。
• 若要求严格均匀的任务次数，需保证z * m能被totalTasks整除（即每人每项任务次数为z*m / totalTasks），否则只能得到近似均匀的结果。
• 对于大规模场景（人数>50），建议放弃回溯法，改用启发式贪心算法+局部优化，平衡计算效率和结果均匀性。

内容的提问来源于stack exchange，提问作者Meister der Magie