这是一个复杂的问题，但我怀疑我可以应用一些原则来使其变得简单——我只是不知道它是什么。
我需要为这个学期的全班学生分配演示空间。有多种可能的日期和多种演示类型。我进行了一项调查，学生可以对他们对不同主题的兴趣进行排名。我想做的是为学生提供最好的（或至少是好的）演示时段分配。
所以，我有什么：
我想得到什么：
intro)、一个演示类型 B ( figures) 和 3 个演示类型 C ( aims)我应该注意，我意识到这看起来像是一个家庭作业问题，但它是现实生活:-)。我在想我可能会Student为每个学生创建一个包含每种演示类型的日期的课程，但我不确定填充它的最佳方式是什么。实际上，我什至不知道从哪里开始。
TL;DR：我认为你给你的学生太多的选择：D
但无论如何，我对这个问题有过尝试。实际上很有趣的练习，虽然有些限制有点模糊。最重要的是，我不得不猜测实际学生的偏好分布会是什么样子。我选择了均匀分布的自变量，尽管这可能不太现实。我仍然认为它在真实数据上的效果应该和在我随机生成的数据上一样好。
我考虑过暴力破解它，但粗略的分析给了我超过 10^65 种可能配置的估计。这有点多。而且由于我们没有一万亿年的时间来考虑所有这些，我们需要一种启发式方法。
由于问题的规模，我尽量避免做任何回溯。但这意味着您可能会陷入困境。可能没有一个解决方案，每个人都只能得到他们给 4 和 5 的日期。
我最终实施了一个双刃迭代深化式搜索，其中我们仍然抱有希望的最好情况（即，将学生分配到他们给 5 的日期）和我们愿意的最坏情况接受（有些学生可能不得不忍受 3）逐渐降低，直到找到解决方案。如果我们卡住了，重新设置，降低期望，然后再试一次。首先分配任务 A 和 B，只有在 A 和 B 完成后才完成 C，因为对 C 的约束远没有那么严格。
我还使用了一个加权因子来模拟最大化学生幸福感与满足每天的演示类型限制之间的权衡。
目前，它似乎为几乎所有随机生成的偏好集找到了解决方案。我包括了一个评估指标；所有分配的学生/日期组合的偏好值总和与所有学生理想/前 3 名偏好值的总和之间的比率。例如，如果学生 X 有两个五分之一，一个四分，其余三分在他的名单上，并被分配到他的五分之一和两个三分之一，他得到 5+3+3=11，但理想情况下可能得到 5+5+ 4=14；他 11/14 = 78.6% 满意。
经过一些测试，似乎我的实现往往会产生大约 95% 的平均学生满意度，比我预期的要好得多 :) 但同样，这是使用假数据。真正的偏好可能更集中，更难满足。
下面是算法的核心。完整的脚本大约有 250 行，我认为这里有点太长了。在 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%