使用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个项目并不是“最不喜欢的”，而是在他们选择的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得到他排名第一的项目，而学生B得到她排名第五的项目，那么他们的局部分配权重就是6。如果我们把学生A调到他排名第二的项目，学生B调到她排名第三的项目，那么权重就变成5了。5小于6，这样整体就更好了。
因此，我从学生的集合开始，然后开始逐个处理他们。
我从第一个和第二个学生开始，给他们分配项目。
然后我按照上面描述的方法计算权重。如果两个人的排名都是1，那么权重就是2。这是最好的情况，我们希望继续处理第三个和第四个学生。
如果权重大于2，说明有一个或多个项目的排名超过了2，我们就尝试找到更好的分配。
我们会选择排名最低的学生，把他/她的排名降低一位（如果他/她原本是排名1，就降到排名2）。
然后我们尝试把另一个学生重新分配到其他排名。
如果新的权重比之前的权重更好，我们就把这个新权重作为新的权重，让他们拥有这些项目。如果更差或相等，我们就继续处理下一个学生对。
在局部范围内，这个算法会不断尝试，直到达到最低权重，无法再改进。

希望这能解释我想做的事情？

所以，有几个问题：

这有点像模拟退火的修改版，任何相关的评论都很受欢迎。
我该如何跟踪哪个学生是(i)，哪个学生是(i+1)？
如果我的学生总数是100，那么在(i+1)=101时会出错，因为没有这个学生。我该如何解决这个问题？
有没有明显的缺陷可以发现？

额外信息：

我的学生字典是这样设计的：

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}

伪代码算法设计搜索空间模拟退火权重分配项目分配学生偏好局部优化

使用Python的分配算法帮助

1 个回答

撰写回答