最大化一系列值的组合
Maximizing a combination of a series of values
这是一个复杂的问题，但我怀疑我可以应用一些原则来使它变得简单——我只是不知道它是什么。
我需要为本学期的 class 学生分配演示时段。有多个可能的日期和多种演示类型。我进行了一项调查，学生可以对他们对不同主题的兴趣进行排名。我想做的是为学生分配最好的（或至少是好的）演示时段。
所以，我有：
- 12 个日期列表
- 18 名学生名单
- CSV 文件，其中每个学生（行）每个日期的评分为 1-5
我想得到什么：
- 每个学生应该有一个演示类型 A (
intro)，一个演示类型 B (figures) 和 3 个演示类型 C (aims)
- 每个日期应该至少有每种类型的演示
- 每个日期不应超过 2 个类型 A 或类型 B
- 尝试向学生展示他们评价很高（4 或 5）的演讲
我应该指出，我意识到这看起来像是一道家庭作业题，但这是现实生活:-)。我想我可以为每个学生制作一个 Student class，其中包含每种演示类型的日期，但我不确定填充它的最佳方式是什么。实际上，我什至不确定从哪里开始。
TL;DR：我认为你给了学生太多选择 :D
但我还是尝试解决了这个问题。实际上非常有趣的练习，尽管有些限制有点模糊。最重要的是，我不得不猜测实际学生的偏好分布是什么样的。我选择了均匀分布的独立变量，尽管这可能不太现实。我仍然认为它在真实数据上的效果应该和在随机生成的数据上一样好。
我考虑过暴力破解，但粗略的分析让我估计有超过 10^65 种可能的配置。那是很多。由于我们没有万亿年的时间来考虑所有这些问题，因此我们需要一种启发式方法。
由于问题的规模，我尽量避免做任何回溯。但这意味着您可能会陷入困境；可能没有解决方案，每个人都只得到他们给出的 4 和 5 的日期。
我最终实施了一个类似于 double-edged Iterative Deepening 的搜索，其中 最佳 情况我们仍然抱有希望（即，将学生分配到他们给 5 分的日期，我们愿意接受的 最坏 案例场景（有些学生可能不得不接受 3 分）逐渐降低，直到找到解决方案.如果我们卡住了，重新设定，降低期望，然后再试一次。先分配任务A和B，A和B完成后才做C，因为C的约束远没有那么严格。
我还使用了一个加权因子来模拟最大化学生幸福感与满足 types-of-presentations-per-day 限制之间的权衡。
目前它似乎为几乎所有随机生成的首选项集找到了解决方案。我包括了一个评估指标；所有指定 student/date 组合的偏好值总和与所有学生 ideal/top 3 偏好值总和之间的比率。例如，如果学生 X 在他的列表中有两个 5、一个 4 和其余的 3，并且分配给他的 1 个 5 和 2 个 3，他得到 5+3+3=11，但理想情况下本可以得到 5+5+ 4=14；他的满意度为 11/14 = 78.6%。
经过一些测试，我的实施似乎倾向于产生大约 95% 的平均学生满意度，比我预期的要好很多 :) 但同样，这是使用假数据。真正的偏好可能更集中，更难满足。
下面是算法的核心部分。完整的脚本大约有 250 行，我认为这里有点太长了。检查一下 at Github。
...
# Assign a date for a given task to each student,
# preferring a date that they like and is still free.
def fill(task, lowest_acceptable, spread_weight=0.1, tasks_to_spread="ABC"):
random_order = range(nStudents) # randomize student order, so everyone
random.shuffle(random_order) # has an equal chance to get their first pick
for i in random_order:
student = students[i]
if student.dates[task]: # student is already assigned for this task?
continue
# get available dates ordered by preference and how fully booked they are
preferred = get_favorite_day(student, lowest_acceptable,
spread_weight, tasks_to_spread)
for date_nr in preferred:
date = dates[date_nr]
if date.is_available(task, student.count, lowest_acceptable == 1):
date.set_student(task, student.count)
student.dates[task] = date
break
# attempt to "fill()" the schedule while gradually lowering expectations
start_at = 5
while start_at > 1:
lowest_acceptable = start_at
while lowest_acceptable > 0:
fill("A", lowest_acceptable, spread_weight, "AAB")
fill("B", lowest_acceptable, spread_weight, "ABB")
if lowest_acceptable == 1:
fill("C", lowest_acceptable, spread_weight_C, "C")
lowest_acceptable -= 1
这是脚本打印的示例结果：
Date
================================================================================
Student | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
================================================================================
1 | | A | B | | C | | | | | | | |
2 | | | | | A | | | | | B | C | |
3 | | | | | B | | | C | | A | | |
4 | | | | A | | C | | | | | | B |
5 | | | C | | | | A | B | | | | |
6 | | C | | | | | | | A | B | | |
7 | | | C | | | | | B | | | | A |
8 | | | A | | C | | B | | | | | |
9 | C | | | | | | | | A | | | B |
10 | A | B | | | | | | | C | | | |
11 | B | | | A | | C | | | | | | |
12 | | | | | | A | C | | | | B | |
13 | A | | | B | | | | | | | | C |
14 | | | | | B | | | | C | | A | |
15 | | | A | C | | B | | | | | | |
16 | | | | | | A | | | | C | B | |
17 | | A | | C | | | B | | | | | |
18 | | | | | | | C | A | B | | | |
================================================================================
Total student satisfaction: 250/261 = 95.00%
这是一个复杂的问题，但我怀疑我可以应用一些原则来使它变得简单——我只是不知道它是什么。
我需要为本学期的 class 学生分配演示时段。有多个可能的日期和多种演示类型。我进行了一项调查，学生可以对他们对不同主题的兴趣进行排名。我想做的是为学生分配最好的（或至少是好的）演示时段。
所以，我有：
- 12 个日期列表
- 18 名学生名单
- CSV 文件，其中每个学生（行）每个日期的评分为 1-5
我想得到什么：
- 每个学生应该有一个演示类型 A (
intro)，一个演示类型 B (figures) 和 3 个演示类型 C (aims) - 每个日期应该至少有每种类型的演示
- 每个日期不应超过 2 个类型 A 或类型 B
- 尝试向学生展示他们评价很高（4 或 5）的演讲
我应该指出，我意识到这看起来像是一道家庭作业题，但这是现实生活:-)。我想我可以为每个学生制作一个 Student class，其中包含每种演示类型的日期，但我不确定填充它的最佳方式是什么。实际上，我什至不确定从哪里开始。
TL;DR：我认为你给了学生太多选择 :D
但我还是尝试解决了这个问题。实际上非常有趣的练习，尽管有些限制有点模糊。最重要的是，我不得不猜测实际学生的偏好分布是什么样的。我选择了均匀分布的独立变量，尽管这可能不太现实。我仍然认为它在真实数据上的效果应该和在随机生成的数据上一样好。
我考虑过暴力破解，但粗略的分析让我估计有超过 10^65 种可能的配置。那是很多。由于我们没有万亿年的时间来考虑所有这些问题，因此我们需要一种启发式方法。
由于问题的规模，我尽量避免做任何回溯。但这意味着您可能会陷入困境；可能没有解决方案，每个人都只得到他们给出的 4 和 5 的日期。
我最终实施了一个类似于 double-edged Iterative Deepening 的搜索，其中 最佳 情况我们仍然抱有希望（即，将学生分配到他们给 5 分的日期，我们愿意接受的 最坏 案例场景（有些学生可能不得不接受 3 分）逐渐降低，直到找到解决方案.如果我们卡住了，重新设定，降低期望，然后再试一次。先分配任务A和B，A和B完成后才做C，因为C的约束远没有那么严格。
我还使用了一个加权因子来模拟最大化学生幸福感与满足 types-of-presentations-per-day 限制之间的权衡。
目前它似乎为几乎所有随机生成的首选项集找到了解决方案。我包括了一个评估指标；所有指定 student/date 组合的偏好值总和与所有学生 ideal/top 3 偏好值总和之间的比率。例如，如果学生 X 在他的列表中有两个 5、一个 4 和其余的 3，并且分配给他的 1 个 5 和 2 个 3，他得到 5+3+3=11，但理想情况下本可以得到 5+5+ 4=14；他的满意度为 11/14 = 78.6%。
经过一些测试，我的实施似乎倾向于产生大约 95% 的平均学生满意度，比我预期的要好很多 :) 但同样，这是使用假数据。真正的偏好可能更集中，更难满足。
下面是算法的核心部分。完整的脚本大约有 250 行，我认为这里有点太长了。检查一下 at Github。
...
# Assign a date for a given task to each student,
# preferring a date that they like and is still free.
def fill(task, lowest_acceptable, spread_weight=0.1, tasks_to_spread="ABC"):
random_order = range(nStudents) # randomize student order, so everyone
random.shuffle(random_order) # has an equal chance to get their first pick
for i in random_order:
student = students[i]
if student.dates[task]: # student is already assigned for this task?
continue
# get available dates ordered by preference and how fully booked they are
preferred = get_favorite_day(student, lowest_acceptable,
spread_weight, tasks_to_spread)
for date_nr in preferred:
date = dates[date_nr]
if date.is_available(task, student.count, lowest_acceptable == 1):
date.set_student(task, student.count)
student.dates[task] = date
break
# attempt to "fill()" the schedule while gradually lowering expectations
start_at = 5
while start_at > 1:
lowest_acceptable = start_at
while lowest_acceptable > 0:
fill("A", lowest_acceptable, spread_weight, "AAB")
fill("B", lowest_acceptable, spread_weight, "ABB")
if lowest_acceptable == 1:
fill("C", lowest_acceptable, spread_weight_C, "C")
lowest_acceptable -= 1
这是脚本打印的示例结果：
Date
================================================================================
Student | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
================================================================================
1 | | A | B | | C | | | | | | | |
2 | | | | | A | | | | | B | C | |
3 | | | | | B | | | C | | A | | |
4 | | | | A | | C | | | | | | B |
5 | | | C | | | | A | B | | | | |
6 | | C | | | | | | | A | B | | |
7 | | | C | | | | | B | | | | A |
8 | | | A | | C | | B | | | | | |
9 | C | | | | | | | | A | | | B |
10 | A | B | | | | | | | C | | | |
11 | B | | | A | | C | | | | | | |
12 | | | | | | A | C | | | | B | |
13 | A | | | B | | | | | | | | C |
14 | | | | | B | | | | C | | A | |
15 | | | A | C | | B | | | | | | |
16 | | | | | | A | | | | C | B | |
17 | | A | | C | | | B | | | | | |
18 | | | | | | | C | A | B | | | |
================================================================================
Total student satisfaction: 250/261 = 95.00%