頂點著色算法解決考試安排沖突的研究

　　摘要： 本文介紹了頂點著色法的基本機理，舉例說明了頂點著色算法在考試安排中的應用。通過實際使用，該算法有效地解決了考試安排沖突的問題，且執行效率較高。
　　關鍵詞： 頂點著色算法 考試安排 算法實施
　　
　　1.引言
　　在高校教學管理工作中，經常會遇到這樣的問題：有門課程被多名學生選修，每一位學生每場考試只能參加一門，那么最少需要多少場次安排完畢？顯然，同一學生選修的兩門課程不能在同一時間考試。當然，沒有相同學生的課程可以安排在同一時間考試。這樣問題可以總結為：在給定一個圖G=（V，E），|V|=n，（V，V）∈E，當且僅當有一個同學選了課程i和課程j，試給出一個考試安排方案：
　　N，N，N，…，N，N∩N=?覫（s≠t，1≤s，t≤k）且V=N（1≤i≤k）。
　　2.算法描述
　　2.1頂點著色算法介紹
　　已知某無向圖G=（V，E），圖G的頂點最大值d={d（v）}，那么無向圖頂點集合為V（G）={v，v，v，…，v}，頂點著色集合為：x={x，x，…xd}。
　　（1）設未染色的頂點集合D=D，已染色的頂點集合D=φ，i=0，取色數x∈x，對?坌∈D，x∶v，D←{v}+D，x∶D，D←D+D，D←，P←P+{v}+D（其中P為用顏色X所染色的頂點集合），i←i+1。
　　（2）?坌∈D，設x∈x，x∶v，D←{v}+D，D←，x∶DID，D←D+DID，P+{v}+D，i←i+1。
　　（3）假若D=D，那么進入第（4）步，否則進入第（2）步。
　　（4）輸出頂點顏色，停止執行。
　　3.算法實施
　　下面通過一個例子說明此算法在考試安排中的使用。
　　如圖1所示：G=（V，E）是一個無向圖，下面利用上面描述的算法對此圖的頂點進行著色：
　　第一步：假設學生A選擇了課程1、課程4，那么可以將課程1安排在第1場（設置為藍色），課程4安排在第2場（設置成紅色），如下圖所示：
　　第二步：找出與課程1不沖突的課程（與頂點1不直接連接的頂點），也安排在第1場次考，如課程3、5。在選擇3、5課程與課程1同時安排考試時，為減少后面出現沖突，最好選擇選課人數最多的課程安排，假設3、5課程中選擇課程5的人最多。那么，我們選擇課程5與課程1同時考試，設置頂點5的顏色為藍色。如下圖所示：
　　第三步：繼續找與課程1、課程5沒有直接連接的點，將頂點顏色標識為藍色。在上圖中可以看到課程3沒有與課程1、5直接相聯，所以我們可以將課程3安排在第一場進行考試。如下圖所示：
　　第四步：查看是否有與頂點1、3、5沒有直接的點，如果沒有當次循環結束。
　　第五步：進入第二場考試安排，查看與課程4沒有直接連接的頂點。分析上圖得知，課程2與課程6都沒有與課程4直接連接可以安排在第二場考試。
　　通過以上分析，課程1、3、5可以安排在第一場考試，課程2、4、6可以安排在第二場考試。
　　為了進一步驗證頂點著色算法在考試安排沖突問題上的卓越表現，隨機選擇3075名學生，共選修了100門課程。得出該算法執行效率統計結果如下圖所示。
　　4.結語
　　通過頂點著色法在考試安排中的實際應用，實驗結果表明，頂點著色算法在解決考試沖突問題上，針對3075名學生，100門課程僅使用了3秒鐘便安排完畢。
　　盡管如此，算法仍有需要改進的地方。今后工作將主要集中在以下方面：可以采用路分治算法充分并行化；采用并行虛擬機技術，使算法在互聯網絡的PC機上實現并行。
　　
　　參考文獻：
　　［1］王曉賀，蔡國永.基于描述邏輯的策略沖突檢測方法研究及實現［J］.計算機工程與科學，2008，（06）.
　　［2］朱曉林.沖突檢測的Java實現［J］.計算機與數字工程，2006，（03）.
　　［3］洪斌.平面圖著色的遺傳算法［J］.貴州大學學報（自然科學版），1999，（04）.
　　［4］王紹文.平面圖的四色算法［J］.光子學報，1995，（03）.
　　［5］王琳，虞厥邦.基于遺傳機制的圖著色分配算法的研究［J］.云南大學學報（自然科學版），2000，（04）.
　　［6］王小瓊.基于粒子群的圖頂點著色算法［D］.西安：華中科技大學，2007.
　　［7］廖輝傳.基于遺傳和啟發式算法的混合頂點著色算法［J］.吉首大學學報（自然科學版），2008，（09）.
　　［8］Bodlaender H L.On the complexity of some coloring game［A］.in：Proceedings of WG，Workshop on Graph Theoretical Concepts in Computer Science，1999：35-39.
　　［9］J.A.Bondy and U.S.R.Murty，Graph Theory with Applications，the Macmillan Press LTD，1976.
　　［10］Guruswami V，Hastad J，Sudan M.Hardness of approximate hypergraph coloring.IEEE，2000.
　　［11］Karp R M.Reducibility among combinatorial problems.In：Raymond E.Miller and James W.Thather，eds.Complexity of Computer Computations，Plenum Press，1972：85-103.