首页博文目录关于我

个人资料

微博

加好友发纸条

写留言加关注

博客等级：
博客积分：

博客访问：
关注人气：
获赠金笔：0支
赠出金笔：0支
荣誉徽章：

正文字体大小：大中小

有关考试安排的算法（二）

(2016-01-20 11:26:18)

分类：算法

有关考试安排的算法（二）：以课程为本，还是以人为本？

标签：算法 insert table delete join c

2009-12-10 09:49 1646人阅读评论(1) 收藏举报

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

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

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

在前几天中，为了想出一个安排考场的算法，我是抓破了头，好不容易想到一个，却有两个不合适的地方：

1、算法中有bug，在前两天的那个算法中，先确定了一门课程，假设为课程A，然后查找所有与课程A不冲突的课程，假设有课程B和课程C与课程A不冲突，然后就将课程B、课程C与课程A放在同一时间考试。在这种方法里，我忽略了课程B和课程C是否有冲突的情况。

2、考试场次过多，131门课程需要106个场次的考试，一天考5场的话，需要22天才能考完，这明显不合事宜。

因此，那个算法可以说是一个完全失败的算法。

上网查了一下，无论是百度还是谷歌，都没有找到一个可行的、现成的算法，不过倒都提供了一个思路：顶点着色法。

什么叫顶点着色法？也就是说，将所有课程（如课程A、B、C、D）看成是一个个圆点，如果有一个学生同时选择了两门课程，假设选择了课程A和课程B，那么就在圆点A和圆点B之间划上一条联接线。如下图所示：

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

在上图中，课程A和课程B、课程E、课程F中间有连线，所以课程A是不能和课程B、课程E、课程F同时考试，而课程A和课程C、课程D、课程G、课程H之间都没有连线，那么课程A则可以和课程C、课程D、课程G、课程H是的一门或多门同时考。为什么说只能和课程C、课程D、课程G、课程H中的一门或多门同时考呢？我们再来看一下上面的图，课程C和课程D之间有连线，所以，课程A、课程C和课程D，这三门是不能同时考的。如果转换成顶点着色的问题，可以这么看，先将顶点A（即课程A）涂上一种颜色，假设为红色，那么顶点B、顶点E和顶点F就不能涂成红色。而顶点C、顶点D、顶点G、顶点H中有一个或多个可以涂成红色，因为它们和顶点A之间都没有连线。但是顶点C和顶点D不能同时为红色，因为它们之间有连线。

这样，选课问题就可以转换成顶点着色问题，即使将上图中所有顶点都涂满颜色，要求有两个：

1、中间有连线的两个顶点不能为同一种颜色。

2、要求使用最少的颜色涂满所有顶点。

确定了这种思想之后，又上谷歌下百度查询一翻，也看到了不少解决方法，什么回溯算法啊、蚂蚁算法啊，甚至还有DNA算法！看得我头都晕了，一个字：看不懂！对不起，晕了，是三个字。

看来求人不如求己了，于是，我决定，还是自己开动脑筋想吧。

一开始，我就钻进了顶点着色算法里去了。后来发现，这个算法不简单，不同的起点（即从不同的顶点入手）、不同的路径（即沿着不同的连线查询到不能着相同颜色的顶点），所得到的结果都不相同。我也没有办法将所有可能的路径都走一遍，然后再去判断哪条路径最短。更何况，还有一个考场最多可容纳考试人数的约束呢。

钻了很久，在我都想要放弃的时候，突然想到，为什么一定要以课程为考虑方向呢？为什么不能以人为考虑方向呢？科技都以人为本了，安排考场同样也应该以人为本才对嘛。

以人为本的考虑方法如下所示：

1、选出选课数最多的学生，很明显，该学生的所有考试是不能在同一时间进行的。所以，可以按次序安排这几门课程。以上图为例，假设学生A选择了课程A、课程E和课程F，那么，就可以将课程A安排在第1场次考（红色），课程E安排在第2场次考（蓝色），课程F安排在第3场次考（黄色），如下图所示。

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

2、然后找出1门与课程A不冲突的课程，也安排在第1场次考，如课程C、D、G、H。那到底是安排哪门课程在第1场次考呢？这个，我无法肯定，因为选择课程C还是课程D，有可能最后的结果会差别很大。但我考虑了一个，应该选选课人数最多的那门课程。假设课程C有100人选修，课程D有30人选修，那么就选择课程C，因为选课人数越多的课程，和其它课程的冲突的可能性也就越大，既然在这里没冲突了，那么就优先安排这门课程吧。如下图所示，课程C也使用红色填涂，这就说明，课程A和课程C可以同时进行考试。

http://p.blog.csdn.net/images/p_blog_csdn_net/smallfools/EntryImages/20091210/3.jpg

3、然后，我们应该继续找和课程A、课程C都没有连线的顶点。在上图中我们可以看到，课程H和课程A、课程C都没有连线，那么课程H也可以放在第1场次考试。如下图所示。

http://p.blog.csdn.net/images/p_blog_csdn_net/smallfools/EntryImages/20091210/14.jpg

4、查看是否还有与A、C、H节点都没有连线的节点。在上图中我们可以看出，已经不存在这样的节点了。（当次循环结束）

5、进入下一个循环，也就是查看第2场次考试的课程，前面我们已经将课程E安排在第2场次考，那么我们现在要看一下和节点E没有连线的节点。如上图所示，课程B、D、E和课程E都没有节点。先安排冲突最少的节点，也就是连线最少的节点——课程B，如下图所示。

http://p.blog.csdn.net/images/p_blog_csdn_net/smallfools/EntryImages/20091210/15.jpg

6、再看和节点B、E都没有连线的节点，也就是节点D，那就说明，课程D可以在第2场次考。如下图所示：

http://p.blog.csdn.net/images/p_blog_csdn_net/smallfools/EntryImages/20091210/16.jpg

7、最后，课程G和课程F正好没有冲突可以安排在第3场次中考。如下图所示。

http://p.blog.csdn.net/images/p_blog_csdn_net/smallfools/EntryImages/20091210/17.jpg

在上例中，所有课程正好都已经安排了。但是，在现实中，会不有这么巧的事，所有课程都正好安排完，如果顶点G和顶点F之间有连线，那么课程G就只能安排在下一个考试场次中了，如下图所示。

http://p.blog.csdn.net/images/p_blog_csdn_net/smallfools/EntryImages/20091210/18.jpg

经过以上几个步骤，我们以一个学生的所有选课（假设他选了N门课程）为基础，安排了N个场次的考试，那么，剩下的课程我们又要怎么做呢？这个时候，我们就不能再选择一个选课最多的学生，再根据他的选课情况来安排考场了。因为这个学生所选的课程，很有可能已经安排过了。

这个时候，我们可以用删除法来做，先将所有已经安排的课程删除，如上图中可以将除课程G之外的所有课程删除。然后，我们在学生的选课表中，将已经安排过的选课删除。这样，我们可以得到另一个顶点图和学生选课表，当然，这个顶点图和学生选课表是上一个顶点图和学生选课表的子集。由于没有了已安排的课程的干扰，我们可以将上面的步骤再循环地操作一次，安排其余的课程。

这样，一直循环下去，最后得到一个完整的考场安排表。

具体的SQL代码如下所示：

[c-sharp]view
plaincopy

--重建考试安排表  

truncate table Exam  

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

declare @MaxNumber int  

set @MaxNumber = 900  

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

declare @RemainNum int  

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

set @RemainNum = @MaxNumber  

--将学生选课表放在临时学生选课表中，这样就可以在临时选课表中随意地删除选课了  

SELECT StudentId, StudentName, CourseName  

into #SelectCourse  

FROM SelectCourse  

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

select CourseName,count(CourseName) as ExamNum, 0 as Arranged   --Arranged：是否已安排；未安排为0，已安排为1  

into #CourseSelection  

    from #SelectCourse  

        group by CourseName  

        order by ExamNum desc  

--创建一个临时冲突记录表，用于说明课程与课程之间是否冲突。这个冲突表相当于顶点图  

CREATE TABLE #CourseClash  

(  

    CourseA varchar(50) NOT NULL,   --课程A  

    CourseB varchar(50) NOT NULL,   --课程B  

    IfClash bit NOT NULL,           --如果冲突则为1，如果不冲突则为0  

    ElectNum int NOT NULL           --同时选择这两门课程的人数  

)  

--将课程与课程之间的冲突情况记录到临时冲突记录表中  

while (select count(CourseName) from #CourseSelection where Arranged=0)>0  

    begin  

        --考试课程A  

        declare @CourseNameA varchar(50)  

        --考试课程B  

        declare @CourseNameB varchar(50)  

        --从临时统计表中取出一条记录  

        select top 1 @CourseNameA = CourseName from #CourseSelection where Arranged = 0  

        --将该课程标记为已安排  

        update #CourseSelection set Arranged=1 where CourseName = @CourseNameA  

        --获取剩下的记录并放在游标里  

        declare aa cursor for  

            select CourseName from #CourseSelection where Arranged = 0  

        --打开游标  

        open aa  

        --从游标中获取一条记录  

        fetch next from aa into @CourseNameB  

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

        while(@@fetch_status=0)  

            begin  

                --判断课程A和课程B是否有冲突，即获得选择它们的学生的交集  

                declare @ElectNum int  

                SELECT @ElectNum = COUNT(*) FROM   

                        (SELECT StudentId FROM #SelectCourse WHERE CourseName=@CourseNameA) AS SelectCourseA  

                    INNER JOIN  

                        (SELECT StudentId FROM #SelectCourse WHERE CourseName=@CourseNameB) AS SelectCourseB  

                    ON  

                        SelectCourseA.StudentId = SelectCourseB.StudentId  

                --如果交集为0，则说明课程A和B没有冲突  

                if @ElectNum=0  

                    begin  

                        --插入记录到临时冲突记录表  

                        INSERT #CourseClash (CourseA,CourseB,IfClash,ElectNum)   

                            VALUES (@CourseNameA,@CourseNameB,0,0)  

                        INSERT #CourseClash (CourseA,CourseB,IfClash,ElectNum)   

                            VALUES (@CourseNameB,@CourseNameA,0,0)  

                    end  

                else  

                    begin  

                        --插入记录到临时冲突记录表  

                        INSERT #CourseClash (CourseA,CourseB,IfClash,ElectNum)   

                            VALUES (@CourseNameA,@CourseNameB,1,@ElectNum)  

                        INSERT #CourseClash (CourseA,CourseB,IfClash,ElectNum)   

                            VALUES (@CourseNameB,@CourseNameA,1,@ElectNum)  

                    end  

                --从游标中获取下一条记录  

                fetch next from aa into @CourseNameB  

            end  

        --关闭游标  

        close aa  

        deallocate aa  

    end  

--考试场次  

declare @ExamScreenings int  

set @ExamScreenings = 0  

--安排的考试课程  

declare @ExamCourse varchar(50)  

--考试人数  

declare @ExamNum int  

set @ExamNum = 0  

while (select count(*) from #SelectCourse)>0  

begin  

    --首先获得选课最多的学生的选课，并将这些选课添加到考试安排表中  

    declare bb cursor for  

        select #SelectCourse.CourseName,#CourseSelection.ExamNum from #SelectCourse  

            inner join #CourseSelection on #CourseSelection.CourseName = #SelectCourse.CourseName  

            where StudentId = (select top 1 StudentId from #SelectCourse group by StudentId order by count(StudentId) desc)  

    --打开游标  

    open bb  

    fetch next from bb into @ExamCourse,@ExamNum  

    while(@@fetch_status=0)  

    begin  

        --考试场次  

        set @ExamScreenings = @ExamScreenings + 1  

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

        set @RemainNum = @MaxNumber  

        --插入考试安排表  

        INSERT Exam (ExamScreenings,Course,ExamNum) VALUES (@ExamScreenings,@ExamCourse,@ExamNum)  

        set @RemainNum = @RemainNum - @ExamNum  

        -------------------------------------------------------------------------------------------  

        --选出所有与该门考试不冲突的课程并且不是正要添加的选课，放在游标中，即有可能安排的课程  

        declare cc cursor for  

            select #CourseClash.CourseB,#CourseSelection.ExamNum from #CourseClash  

                inner join #CourseSelection on #CourseSelection.CourseName = #CourseClash.CourseB  

            where #CourseClash.CourseA=@ExamCourse and #CourseClash.IfClash=0  

                and #CourseClash.CourseB not in   

                    (select #SelectCourse.CourseName from #SelectCourse  

                        where StudentId =   

                            (select top 1 StudentId from #SelectCourse group by StudentId order by count(StudentId) desc))  

                and #CourseSelection.ExamNum <=@RemainNum  

            order by #CourseSelection.ExamNum desc      --这里排序是按选课人数多少排，也可以按冲突人数多少来排  

        --将要安排的课程  

        declare @WillArrange varchar(50)  

        --打开游标  

        open cc  

        --取出一条记录  

        fetch next from cc into @WillArrange,@ExamNum  

        while (@@fetch_status=0)  

        begin  

            --======================================================================================  

            --判断当前课程的选课人数是否大于考场可安排人数  

            if @ExamNum>@RemainNum  

            begin  

                fetch next from cc into @WillArrange,@ExamNum  

                continue  

            end  

            --======================================================================================  

            --======================================================================================  

            --判断将要安排的课程和已安排的课程是否有冲突  

            --======================================================================================  

            --定义一个标识变量  

            declare @bFlag int  

            set @bFlag = 0  

            --查找所有已安排的课程  

            declare dd cursor for  

                select Course from Exam where ExamScreenings = @ExamScreenings  

            --已安排的课程  

            declare @Arranged varchar(50)  

            open dd  

            fetch next from dd into @Arranged  

            while (@@fetch_status=0)  

            begin  

                --判断将要安排的课程和已安排的课程是否有冲突  

                if (select top 1 IfClash from #CourseClash where CourseA=@WillArrange and CourseB=@Arranged)=1  

                begin  

                    --如果有冲突，则将标识变量设为1，跳出循环  

                    set @bFlag = 1  

                    break  

                end  

                fetch next from dd into @Arranged  

            end  

            --判断将要安排的课程是否和已安排的课程冲突  

            if (@bFlag=0)  

            begin  

                --如果不冲突，则在考场安排表中插入记录  

                INSERT Exam (ExamScreenings,Course,ExamNum) VALUES (@ExamScreenings,@WillArrange,@ExamNum)  

                set @RemainNum = @RemainNum - @ExamNum  

            end  

            close dd  

            deallocate dd  

            --======================================================================================  

            fetch next from cc into @WillArrange,@ExamNum  

        end  

        --关闭游标  

        close cc  

        deallocate cc  

        -------------------------------------------------------------------------------------------  

        --从临时学生选课表中删除该门选课  

        delete #SelectCourse where CourseName in (select Course from Exam where ExamScreenings=@ExamScreenings)  

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

        delete #CourseSelection where CourseName in (select Course from Exam where ExamScreenings=@ExamScreenings)  

        --从冲突表中删除该门课程  

        delete #CourseClash where CourseA in (select Course from Exam where ExamScreenings=@ExamScreenings)   

            or CourseB in (select Course from Exam where ExamScreenings=@ExamScreenings)  

        fetch next from bb into @ExamCourse,@ExamNum  

    end  

    --关闭游标  

    close bb  

    deallocate bb  

end  

--删除临时表  

drop table #SelectCourse        --临时选课表  

drop table #CourseSelection     --临时统计表  

drop table #CourseClash         --临时冲突表

使用以上方法，成功的为13756人次、131门课程安排了考场，考试场次为22。

虽然以上方法不是最佳的，但是，这是可行的。

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

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

前一篇：强迫症的 Mac 设置指南

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

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