基于分治法的高?？荚嚢才潘惴?/h1>
2012-07-09 01:44:36駱紹燁
長春工業大學學報 2012年2期
駱紹燁
（莆田學院電子信息工程系，福建莆田 351100）
0 引 言
現代教育理論認為，考試是教育評價的一種重要手段，其作用主要表現在以下兩個方面：其一是評估教師的課堂教學效果，促使教師總結教學經驗，改進教學方法；其二是評價檢測學生的學習效果，了解學生對所學知識和技能的掌握情況和應用能力，促使學生學習以及幫助改進學習方法［1］。
傳統的考試安排方式主要是依靠教學管理人員的人工安排，雖然他們在考試安排中逐漸積累了一些經驗和方法［2］，但是，隨著專業的不斷增加和細化，組織考試的工作量越來越大［3］，而且組織考試的時間大多是在學期中或學期末，此時教學管理的工作又相對集中，時間有限，任務又重，人工管理的方式暴露出了不少的弊端。
計算機自動排考是一個時間表問題，把考試安排問題化為計算領域有約束的時空組合優化問題進行求解［4］。由于約束條件復雜，問題規模龐大，對于排考這類問題迄今為止還沒有找到在多項式步驟內解決的有效算法，只能在一定范圍內尋求最優解。
1 排考問題描述
從排考過程中涉及到的可能引起潛在資源競爭沖突的角度，排考問題涉及到的因素主要有：時間、課程、場地、班級和教師。其中班級又分為行政班級和考試班級。行政班級指招生時注冊的班級，每個行政班級有編號、名稱、院系、專業和學生人數。每個行政班同一時間只能考一門課程?？荚嚢喔拍畹漠a生主要是基于有些課程由于人數過多或者其它原因需要拆班考試。
1.1 約束條件
排考的約束條件可分為兩大類：硬約束和軟約束。
1．1．1 硬約束
硬約束表示必須遵守的約束條件。
硬約束主要包括以下幾個方面：
1）同一班級在同一時間不能考兩門不同的課程。
2）同一教師在同一時間不能安排兩個考場。
3）同一考卷的班級應在同一時間安排考試。
4）考場的容積必須大于在該處考試的學生的人數。這里所說的容積不是考場的總座位數，而應指按照考試要求所能排下的最大學生數。
5）安排監考的教師必須在崗。
1．1．2 軟約束
軟約束表示在排考過程中盡可能滿足的約束條件，但不滿足也無妨，軟約束條件的滿足與否往往與排考實際情況有關。
軟約束主要包括以下幾個方面：
1）該課程的授課教師應參加監考，且盡可能安排在該教師所授課班級監考。這樣可以方便解決考試中出現的諸如試卷不清等問題。
2）課程安排有一定間隔，讓學生有足夠備考時間。一天內一個班級盡可能只安排一門考試。
3）教師安排監考次數適當。
4）滿足監考教師監考意愿偏好。
5）在指定時間段內安排考試。
1.2 排考目標
由約束條件可以看出，對于排考問題實際上是一個組合規劃問題，但要求出問題的最優解卻是不可能的，雖然約束條件能幫助我們進行求解，但是隨著問題范圍的擴大，組合方案呈爆炸式增長，特別是高校的排考問題，其排考難度更大［5］。因而，我們必須放棄尋求最優解，事實上，迄今為止，對排考和排課問題的研究也證明了最優解是極難求出的，只能“退而求其次”，尋找問題的近似最優解。只要這個解能夠在滿足硬約束條件的前提下，盡可能地滿足軟約束，滿足各方面的需求，使得解決方案合理可行。
2 系統自動排考算法設計
隨著資源數量的增大，排考問題因考試編排選擇方案的劇增，就可能出現“組合爆炸”，致使排考問題變得錯綜復雜，從而直接影響到排考問題的解［6］。為了降低排考算法的復雜性，在自動排考時運用分治法的思想，將問題空間分解成多個小規?？臻g，分別求出各個小空間的解，再組成整個問題的解的方法。
分治法的思想就是將整個問題分成若干個問題后分而治之［7］。當要求解一個輸入規模為n，且n取值又相當大的問題時，直接求解往往是非常困難的，有的甚至根本沒法直接求出。每當遇到這類問題時，分治法往往能發揮很大的作用。任何一個可以用計算機求解的問題所需的計算時間都與其規模有關。問題的規模越小，越容易直接求解，解題所需的計算時間也越少［6］。
運用分治法解決排考問題，把問題空間逐層分解成多個小規?？臻g，可以減小問題規模。排考時，先將課程分成公共課與專業課兩種類型，因為公共課與專業課有著各自不同的特點。公共課課程數量少，但參加考試的班級較多，而專業課則恰恰相反。將兩種課程類型分開，有利于采取不同的分配方案，同時也降低了問題的規模。其次，在專業課排考時，將整個學校的考試安排調度分解成各個開課院系的考試安排，問題空間再次縮小。最后將排考過程分解成安排時間、安排場地和安排監考老師3個相對獨立的子問題。安排時間時，只需要考慮課程與時間的搭配；安排場地時，只需考慮考試班級與考試場地的搭配；安排監考教師時，只需保證監考教師的監考時間不沖突即可。由以上可以看出，在逐層的分解過程中，求解的難度也不斷降低，排考得到了更簡單和更迅速的求解。分解到位的排考算法主要通過以下步驟實現。
1）選取課程。為了減少排考過程中可能出現的沖突，采取先難后易的原則，不好安排的課程先排，即容易在排考時出現沖突的、排考條件要求較難滿足的課程優先進行排考。如果這些課程在排考后期才開始安排，此時很多資源已被占用。因為雖然總的資源數量是一定的，但到了排考的后期，剩余的資源特別可能會出現類似存儲管理中的資源碎片問題，即大量空余的資源很少，取而代之的是分布零散的資源碎片。這時為這些較難安排的課程尋找到適合的資源就變得更難了，也就影響了排考的順利進行。排考過程中，課程的參加考試班級數、參加考試班級的人數、參加考試班級的考試課程數等多個因素都會影響課程的考試安排難度，但影響最大的因素還是課程的參加考試班級數。
2）貪心法安排時間。選定待排考課程之后，接著就是為課程安排考試時間，公共課的考試時間由排考人員直接指定，專業課程的考試時間在計算機自動排考時是由系統根據權值法和貪心法選定。
在安排專業課程考試時，排考人員首先需要計算每個可排考時間的權值。管理員可以根據需要將一天的考試時段分成1～5個不等的時間段。將所有可以排考的時段的權值存放在權值數組periodstate［］中，periodstate［X］表示第X個時間段的權值。當我們需要表示考試安排區間中的第M天的第L個時段的權值時，有如下公式：
式中：N——每天可排考的時段數。
在為課程選擇考試時間時，首先初始化時段權值數組，將所有的考試時段的初始權值為同一值10 000。然后逐時段分析計算各個考試時段的權值。權值的計算方法如下：
首先，如果該時段排考課程中的任何一個參考班級在此時段已安排了考試，則該時段的權值為0。其次，為了使得軟約束中的要為學生留有一定的備考時間的條件盡量得到滿足，一個班級盡可能不在一天安排多場考試，即一天在可能的情況下最多只安排一場考試。因此，檢查該天是否有班級已安排了考試課程，如果有，每增加一個已在該天安排了考試課程的班級，則相應地降低該時段的部分權值。
在使用權值的計算辦法處理完所有時段的權值后，就可以使用貪心策略來選擇課程的考試時間了。貪心法是一種改進了的分級處理方法，就是在對問題求解時，總是做出在當前看來是最好的選擇，每一步都應是局部最優解，不從整體最優上加以考慮，所做出的僅是在某種意義上的局部最優解［8］。貪心法通過不斷求解局部最優解逐步構造全局解的方式，對許多問題可以產生整體最優解，即使不能得到整體最優解，也能找到最優解的較好的近似解。并且排考問題實際上并不一定需要找出整體最優解，排考問題最優解的定義也是個難題。所以在很大程度上，只需要求得一個次優解或者滿足解即可。在安排課程考試時間上采用貪心法，能在保證速度的前提下求得局部最優解，符合速度和效用的平衡，從而獲得整體最優解的良好特性，進而使其在排考系統的應用中能夠發揮其主要的特性。
3）最佳適應法安排場地。最佳適應算法（Best Fit）是動態存儲分配解決方案中最為常見的一種方案。最佳適應算法就是在內存空間中為將要加入的作業選擇大于該作業需要的空間大小，并且是最小的內存空間來存放該作業［9］。排考時的安排考試場地與模擬內存分配十分類似，可以模擬其分配方式。
安排考試場地，首先必須從數據庫中獲取在排的考試班級的人數K，接著從數據庫中獲取屬于開考班級院系且容積大于K的所有考試場地的信息，然后逐個考試場地進行比較選擇。比較選擇時，在確定考試場地在安排的課程考試時間時是空閑的情況下，計算考試場地容積S與班級人數K的差值，與已有的場地中的容積與班級人數之差的最小值MIN（S－K）做比較。如果當前的S－K值更小，則記錄下當前的考試場地編號和新的MIN（S－K），否則直接選取下一個場地。如此判斷比較直至比較完所有的考試場地，此時記錄的考試場地即是算法所求的場地。
4）等概率分配法安排監考教師。在安排了考試的時間和考試場地之后，最后要做的是安排監考教師。依據高校的有關考試規定，每個考場安排兩位監考教師監考。監考教師原則上選取學生所在系的教師。在安排監考教師時應考慮教師的在崗情況及監考意愿。同時，在滿足教師監考意愿的前提下，應考慮教師工作量的均衡，因而對于可任意參加監考的教師使用等概率分配法來安排監考教師。為了方便解決考試中可能出現的一些問題，在安排監考時，優先安排授課教師參加監考，如果該授課教師還未被安排監考，則將其安排到他所擔任課程的班級監考。然后獲取所有在崗且愿意參加監考的教師信息，以相同的概率分配監考任務。
3 結 語
排考問題是一個有約束的、非線性的、模糊多目標優化的、難解的、時空組合的數學問題［4］。目前還沒有找到在多項式步驟內解決的有效算法，只能在一定范圍內尋求最優解。根據高校的具體實際所設計的排考算法實現較容易，求出解的合理性也較高，能適應大部分高校排考系統算法設計的要求。
［1］ 朱菊芳．高等教育學教程［M］．南京：南京師范大學出版社，1995．
［2］ 王玲．分布估計算法在排考中的應用［D］：［碩士學位論文］．長沙：湖南師范大學，2008．
［3］ 李紅，陳晏輝．高校課程考試管理的思考［J］．長春工業大學學報：高教研究版，2008，29（4）：31－32．
［4］ 張磊，張博鋒．分組遺傳算法優化大學考試時間表［J］．計算機工程與應用，2009，45（23）：236－238．
［5］ 胡荷芬．高?？荚囎詣影才潘惴ㄑ芯亢拖到y設計［D］：［碩士學位論文］．上海：上海師范大學，2008．
［6］ 唐洪英，周敏．基于分層次、貪心算法的排課系統的設計與實現［J］．微計算機信息，2006，22（3）：237－240．
［7］ 胡峰，王國胤．基于分治法的快速確定規則獲取算法［J］．模式識別和人工智能，2010，23（3）：349－356．
［8］ 常友渠，肖貴元，曾敏．貪心法的探討與研究［J］．重慶電力高等專科學校學報，2008，13（3）：40－42．
［9］ 宗大華，宗濤，陳吉人．操作系統［M］．北京：人民郵電出版社，2009．
猜你喜歡
《無機化學》課程教學改革云南化工(2021年6期)2021-12-21 07:31:42 最美教師快樂語文(2021年27期)2021-11-24 01:29:04 大山里的教師黃河之聲(2021年5期)2021-05-15 02:31:24 數字圖像處理課程混合式教學改革與探索內蒙古教育(2021年20期)2021-03-08 01:09:14 軟件設計與開發實踐課程探索與實踐計算機教育(2020年5期)2020-07-24 08:53:38 教師如何說課甘肅教育(2020年22期)2020-04-13 08:11:16 為什么要學習HAA課程？家庭影院技術(2019年11期)2019-12-09 09:14:30 未來教師的當下使命福建基礎教育研究(2019年3期)2019-05-28 23:14:43 教師贊小學生優秀作文(高年級)(2018年9期)2018-09-14 02:42:12 “學而時習之”的課程值得贊賞教育與職業(2014年1期)2014-04-17 14:28:07
駱紹燁
（莆田學院電子信息工程系，福建莆田 351100）
0 引 言
現代教育理論認為，考試是教育評價的一種重要手段，其作用主要表現在以下兩個方面：其一是評估教師的課堂教學效果，促使教師總結教學經驗，改進教學方法；其二是評價檢測學生的學習效果，了解學生對所學知識和技能的掌握情況和應用能力，促使學生學習以及幫助改進學習方法［1］。
傳統的考試安排方式主要是依靠教學管理人員的人工安排，雖然他們在考試安排中逐漸積累了一些經驗和方法［2］，但是，隨著專業的不斷增加和細化，組織考試的工作量越來越大［3］，而且組織考試的時間大多是在學期中或學期末，此時教學管理的工作又相對集中，時間有限，任務又重，人工管理的方式暴露出了不少的弊端。
計算機自動排考是一個時間表問題，把考試安排問題化為計算領域有約束的時空組合優化問題進行求解［4］。由于約束條件復雜，問題規模龐大，對于排考這類問題迄今為止還沒有找到在多項式步驟內解決的有效算法，只能在一定范圍內尋求最優解。
1 排考問題描述
從排考過程中涉及到的可能引起潛在資源競爭沖突的角度，排考問題涉及到的因素主要有：時間、課程、場地、班級和教師。其中班級又分為行政班級和考試班級。行政班級指招生時注冊的班級，每個行政班級有編號、名稱、院系、專業和學生人數。每個行政班同一時間只能考一門課程?？荚嚢喔拍畹漠a生主要是基于有些課程由于人數過多或者其它原因需要拆班考試。
1.1 約束條件
排考的約束條件可分為兩大類：硬約束和軟約束。
1．1．1 硬約束
硬約束表示必須遵守的約束條件。
硬約束主要包括以下幾個方面：
1）同一班級在同一時間不能考兩門不同的課程。
2）同一教師在同一時間不能安排兩個考場。
3）同一考卷的班級應在同一時間安排考試。
4）考場的容積必須大于在該處考試的學生的人數。這里所說的容積不是考場的總座位數，而應指按照考試要求所能排下的最大學生數。
5）安排監考的教師必須在崗。
1．1．2 軟約束
軟約束表示在排考過程中盡可能滿足的約束條件，但不滿足也無妨，軟約束條件的滿足與否往往與排考實際情況有關。
軟約束主要包括以下幾個方面：
1）該課程的授課教師應參加監考，且盡可能安排在該教師所授課班級監考。這樣可以方便解決考試中出現的諸如試卷不清等問題。
2）課程安排有一定間隔，讓學生有足夠備考時間。一天內一個班級盡可能只安排一門考試。
3）教師安排監考次數適當。
4）滿足監考教師監考意愿偏好。
5）在指定時間段內安排考試。
1.2 排考目標
由約束條件可以看出，對于排考問題實際上是一個組合規劃問題，但要求出問題的最優解卻是不可能的，雖然約束條件能幫助我們進行求解，但是隨著問題范圍的擴大，組合方案呈爆炸式增長，特別是高校的排考問題，其排考難度更大［5］。因而，我們必須放棄尋求最優解，事實上，迄今為止，對排考和排課問題的研究也證明了最優解是極難求出的，只能“退而求其次”，尋找問題的近似最優解。只要這個解能夠在滿足硬約束條件的前提下，盡可能地滿足軟約束，滿足各方面的需求，使得解決方案合理可行。
2 系統自動排考算法設計
隨著資源數量的增大，排考問題因考試編排選擇方案的劇增，就可能出現“組合爆炸”，致使排考問題變得錯綜復雜，從而直接影響到排考問題的解［6］。為了降低排考算法的復雜性，在自動排考時運用分治法的思想，將問題空間分解成多個小規?？臻g，分別求出各個小空間的解，再組成整個問題的解的方法。
分治法的思想就是將整個問題分成若干個問題后分而治之［7］。當要求解一個輸入規模為n，且n取值又相當大的問題時，直接求解往往是非常困難的，有的甚至根本沒法直接求出。每當遇到這類問題時，分治法往往能發揮很大的作用。任何一個可以用計算機求解的問題所需的計算時間都與其規模有關。問題的規模越小，越容易直接求解，解題所需的計算時間也越少［6］。
運用分治法解決排考問題，把問題空間逐層分解成多個小規?？臻g，可以減小問題規模。排考時，先將課程分成公共課與專業課兩種類型，因為公共課與專業課有著各自不同的特點。公共課課程數量少，但參加考試的班級較多，而專業課則恰恰相反。將兩種課程類型分開，有利于采取不同的分配方案，同時也降低了問題的規模。其次，在專業課排考時，將整個學校的考試安排調度分解成各個開課院系的考試安排，問題空間再次縮小。最后將排考過程分解成安排時間、安排場地和安排監考老師3個相對獨立的子問題。安排時間時，只需要考慮課程與時間的搭配；安排場地時，只需考慮考試班級與考試場地的搭配；安排監考教師時，只需保證監考教師的監考時間不沖突即可。由以上可以看出，在逐層的分解過程中，求解的難度也不斷降低，排考得到了更簡單和更迅速的求解。分解到位的排考算法主要通過以下步驟實現。
1）選取課程。為了減少排考過程中可能出現的沖突，采取先難后易的原則，不好安排的課程先排，即容易在排考時出現沖突的、排考條件要求較難滿足的課程優先進行排考。如果這些課程在排考后期才開始安排，此時很多資源已被占用。因為雖然總的資源數量是一定的，但到了排考的后期，剩余的資源特別可能會出現類似存儲管理中的資源碎片問題，即大量空余的資源很少，取而代之的是分布零散的資源碎片。這時為這些較難安排的課程尋找到適合的資源就變得更難了，也就影響了排考的順利進行。排考過程中，課程的參加考試班級數、參加考試班級的人數、參加考試班級的考試課程數等多個因素都會影響課程的考試安排難度，但影響最大的因素還是課程的參加考試班級數。
2）貪心法安排時間。選定待排考課程之后，接著就是為課程安排考試時間，公共課的考試時間由排考人員直接指定，專業課程的考試時間在計算機自動排考時是由系統根據權值法和貪心法選定。
在安排專業課程考試時，排考人員首先需要計算每個可排考時間的權值。管理員可以根據需要將一天的考試時段分成1～5個不等的時間段。將所有可以排考的時段的權值存放在權值數組periodstate［］中，periodstate［X］表示第X個時間段的權值。當我們需要表示考試安排區間中的第M天的第L個時段的權值時，有如下公式：
式中：N——每天可排考的時段數。
在為課程選擇考試時間時，首先初始化時段權值數組，將所有的考試時段的初始權值為同一值10 000。然后逐時段分析計算各個考試時段的權值。權值的計算方法如下：
首先，如果該時段排考課程中的任何一個參考班級在此時段已安排了考試，則該時段的權值為0。其次，為了使得軟約束中的要為學生留有一定的備考時間的條件盡量得到滿足，一個班級盡可能不在一天安排多場考試，即一天在可能的情況下最多只安排一場考試。因此，檢查該天是否有班級已安排了考試課程，如果有，每增加一個已在該天安排了考試課程的班級，則相應地降低該時段的部分權值。
在使用權值的計算辦法處理完所有時段的權值后，就可以使用貪心策略來選擇課程的考試時間了。貪心法是一種改進了的分級處理方法，就是在對問題求解時，總是做出在當前看來是最好的選擇，每一步都應是局部最優解，不從整體最優上加以考慮，所做出的僅是在某種意義上的局部最優解［8］。貪心法通過不斷求解局部最優解逐步構造全局解的方式，對許多問題可以產生整體最優解，即使不能得到整體最優解，也能找到最優解的較好的近似解。并且排考問題實際上并不一定需要找出整體最優解，排考問題最優解的定義也是個難題。所以在很大程度上，只需要求得一個次優解或者滿足解即可。在安排課程考試時間上采用貪心法，能在保證速度的前提下求得局部最優解，符合速度和效用的平衡，從而獲得整體最優解的良好特性，進而使其在排考系統的應用中能夠發揮其主要的特性。
3）最佳適應法安排場地。最佳適應算法（Best Fit）是動態存儲分配解決方案中最為常見的一種方案。最佳適應算法就是在內存空間中為將要加入的作業選擇大于該作業需要的空間大小，并且是最小的內存空間來存放該作業［9］。排考時的安排考試場地與模擬內存分配十分類似，可以模擬其分配方式。
安排考試場地，首先必須從數據庫中獲取在排的考試班級的人數K，接著從數據庫中獲取屬于開考班級院系且容積大于K的所有考試場地的信息，然后逐個考試場地進行比較選擇。比較選擇時，在確定考試場地在安排的課程考試時間時是空閑的情況下，計算考試場地容積S與班級人數K的差值，與已有的場地中的容積與班級人數之差的最小值MIN（S－K）做比較。如果當前的S－K值更小，則記錄下當前的考試場地編號和新的MIN（S－K），否則直接選取下一個場地。如此判斷比較直至比較完所有的考試場地，此時記錄的考試場地即是算法所求的場地。
4）等概率分配法安排監考教師。在安排了考試的時間和考試場地之后，最后要做的是安排監考教師。依據高校的有關考試規定，每個考場安排兩位監考教師監考。監考教師原則上選取學生所在系的教師。在安排監考教師時應考慮教師的在崗情況及監考意愿。同時，在滿足教師監考意愿的前提下，應考慮教師工作量的均衡，因而對于可任意參加監考的教師使用等概率分配法來安排監考教師。為了方便解決考試中可能出現的一些問題，在安排監考時，優先安排授課教師參加監考，如果該授課教師還未被安排監考，則將其安排到他所擔任課程的班級監考。然后獲取所有在崗且愿意參加監考的教師信息，以相同的概率分配監考任務。
3 結 語
排考問題是一個有約束的、非線性的、模糊多目標優化的、難解的、時空組合的數學問題［4］。目前還沒有找到在多項式步驟內解決的有效算法，只能在一定范圍內尋求最優解。根據高校的具體實際所設計的排考算法實現較容易，求出解的合理性也較高，能適應大部分高校排考系統算法設計的要求。
［1］ 朱菊芳．高等教育學教程［M］．南京：南京師范大學出版社，1995．
［2］ 王玲．分布估計算法在排考中的應用［D］：［碩士學位論文］．長沙：湖南師范大學，2008．
［3］ 李紅，陳晏輝．高校課程考試管理的思考［J］．長春工業大學學報：高教研究版，2008，29（4）：31－32．
［4］ 張磊，張博鋒．分組遺傳算法優化大學考試時間表［J］．計算機工程與應用，2009，45（23）：236－238．
［5］ 胡荷芬．高?？荚囎詣影才潘惴ㄑ芯亢拖到y設計［D］：［碩士學位論文］．上海：上海師范大學，2008．
［6］ 唐洪英，周敏．基于分層次、貪心算法的排課系統的設計與實現［J］．微計算機信息，2006，22（3）：237－240．
［7］ 胡峰，王國胤．基于分治法的快速確定規則獲取算法［J］．模式識別和人工智能，2010，23（3）：349－356．
［8］ 常友渠，肖貴元，曾敏．貪心法的探討與研究［J］．重慶電力高等專科學校學報，2008，13（3）：40－42．
［9］ 宗大華，宗濤，陳吉人．操作系統［M］．北京：人民郵電出版社，2009．
猜你喜歡
云南化工(2021年6期)2021-12-21 07:31:42
快樂語文(2021年27期)2021-11-24 01:29:04
黃河之聲(2021年5期)2021-05-15 02:31:24
內蒙古教育(2021年20期)2021-03-08 01:09:14
計算機教育(2020年5期)2020-07-24 08:53:38
甘肅教育(2020年22期)2020-04-13 08:11:16
家庭影院技術(2019年11期)2019-12-09 09:14:30
福建基礎教育研究(2019年3期)2019-05-28 23:14:43
小學生優秀作文(高年級)(2018年9期)2018-09-14 02:42:12
教育與職業(2014年1期)2014-04-17 14:28:07
