python - 分配算法帮助，使用Python

Question

我一直在为学生研究这种通用分配算法。

它的伪代码(Python 实现)是:

for a student in a dictionary of students:
    for student preference in a set of preferences (ordered from 1 to 10):
        let temp_project be the first preferred project
        check if temp_project is available
        if so, allocate it to him and make the project unavailable to others
        break

很简单，这将尝试从最喜欢的项目开始分配项目。它的工作方式是，在一组假设 100 个项目中，你列出 10 个你想做的。因此，第 10 个项目不会是“总体上最不受欢迎的”，而是在他们选择的集合中最不受欢迎的，这还不错。

显然，如果无法分配项目，学生只会恢复到基本情况，即无分配，等级为 11。

我正在做的是根据等级的加权和计算分配“质量”。因此，数字越低(即更多高度偏好的项目)，分配质量越好(即更多学生拥有高度偏好的项目)。

这基本上就是我目前所拥有的。简单有效。

---

现在我正在研究这个试图在本地最小化分配权重的算法(这个伪代码有点乱，抱歉)。

这可能有效的唯一原因是因为我的“搜索空间”并不是特别大(请注意，这只是一个非常普遍的轶事观察)。由于该项目仅针对我的部门，因此我们有自己的限制。所以学生人数不能超过100人，偏好人数也不能超过10人。

for student in a dictionary/list/whatever of students:
    where i = 0
    take the (i)st student, (i+1)nd student
    for their ranks: 
        allocate the projects
        and set local_weighting(N) to be sum(student_i.alloc_proj_rank, student_i+1.alloc_proj_rank)

    these are the cases:

    if N is 2 (i.e. both ranks are 1):
        then i += 1 and
        and continue above

    if N > 2 (i.e. one or more ranks are greater than 1):
        let temp_N be N:
            pick student with lowest rank 
            and then move him to his next rank
            and pick the other student and reallocate his project

            temp_N is sum of the the ranks

            if temp_N is < N:
                then allocate those projects to the students
                i += 1 
                and move on for the rest of the students

更新评论:

---

我正在尝试做的事情:

• 我正试图在两个学生组之间实现“最低权重分配”(即本地)

• 权重分配是学生指定排名的总和。我们希望学生获得总体排名最高的项目。因此，如果学生 A 获得了他排名第 1 的项目，而学生 B 获得了她排名第 5 的项目，则他们的本地分配权重为 6。如果我们将学生 A 移至他排名第 2 的项目，因此，学生 B 将移至她的排名3 项目然后权重现在是 5. 5 < 6 总体上更好。

• 因此，我从我的学生集合开始，然后开始遍历他们

• 我从第一个和第二个学生开始，给他们分配他们的项目

• 然后我按上述方法计算权重。考虑到权重等于排名，如果两者都排在第 1 位，则权重为 2。这已经很好了，我们想继续第二和第三位学生。

• 现在，如果权重大于2，说明一个或多个项目的排名大于2，我们尝试得到一个更好的版本。

• 因此，我们选取​​排名最低的学生，然后将他/她降一级(因此，如果他/她是排名 1，则将他降到排名 2)

• 然后我们尝试将其他学生重新分配到另一个等级。

• 现在，如果权重比以前的权重更好，那么我们就将其作为新的权重，并让他们拥有这些项目。如果它更差或相等，那么我们就转到下一组学生。

• 在本地，对于学生来说，这个东西一直在尝试，直到它达到最小重量并且不能做得更好。

希望这能解释我想做什么？

---

那么，问题:

1. 这是模拟退火的一种修改，但如有任何评论，我们将不胜感激。

2. 我如何跟踪哪个学生是 (i) 以及哪个学生是 (i+1)

3. 如果我的学生总数是 100，那么在 (i+1) = 101 时事情会搞砸，因为没有学生。我怎样才能避免这种情况？

4. 有任何可以立即发现的缺陷吗？

额外信息:

我的学生词典是这样设计的:

students[student_id] = Student(student_id, student_name, alloc_proj, alloc_proj_rank, preferences) 
    where preferences is in the form of a dictionary such that
        preferences[rank] = {project_id}

Answer 1

好像Assignment Problem可能对你有用，可以使用 Hungarian Algorithm 解决(如您在其他问题中所述:Student-Project allocation algorithms?)。

显然有一个匈牙利算法的 python 实现:http://pypi.python.org/pypi/hungarian/0.2

我建议只使用一种众所周知且已经实现的算法，而不是尝试提出自己的算法。

如果您真的想使用自己的算法并希望获得有关如何让它发挥作用的建议，我建议您清楚地解释您正在尝试做什么，而不仅仅是提供代码。

祝你好运，希望对你有所帮助。