約束滿足問題(高校排課問題)

1、高校排課問題-CSP：SMU報(bào)告人：Charlie1目錄變量及值域自約束和關(guān)系約束優(yōu)化約束與解的質(zhì)量改進(jìn)回溯算法2高校排課問題在高校排課問題中，一個(gè)排課任務(wù)是指為一次教學(xué)任務(wù)做出的場(chǎng)地及時(shí)間的選擇，這種選擇必須滿足教學(xué)任務(wù)自身的條件需求，并且不能與其他排課任務(wù)發(fā)生沖突。這里，排課任務(wù)是變量，可供選取的資源為問題的值域，而需求與沖突就是約束。由上可見，排課問題可以看做一個(gè)約束滿足問題，問題的求解表現(xiàn)為對(duì)各排課任務(wù)尋找滿足約束的資源，解的優(yōu)劣也可以通過約束來表征。3變量及值域 在高校排課問題中，排課任務(wù)應(yīng)具有課程、教師、班級(jí)、教學(xué)場(chǎng)地、教學(xué)時(shí)間等基本屬性。 為便于問題的簡(jiǎn)化，不妨將教學(xué)場(chǎng)地和教學(xué)時(shí)

2、間看作排課任務(wù)的一個(gè)屬性。在這里，教學(xué)場(chǎng)地與教學(xué)時(shí)間同時(shí)也具有自身的屬性。4自約束自約束：指由單一排課任務(wù)自身的條件需求而規(guī)定。例如：排課任務(wù)對(duì)教學(xué)場(chǎng)地的類別、容量的要求及教學(xué)時(shí)間節(jié)次的要求初始化過程中，可以將其作用于相應(yīng)排課任務(wù)的值域。5關(guān)系約束關(guān)系約束通常是動(dòng)態(tài)的二元或高階約束，但高階約束一般總可以轉(zhuǎn)化為二元約束，一個(gè)排課任務(wù)的取值通過關(guān)系約束而受到相關(guān)排課任務(wù)的影響。如為回避沖突而規(guī)定的約束、保證同一課程的不同教學(xué)任務(wù)有合理的時(shí)間間隔及使其在相同地點(diǎn)進(jìn)行而規(guī)定的約束，都是典型的關(guān)系約束。由于關(guān)系約束是動(dòng)態(tài)的，它們一般在求解過程中由相關(guān)排課任務(wù)的賦值來觸發(fā)。6約束舉例某排課任務(wù)具有自約束：

3、兩個(gè)具有相同班級(jí)的排課任務(wù)具有關(guān)系約束： 它由對(duì) 的賦值來觸發(fā)。7優(yōu)化約束與解的質(zhì)量高校排課問題具有多個(gè)優(yōu)化目標(biāo)，將目標(biāo)通過約束表征而得到高質(zhì)量解的間接求解方法，通常是有效的。優(yōu)化約束是針對(duì)高校排課問題的優(yōu)化目標(biāo)而建立的約束。它可以是自約束，也可以是關(guān)系約束。當(dāng)排課問題的解滿足連同優(yōu)化約束在內(nèi)的全部約束條件時(shí)，則可以認(rèn)為解是高質(zhì)量的。8最小剩余值啟發(fā)式+前向檢驗(yàn)的改進(jìn)回溯算法S1 獲取課程、教師、班級(jí)、教學(xué)場(chǎng)地、教學(xué)時(shí)間及約束信息，建立排課任務(wù)并根據(jù)自約束確定各排課任務(wù)變量的值域，如存在值域?yàn)榭眨瑒t問題無解；S2 i=1（ i為當(dāng)前待排課任務(wù)序號(hào)）；S3 如果i大于排課任務(wù)數(shù)量，則得到問題解而終止；S4 采用最小剩余值啟發(fā)式，按值域空間大小對(duì)剩余排課任務(wù)進(jìn)行升序排列，即優(yōu)先安排可選資源少的排課任務(wù)；S5 逐次考察排課任務(wù)變量 值域中的元素，直至利用關(guān)系約束的前向檢驗(yàn)，檢測(cè)到所有剩余排課任務(wù)均存在可選資源；S6 如果變量 的值域已越界，則i=i-1；否則，對(duì)排課任務(wù) 賦值，并修改相關(guān)剩余排課任務(wù)的值域，i=i+1，并轉(zhuǎn)S3；S