时间戳

首页 > 解决方案 > 根据排名为学生分配主题

python - 根据排名为学生分配主题

问题描述

假设我想为 3 个学生分配 3 个主题。允许学生从1到3对每个主题进行排名。稍后添加：每个主题都不能有超过2名学生。

学生的可能分配是以下排列（包括一个主题有三个学生但忽略他们的情况），其中每个是

（学生 1 主题、学生 2 主题、学生 3 主题）

请注意，这三个学生不需要被分配到不同的主题。

n_topics = 3
n_students = 3


per = [el for el in itertools.product(range(n_topics), repeat=n_students)]

我们也有学生排名

rankings = [{0:1, 1:3, 2:2}, #student 1
        {0:3, 1:1, 2:2}, #student 2
        {0:2, 1:1, 2:3}] # ...

因此，很自然地让排名成为成本。因此，如果学生将某个主题排在第一位并被分配到该主题，他们支付的最低费用为 1。如果他们将某个主题排在第三位并被分配，他们支付的费用为 3。

找到最好的 3 个排列

def get_cost(perm, rankings):
        cost = 0
        for (el, c) in zip(perm, rankings):
                cost += c[el]
        return cost

def get_best_perms(per, rankings):
        perm_cost = {}
        for perm in per:
                perm_cost[perm] = get_cost(perm, rankings)
        return sorted(perm_cost.items(), key=operator.itemgetter(1))[0:3]

最好给第一个学生第零个主题，第二个学生第二个主题，以最小化成本。

print(get_best_perms(per, rankings))
#[((0, 1, 1), 3), ((0, 2, 1), 4), ((0, 1, 0), 4)]

然而，实际上有 13 个学生和 7 个主题，所以 7**13 = 96889010407 排列（在这种情况下，没有一个主题可以有超过 4 个学生，并且某些主题可能不会被选择）

是否有人对如何并行化此代码有任何建议（要使用的库等）（因为每个成本都可以独立于其他成本计算）？或者一般如何加快速度？

我认为这是一个旅行推销员类型的问题，但是学生和主题太少了，我认为可以尝试尝试所有选项，但我对做这种事情可能需要时间的直觉是不是很好。

感谢您的时间

***如果有更好的地方转发，请告诉我！

标签： pythonalgorithmtraveling-salesman

解决方案

这是一个约束满足问题，与n皇后问题非常相似。我们可以通过应用迭代算法贪婪地解决这个问题。

  • 将所有学生放在最小化总成本的最佳位置（即位置 0）。
  • 当有冲突时（一个话题被分配给超过 4 个学生），选择一个有冲突的学生并将他移动到一个次优的位置。
  • 当没有冲突时，你会得到你的结果。

该算法可能会给出次优的解决方案，但比回溯要快。

如果您想了解有关算法的更多信息，这是一个很好的链接

推荐阅读