2、空間染色模型描述

2.1、建立立方體染色模型

我們分析一下排課表就會發現，編制排課表就是要把教師、班級、課程等信息安排在某天、某時的某個教室所對應的位置上，在符合各種約束條件的前提下，用盡量少的教室安排盡量多的課程。因此，我們不妨將這個問題模型化。以周天（ ）、課程（ ）和 時間單元（ ）為維數，建立一個三維坐標系（如圖1）。由圖，我們不難看出，該空間中垂直于 軸的任意一個面 ，即對應著排課表中的一門課程，我們只要把相關的教室信息根據約束條件添加到面中對應的點上即可。同時，為了方便使用數學符號表達，我們將每個教室及其相關信息抽象化為一種顏色，不同的教室為不同的顏色。那么，編制排課表的過程就是求解最少顏色種類的過程，即是對立方體進行染色的過程。這一好處在于，我們可以將眾多的約束條件轉換為空間坐標系中點、線、面之間的關系，非常清晰化，并且便于數學表達和在計算機上實現。同時也將排課表問題成功地轉化為點、線、面可區別的立方體染色。

 圖 1

2.2、顏色值以及排課表的數據結構

顏色值的數據結構：顏色值包含了教室的信息，我們把每一個顏色定義為一個結構體的對象。設定所有的顏色值是一個集合 （），集合中的每一個元素代表一種顏色。每個元素定義為一個結構體 的對象，該結構體包括對象的教室編號、教室容量、教室類型。具體定義如下

Public Structure

        Dim as integer‘教室編號

        Dim   as integer ‘教室容量

        Dim as integer ‘教室類型

End Structure

排課表的數據結構：從空間模型來看，繪制排課表，即是將空間中的某個點根據約束條件添加顏色值（允許為空）。因此我們可以用一個三維數組來表示排課表的結構，即 ，其中， 表示一周內的某個教學日， 表示一天內的某個課次（即某個教學單元）， 表示某門課程，即課程編號，數組中存儲的是教室編號，即顏色值。

課程的數據結構：排課表中每一個門課程都包含了許多信息，如教師、班級、單雙周安排等，因此，我們把所有的課程放到一個數組 （）中，數組（）的每一個元素均是結構體 的對象，定義如下：

Public Structure

        Dim as integer‘教師編號

        Dim   as integer ‘班級編號

        Dim as integer ‘課程編號

        Dim as interger ‘學生數量

           Dim As Integer ‘一周內對應課程的次數

End Structure

2.3、在空間坐標系中映射約束條件

此時，我們不難理解，編制排課表即是對空間坐標系中的點著色，而約束條件即是空間坐標系各點顏色值之間的關系以及著色點的屬性之間的關系。因此，需要把約束條件映射到空間坐標系上，這樣自然語言表述的約束條件即可清晰地轉化為空間坐標系的點、線、面上顏色值之間的關聯與約束。為方便描述，我們將軸視為 軸， 軸視為 軸， 軸視為 軸，原點為 點。舉個例子，將下面的基本約束條件進行轉換：

“在同一天同一個課次同一教師不能給兩門不同的課程上課” “對于任意的直線 面  ， ， …… 是直線上的點，則    …… ”。

3、算法描述

在排課的染色算法中，根據基本約條件（1）可知，如果空間坐標系中垂直于 面的任意直線上點的染色值不為空，則各個點的顏色值均不同，這類似于路的點染色。在滿足此條件的同時，再根據其他約束條件對空間各點進行染色，以下是該算法的具體步驟。

<1>初始化空間坐標構成的三維數組 。

<2>開始時，解空間很大，從周一至周五的每個 面上先染 個顏色（的值為 的長度），并生成個顏色值 ， ，……， （  ……），存儲到教室集合 。

<3>生成 組坐標值（ ， ， ），（ ， ， ），……（ ， ， ）（ ， ， ， 為課程編號的最大值， 隨機產生）。

<4>判斷是否滿足條件（，），如果滿足，則將顏色值，，……，添加到數組 ， ，……中

， （ ）. -1……（）. -1；否則，返回第4步。

<5>備份數組 至數組 中。

<6>隨機生成一個課程編號 ，設整型變量 =0。

<7>判斷 （）. 是否為零，如果為零返回第7步，否則，進行下一步，并且+1。

<8>隨機生成一組坐標值 （    ， ， =）。

<9>存在 ， ，……，  是直線 上的顏色值，每個顏色所在點的Z軸坐標值為 ， ，……， 。如果（）. （,,……, ）. 并且（）. （）（,,……, ）. （），執行下一步，否則，如果<4返回第9步，否則返回第7步。

<10>在點 上添加顏色值，如果（）. >().，并且 ，……，，則=，（）. -1。否則，將替換為中的顏色 ，如果中的顏色均不合適，則產生新的顏色 ，=，（）. -1并將添加到顏色集合中。

<11>遍歷軸的課程編號，如果存在任意課程編號 ，（）. 0，則返回步驟7；否則排課完畢，打印排課表。

4、算法分析

我們假定一周上課的天數為 ，一天內的課次為 ，需要安排的課次的總數為 ，教室數目為 ，根據平均染色的思想， ，由于還有其他約束條件，我們通過實驗得知，×2。本算法根據約束條件，借鑒某些圖的染色算法（如路和圈的點可區別全染色），采取個體與集合相結合的染色方法，具有較好的收斂性。由上面算法的詳細步驟，我們可以得到該算法在最壞情況下的時間復雜度為 ，較為理想。

5、實驗和總結

我們根據立方體染色的思想，在計算機上實現了本校電信學院2007至2008第一學年排課表，如表1。共有64個任課教師，45個班級，37門課程，共用教室數目是16。表1中每個單元格的數字表示課程編號，一個課程編號表示該課程的一個課次。下面結果中，課程數量較為平均，每天的最后一節課盡量不安排課程，并且滿足基本約束條件、硬約束條件以及部分軟約束條件�？偟膩碚f，排課結果較為合理，本文算法能夠較好地解決實際應用的問題。通過“立方體染色”染色的思想，我們使排課表的編制過程變的更加清晰化和數學化，因此，立方體染色為解決排課表問題提供了一條新的途徑。

表一

參考文獻：

[1]EVEN S,ITAI A,SHAMIR A.On the complexity of timetable and multicommodity flow          problems[J].SIAM Journal on Computing,1976,5(4):691-703.

[2]張忠甫、陳祥恩、李敬文等，關于圖的鄰點可區別全染色，中國科學，A輯，數學，Vol.34,No.5,(2004),574-583

[3]翟音、羅萍， 遺傳算法在高校排課問題中的應用，廊坊師范學院學報，2008，8，4.