有关考试安排的算法（一）：不冲突的算法

(2016-01-20 11:27:08)

分类：算法

有关考试安排的算法（一）：不冲突的算法

标签：算法 insert delete join table sql

2009-12-08 08:57 1385人阅读评论(0) 收藏举报

http://static.blog.csdn.net/images/category_icon.jpg 分类：

SQL Server（10） http://static.blog.csdn.net/images/arrow_triangle%20_down.jpg

版权声明：本文为博主原创文章，未经博主允许不得转载。

这是一个困扰我很久的问题，今天早上洗脸的时候突然想起，事实上也没有一开始想象中的那么困难，不管三七二十一、四七二十八，先记录下来再说。

要求：

1、学校在某个学期一共开放了N门课程由学生自由选择，每一个学生可以选择一门或几门课程进行学习。

2、在进行期末考试时，同一学生选修的两门课程不能安排在同一个时间考。

原本还想要求在最短时间内考完，但只要加上一个“最”字，实现起来就比较困难了，所以，先简化一下，只要同一学生选修的两门课程不能安排在同一时间内考试即可。

学生选课表（SelectCourse）的结构如下图所示：

http://p.blog.csdn.net/images/p_blog_csdn_net/smallfools/EntryImages/20091208/1.jpg

其中：

Id：自动增长的主键

StudentId：学号

StudentName：姓名

CourseName：选课的课程名

考场安排表（Exam）的结构如下图所示：

http://p.blog.csdn.net/images/p_blog_csdn_net/smallfools/EntryImages/20091208/2.jpg

其中：

Id：自动增长的主键

ExamScreenings：考场场次，既第几场考试

Course：考试课程名

ExamNum：该门课程的选课人数

算法如下所示：

1、设置考场中最多可同时考试的人数。

2、统计每门课程的考试人数，放入临时表中。

3、先在临时表中选出选课人数最多的那门课程，当然，必须要先确定考场中最多可同时考试的人数要大于单门课程的最多选课人数。

4、将考试场次加1，并将选课人数最多的课程（当前课程）添加到考场安排表里（Exam），然后将该门课程从临时选课表中删除。

5、然后将考试最多可同时考试的人数减去已经安排的考试课程的人数，得到考场中还可以安排的考试人数，即剩余考试人数（@RemainNum）

6、选择所有选课人数少于或等于剩余考试人数的课程，并放到游标里。

7、循环从游标里取出课程，判断选择该课程的学生是否和当前考试场次中已安排的课程的选课学生有冲突（既是否同一学生在同一时间内参加两门考试）。如果没有冲突，则将该课程放入考场安排表中，并从临时表中删除该门课程。

8、重新统计剩余考试人数，返回到第5步骤，直到所有选课人数少于剩余考试人数，或着所有考试都有冲突不能安排为止。

9、返回第3步骤，直到所有课程都已经安排为止。

具体实现的SQL语句如下所示：

[c-sharp]view
plaincopy

truncate table Exam  

--考场中可同时容纳的考生人数  

declare @MaxNumber int  

set @MaxNumber = 1500  

--考试场次  

declare @ExamScreenings int  

set @ExamScreenings = 0  

--单场考试还能安排多少人数  

declare @RemainNum int  

--最始化：可安排人数与考场可容纳人数相同  

set @RemainNum = @MaxNumber  

--最后一次已安排的考试课程名  

declare @LastCourseName varchar(50)  

set @LastCourseName = null  

--统计每门课程的考试人数，并放入临时表中  

select CourseName,count(id) as ExamNum   

into #tempSelectCourse  

    from SelectCourse  

        group by  CourseName  

        order by ExamNum desc  

--显示临时表中的数据  

select * from #tempSelectCourse  

--开始循环  

while 1=1  

begin  

    --当前选择的考试课程名  

    declare @CurrentCourseName varchar(50)  

    set @CurrentCourseName = null  

    --当前课程的选课人数  

    declare @CurrentExamNum int  

    --在临时表中选出选课最多的那门课程（假设该门课程的选课人数小于考场可安排的人数）  

    select top 1 @CurrentExamNum = ExamNum, @CurrentCourseName = CourseName from #tempSelectCourse order by ExamNum desc  

    --如果当前选择的考试课程名为空，则说明在该场次考试中已经没有可安排的课程  

    if @CurrentCourseName is null  

        begin  

            --跳出循环  

            break  

        end  

    else  

        --否则说明还有可安排的课程  

        begin  

            --考试场次加1  

            set @ExamScreenings = @ExamScreenings + 1  

            --将当前选择的课程添加到考场安排表里  

            insert Exam (ExamScreenings,Course,ExamNum) values (@ExamScreenings,@CurrentCourseName,@CurrentExamNum)  

            --从临时表中删除该门课程  

            delete #tempSelectCourse where CourseName = @CurrentCourseName  

            NextCourse:  

            --当前考场还能安排多少人进行考试  

            set @RemainNum = @RemainNum - @CurrentExamNum  

            --将选课人数少于或等于当前考场还能安排考试人数的记录放在游标里  

            declare aa cursor for  

                select ExamNum,CourseName from #tempSelectCourse where ExamNum<=@RemainNum order by ExamNum desc  

            --打开游标  

            open aa  

            --从游标里取出一条记录  

            fetch next from aa into @CurrentExamNum,@CurrentCourseName  

            --判断游标里是否还有记录  

            while(@@fetch_status=0)  

                begin  

                    --判断选课当前课程的学生，在同一场考试中是否还有别的课程需要考试（考试冲突判断）  

                    if (SELECT count(id) FROM SelectCourse   

                            INNER JOIN  (  

                                SELECT SelectCourse.StudentId FROM Exam   

                                    INNER JOIN SelectCourse ON Exam.Course = SelectCourse.CourseName  

                                WHERE (Exam.ExamScreenings = @ExamScreenings)  

                                ) AS ArrangedCourse   

                            ON SelectCourse.StudentId = ArrangedCourse.StudentId  

                        WHERE CourseName=@CurrentCourseName)=0  

                        begin  

                            --如果考试不冲突，则将当前选择的课程添加到考场安排表里  

                            insert Exam (ExamScreenings,Course,ExamNum) values (@ExamScreenings,@CurrentCourseName,@CurrentExamNum)  

                            --从临时表中删除该门课程  

                            delete #tempSelectCourse where CourseName = @CurrentCourseName  

                            --关闭游标，重新计算剩余的课程  

                            close aa  

                            deallocate aa  

                            goto NextCourse  

                        end  

                        --获取下一条记录  

                        fetch next from aa into @CurrentExamNum,@CurrentCourseName  

                end  

            --关闭游标  

            close aa  

            deallocate aa  

        end  

end  

--删除临时表  

drop table #tempSelectCourse

这个算法运行速度还可以，我试了13756人次131门选课，运行结果20秒左右。但是，这不是最优的算法，这131门的选课一共需要106个场次的考试，天哪，太多了！

可以说，这个算法失败了！

有人知道更好的算法吗？

原创不容易，转载请注明出处。http://blog.csdn.net/smallfools/archive/2009/12/08/4961307.aspx

阅读┊ 收藏 ┊ 喜欢 ▼ ┊打印┊举报/Report

前一篇：有关考试安排的算法（二）

后一篇：《挑战算法之路》目录页

新浪BLOG意见反馈留言板　欢迎批评指正