大佬教程收集整理的这篇文章主要介绍了我应该使用哪种算法来排序学生?,大佬教程大佬觉得挺不错的,现在分享给大家,也给大家做个参考。
students = { student1 = @R_772_9111@=student1,force={"student2"},deny={}}; student2 = @R_772_9111@=student2,force={"student1","student3"},deny={}}; student3 = @R_772_9111@=student3,deny={}}; }-- A second name property is given in the case that the student table needs to be accessed by students[num] to retrieve a name
然后我创建临时表:
forced = {}--Every student who has at least 1 entry in their force table is placed here,even if they have 1 or more in the deny table denied = {}--Every student with 1 entry for the deny table and none in the force table is placed here leftovers = {}--Every student that doesn't have any entries in the force nor deny tables is placed here unsortable = {}--None are placed here yet -- this is to store students that are unable to be placed according to set rules(i.e. a student being forced to be paired with someone in a group that also contains a student that they can't be paired with SortstudentsIntoGroups()--predefined; sorts students into above groups
在每个学生都被安排在这些小组之后(注意他们也仍留在学生桌上),我首先插入被迫在小组中配对的学生(好吧,我已经尝试过),插入有一个学生的学生或者将deny表中的更多条目放入可以放置它们的组中,然后用剩余的组填充剩余的组.
有几件事情会有所帮助:
numGroups--predefined number of groups maxGroupSize--automatically calculated; quick reference to largest amount of students allowed in a group groups = {}--number of entries is equivalent to numGroups(i.e. groups = {{},{},{}} in the case of three groups). This is for storing students in so that the groups may be displayed to the end user after the algorithm is complete. sortGroups()--predefined function that sorts the groups from smallest to largest; will sort largest to smallest if supplied a true Boolean as a parameter)
正如我之前所说,我不知道如何为此设置递归算法.每当我尝试将强迫学生插入到一起时,我最终会将同一个学生分成多个组,强制对没有配对,等等.还要注意格式.在每个学生的强制/拒绝表中,给出了目标学生的姓名 – 而不是直接参考学生.@R_879_10675@用什么样的算法(如果这种情况存在的话)?任何帮助是极大的赞赏.
这相当于k001颜色的graph-coloring问题,其中edge是拒绝列表.
图形着色:
Given a graph G=(V,E),and an Integer `k`,create coloring function f:V->{1,2,..,k} such that: f(v) = f(u) -> (v,u) is NOT in E
从图形着色到您的问题的减少:
给定图形着色问题(G,k),其中G =(V,用以下方法创建问题的实例:
students = V for each student: student.denial = { student' | for each edge (student,student')} #groups = k
直观地,每个顶点由学生表示,并且学生否认所有学生在表示它们的顶点之间存在边缘.
组的数量是给定的颜色数.
现在,给你一个问题的解决方案 – 我们得到k组,如果学生你否认学生v – 他们不在同一组,但这与用不同颜色着色u和v相同,所以对于每个边缘(u,v)在原始图中,u和v是不同的颜色.
另一种方式是类似的
所以,我们从图形着色问题得到了一个polynomial reduction,因此找到问题的最佳解决方案是NP-Hard,并且没有已知的有效解决方案,并且大多数人认为不存在.
一些替代方案使用诸如Genetic Algorithms之类的启发式方法,其不提供最佳解决方案,或使用耗时的@L_262_4@方法(对于大量学生来说不可行).蛮力只会产生对k组的所有可能的分裂,并检查它是否是可行的解决方案,最后 – 将选择找到的最佳解决方案.
以上是大佬教程为你收集整理的我应该使用哪种算法来排序学生?全部内容,希望文章能够帮你解决我应该使用哪种算法来排序学生?所遇到的程序开发问题。
如果觉得大佬教程网站内容还不错,欢迎将大佬教程推荐给程序员好友。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。