數(shù)據(jù)庫(kù)系統(tǒng)中應(yīng)用A*算法的程序模板研究

林峰，鄭愛媛

(福建商學(xué)院 信息管理工程系，福建 福州，350012)

數(shù)據(jù)庫(kù)系統(tǒng)中應(yīng)用A*算法的程序模板研究

林峰，鄭愛媛

(福建商學(xué)院 信息管理工程系，福建 福州，350012)

數(shù)據(jù)庫(kù)系統(tǒng)已經(jīng)獲得了廣泛的應(yīng)用，借助它能處理現(xiàn)實(shí)生活中許多復(fù)雜的事務(wù)性的數(shù)據(jù)工作，A*算法也有許多成功的應(yīng)用，但是，對(duì)結(jié)合利用數(shù)據(jù)庫(kù)技術(shù)與A*算法來(lái)解決實(shí)際問(wèn)題的探索做得還很不夠。A*算法的搜索空間大，往往需要花費(fèi)幾十分鐘甚至更長(zhǎng)的時(shí)間才能搜索到問(wèn)題的解，因此，采用A*算法的數(shù)據(jù)庫(kù)系統(tǒng)可能由于等待執(zhí)行結(jié)果的時(shí)間太長(zhǎng)而不適合實(shí)際需要。針對(duì)這些不足，設(shè)計(jì)了一套在數(shù)據(jù)庫(kù)系統(tǒng)中應(yīng)用A*算法的程序模板，套用這個(gè)模板開發(fā)的自動(dòng)排課系統(tǒng)能夠在很短的時(shí)間內(nèi)處理好一個(gè)典型的中學(xué)排課工作，滿足實(shí)際需求。結(jié)果表明，該程序模板具有指導(dǎo)性價(jià)值。

A*算法；次級(jí)啟發(fā)函數(shù)；數(shù)據(jù)庫(kù)技術(shù)；自動(dòng)排課

A*算法是人工智能領(lǐng)域中最重要的算法之一，它的經(jīng)典應(yīng)用是解決數(shù)碼問(wèn)題[1]。目前，A*算法主要用于解決路徑規(guī)劃問(wèn)題[2]，在電子游戲和無(wú)人機(jī)飛行控制等領(lǐng)域都有很多應(yīng)用[3-4]。A*算法取得如此大的成功，使得研究利用A*算法來(lái)解決現(xiàn)實(shí)生活中其他問(wèn)題的工作變得很有必要。A*算法是狀態(tài)空間圖中的啟發(fā)式搜索方法，狀態(tài)空間圖中的節(jié)點(diǎn)就是狀態(tài)。在計(jì)算機(jī)應(yīng)用程序中，狀態(tài)由數(shù)據(jù)構(gòu)成。在數(shù)碼問(wèn)題或路徑規(guī)劃等問(wèn)題中，構(gòu)成狀態(tài)的數(shù)據(jù)很簡(jiǎn)單，一般用二維或三維數(shù)組來(lái)表示。因此，在應(yīng)用程序的運(yùn)行期間，這些數(shù)據(jù)可以一直保持在內(nèi)存中，應(yīng)用程序的運(yùn)行速度較快，等待輸出結(jié)果的時(shí)間較短?，F(xiàn)實(shí)生活中的其他問(wèn)題需要處理的數(shù)據(jù)可能很復(fù)雜，數(shù)據(jù)量也很大，這些問(wèn)題一般要借助于數(shù)據(jù)庫(kù)系統(tǒng)來(lái)實(shí)現(xiàn)。數(shù)據(jù)庫(kù)系統(tǒng)中對(duì)數(shù)據(jù)的訪問(wèn)和操作都要涉及到物理層面的讀寫過(guò)程，并且所有的數(shù)據(jù)不能同時(shí)保持在內(nèi)存中，因此，利用A*算法的數(shù)據(jù)庫(kù)系統(tǒng)的應(yīng)用程序的運(yùn)行速度很慢，需要花費(fèi)很長(zhǎng)時(shí)間來(lái)等待輸出結(jié)果，限制了這類應(yīng)用程序的推廣和應(yīng)用。

利用A*算法的數(shù)據(jù)庫(kù)系統(tǒng)把狀態(tài)保存在數(shù)據(jù)庫(kù)表中，每一個(gè)狀態(tài)都是由多條記錄組成的。這樣的系統(tǒng)在進(jìn)行狀態(tài)擴(kuò)展時(shí)，以下兩個(gè)環(huán)節(jié)影響了它的工作效率，造成等待運(yùn)行結(jié)果的時(shí)間過(guò)長(zhǎng)：(1)構(gòu)造子狀態(tài)的數(shù)據(jù)時(shí)，需要從父狀態(tài)進(jìn)行大量的數(shù)據(jù)拷貝，這需要進(jìn)行大量的、重復(fù)的把數(shù)據(jù)插入到數(shù)據(jù)庫(kù)表中的操作；(2)為了避免搜索過(guò)程陷入循環(huán)，如果擴(kuò)展出來(lái)的新狀態(tài)與任何已經(jīng)存在的狀態(tài)相同，那么必須拋棄這個(gè)新狀態(tài)，這需要進(jìn)行狀態(tài)之間的比較，即把組成一個(gè)狀態(tài)的多條記錄與組成另一個(gè)狀態(tài)的多條記錄進(jìn)行比較，會(huì)涉及到大量的、重復(fù)的對(duì)數(shù)據(jù)表的查詢操作。

利用數(shù)據(jù)庫(kù)技術(shù)與巧妙的設(shè)計(jì)，能夠有效減少上述兩個(gè)瓶頸環(huán)節(jié)造成的不利影響。針對(duì)第一個(gè)環(huán)節(jié)，本文提供了一個(gè)能在狀態(tài)之間實(shí)現(xiàn)數(shù)據(jù)共享的設(shè)計(jì)方案，避免了數(shù)據(jù)拷貝過(guò)程。因?yàn)?，父子狀態(tài)之間絕大多的數(shù)據(jù)都是相同的，以8數(shù)碼問(wèn)題為例，不相同的數(shù)據(jù)只占全部數(shù)據(jù)的2/9。針對(duì)第二個(gè)環(huán)節(jié)，本文提供了一個(gè)利用狀態(tài)特征值進(jìn)行狀態(tài)比較的設(shè)計(jì)方案，狀態(tài)特征值是一個(gè)簡(jiǎn)短的字符串，它與狀態(tài)一一對(duì)應(yīng)，并且從狀態(tài)中提取特征值的過(guò)程簡(jiǎn)單、容易實(shí)現(xiàn)。老狀態(tài)的特征值存放在專門的數(shù)據(jù)庫(kù)表中，把新狀態(tài)的特征值作為SQL語(yǔ)言的select語(yǔ)句中的where子句的條件，就能夠很容易實(shí)現(xiàn)新狀態(tài)與老狀態(tài)的比較。這兩個(gè)設(shè)計(jì)方案具有普遍性，因此，可以作為程序模板來(lái)套用。

1.A*算法

圖1是狀態(tài)擴(kuò)展的模型。算子表示動(dòng)作，動(dòng)作執(zhí)行前后的環(huán)境稱為狀態(tài)。算子使?fàn)顟B(tài)發(fā)生變化，從執(zhí)行前狀態(tài)得到執(zhí)行后狀態(tài)，執(zhí)行后狀態(tài)稱為執(zhí)行前狀態(tài)的子狀態(tài)，這個(gè)過(guò)程稱為狀態(tài)擴(kuò)展。特定的執(zhí)行前狀態(tài)可以通過(guò)不同的算子(參數(shù))得到多個(gè)不同的執(zhí)行后狀態(tài)，所以，狀態(tài)和子狀態(tài)之間是1n的關(guān)系。連續(xù)多次的狀態(tài)擴(kuò)展，構(gòu)成了一個(gè)有向圖，即狀態(tài)空間圖，狀態(tài)是圖的節(jié)點(diǎn)，算子是圖的邊。

圖1 狀態(tài)擴(kuò)展模型Fig.1 State-expansion model

A*算法是狀態(tài)空間圖中的啟發(fā)式搜索方法。搜索的起始節(jié)點(diǎn)記為n0，搜索過(guò)程中的某個(gè)中間節(jié)點(diǎn)記為n，定義以下符號(hào)：

f (n) = g(n)+h(n)：從n0經(jīng)過(guò)n到達(dá)目標(biāo)節(jié)點(diǎn)的最小路徑的代價(jià)；

g(n)：從n0到n的一個(gè)最小代價(jià)路徑的代價(jià)；

h(n)：n到目標(biāo)節(jié)點(diǎn)最小代價(jià)路徑的實(shí)際代價(jià)。

在n處，有多條可以選擇的搜索路徑，與之對(duì)應(yīng)的有一系列 f (n)，選擇 f (n)值最小的路徑進(jìn)行搜索，就最有可能以最少的代價(jià)得到問(wèn)題的解。這個(gè)搜索過(guò)程稱為啟發(fā)式搜索， f (n)稱為啟發(fā)函數(shù)。A*算法的具體步驟：

1)生成一個(gè)只包含開始節(jié)點(diǎn)n0的搜索圖G，把n0放在一個(gè)叫OPEN的列表上；

2)生成一個(gè)列表CLOSED，它的初始值為空；

3)如果OPEN為空，則失敗退出；

4)選擇OPEN上的第一個(gè)節(jié)點(diǎn)，把它從OPEN中移入CLOSED，稱該節(jié)點(diǎn)為n；

5)如果n是目標(biāo)節(jié)點(diǎn)，順著G中從n到n0的指針找到一條路徑，獲得解，成功退出；

6)擴(kuò)展節(jié)點(diǎn)n，生成其后繼節(jié)點(diǎn)集M。丟棄M中與G中任何一個(gè)節(jié)點(diǎn)值相同的成員，把M中其余的成員添加到G中，使它們成為n的后繼；

7)把新加入G中的節(jié)點(diǎn)加入到OPEN中，對(duì)M的每一個(gè)已在OPEN中或CLOSED中的成員m，如果到目前為止到達(dá)m的最好路徑通過(guò)n，就把它的指針指向n。對(duì)已在CLOSED中的M的每一個(gè)成員，重定向它在G中的每一個(gè)后繼，以使它們順著到目前為止發(fā)現(xiàn)的最好路徑指向它們的祖先；

8)根據(jù) f (n)值，以從小到大的順序重新安排OPEN中節(jié)點(diǎn)的順序；

9)返回第3步。

2.實(shí)現(xiàn)數(shù)據(jù)共享的程序模板

在狀態(tài)之間實(shí)現(xiàn)數(shù)據(jù)共享的目的是：(1)子狀態(tài)能最大限度地重用祖先狀態(tài)的數(shù)據(jù)；(2)在擴(kuò)展子狀態(tài)時(shí)，通過(guò)采用盡量少的補(bǔ)償操作使其他狀態(tài)的數(shù)據(jù)不會(huì)發(fā)生改變。采用3個(gè)方法來(lái)實(shí)現(xiàn)這個(gè)目的。

(1)有效組織狀態(tài)的數(shù)據(jù)。按照下列的公式對(duì)狀態(tài)的數(shù)據(jù)進(jìn)行有效的組織：

狀態(tài)的數(shù)據(jù)=往祖先路徑上每一個(gè)狀態(tài)的重用數(shù)據(jù)+本狀態(tài)的專用數(shù)據(jù)

所有狀態(tài)的數(shù)據(jù)保存在名字為tblData數(shù)據(jù)庫(kù)表中(根據(jù)具體情況，狀態(tài)數(shù)據(jù)也可以保存在多個(gè)數(shù)據(jù)庫(kù)表中)，每一個(gè)狀態(tài)由若干條記錄組成。在tblData中添加名字為stateId和stateId0的兩個(gè)字段，它們的數(shù)據(jù)類型都為整型，其中stateId用來(lái)標(biāo)識(shí)記錄所屬的狀態(tài)。利用stateId和stateId0字段值的組合(必有一個(gè)字段值為-1，另一個(gè)字段值為狀態(tài)號(hào)n)把tblData表中記錄的分為重用和專用兩種：

·重用的記錄：stateId=n并且stateId0=-1，這些記錄可以被子孫狀態(tài)共享；

·專用的記錄：stateId=-1并且stateId0=n，這些記錄只能被狀態(tài)自身使用。

初始狀態(tài)的所有記錄都被初始化為stateId=0，stateId0=-1。

圖2是一個(gè)狀態(tài)空間圖，圖中的節(jié)點(diǎn)等同于狀態(tài)。從初始狀態(tài)S0依次擴(kuò)展出子狀態(tài)S1、S2、…、S10，從狀態(tài)S1依次擴(kuò)展出子狀態(tài)S11、S12、…、S16，從狀態(tài)S12依次擴(kuò)展出子狀態(tài)S20、S21、…、S28，等等。

圖2 狀態(tài)空間圖Fig.2 State-space graph

按照上述公式，讀取任意狀態(tài)數(shù)據(jù)的SQL語(yǔ)言的select語(yǔ)句(僅列出where子句)：

S0：where (stateId=0 and stateId0=-1) or (stateId =-1 and stateId0=0)

S2：where(stateId=0 and stateId0=-1) or (stateId=2 and (stateId0=-1) or (stateId=-1 and stateId0=2)

S16：where (stateId=0 and stateId0=-1) or (stateId=1 and stateId0=-1) or (stateId=16 and stateId0=-1) or (stateId =-1 and stateId0=16)

(2)對(duì)受影響狀態(tài)進(jìn)行數(shù)據(jù)補(bǔ)償。在擴(kuò)展?fàn)顟B(tài)的過(guò)程中，祖先狀態(tài)的數(shù)據(jù)可能會(huì)被改變，這會(huì)影響到包括該祖先狀態(tài)在內(nèi)的其他狀態(tài)的數(shù)據(jù)。因此，采用delete取代update來(lái)改變祖先狀態(tài)的數(shù)據(jù)，采用insert對(duì)受到影響的狀態(tài)進(jìn)行數(shù)據(jù)補(bǔ)償。以S21為例，其祖先狀態(tài)依次是S12、S1和S0。假設(shè)在擴(kuò)展出S21時(shí)，刪除了S0中的某條記錄(stateId=0，stateId0=-1)，那么必須按表1中列出的情況對(duì)受影響的狀態(tài)進(jìn)行補(bǔ)償。

表1 補(bǔ)償方法

需要補(bǔ)償?shù)臓顟B(tài)分為一類狀態(tài)和二類狀態(tài)。一類狀態(tài)是當(dāng)前狀態(tài)S21的祖先，對(duì)它們的補(bǔ)償不能被當(dāng)前狀態(tài)S21重用。結(jié)合上述列出的SQL語(yǔ)句，可以看出，擴(kuò)展S21前后，其他狀態(tài)的數(shù)據(jù)都保持不變。

進(jìn)行數(shù)據(jù)補(bǔ)償?shù)年P(guān)鍵點(diǎn)是：(1)確定需要補(bǔ)償?shù)臓顟B(tài)；(2)對(duì)它們進(jìn)行分類。假設(shè)，新擴(kuò)展出的狀態(tài)為S_n，被改變數(shù)據(jù)的祖先狀態(tài)為S_0。參考圖2中的方位，S_n處于下方，S_0處于上方。程序模板的偽代碼如下：

Being

按S_0到S_n的路徑，提取節(jié)點(diǎn)，存放到list中；

For i=0 to n-2 Do

Begin

提取list[i]的直接孩子節(jié)點(diǎn)，存放到list_c中；

For each chlidNode in list_c Do

Begin

If chlidNode屬于list Then

chlidNode是一類節(jié)點(diǎn)

else

chlidNode是二類節(jié)點(diǎn)；

End；

End；

End。

(3)重構(gòu)初始狀態(tài)。隨著狀態(tài)擴(kuò)展的不斷進(jìn)行，一方面，狀態(tài)空間圖(實(shí)際上是一棵樹)的層次不斷增加，需要進(jìn)行補(bǔ)償?shù)臓顟B(tài)的數(shù)量會(huì)急劇增加，大量的補(bǔ)償操作造成系統(tǒng)的運(yùn)行速度變慢；另一方面，讀取狀態(tài)數(shù)據(jù)的SQL語(yǔ)言中的select語(yǔ)句的where子句中的or運(yùn)算符的數(shù)量也會(huì)急劇增加，最終將會(huì)超過(guò)數(shù)據(jù)庫(kù)系統(tǒng)的限制，造成系統(tǒng)異常。因此，必須在適當(dāng)?shù)那闆r下，選擇某個(gè)比較好的狀態(tài)(可以是最接近目標(biāo)的狀態(tài))進(jìn)行重構(gòu)，即拋棄其他所有的狀態(tài)，把選中的狀態(tài)作為執(zhí)行新一輪A*算法的初始狀態(tài)。

3.利用特征值進(jìn)行狀態(tài)比較的程序模板

綜合A*算法的其他要點(diǎn)，設(shè)計(jì)tblAStar數(shù)據(jù)庫(kù)表，如表2所示。

表2 tbl AStar

程序模板的偽代碼如下：

Begin

把tblAStar表清空；

擴(kuò)展子狀態(tài)，存放到list中；

For each子狀態(tài)in list Do

Begin

val_stateStr = 子狀態(tài)特征值；

執(zhí)行select count(*) from tblAStar where state Str = val_stateStr；

If 返回值為0 Then

把val_stateStr插入talAStar中

Else

拋棄子狀態(tài)；

End；

End。

每一個(gè)狀態(tài)都是由數(shù)量相同的記錄的數(shù)據(jù)集組成，對(duì)兩個(gè)狀態(tài)進(jìn)行比較涉及這兩組數(shù)據(jù)集的比較運(yùn)算，并且需要依次讀取每一個(gè)被比較的狀態(tài)的數(shù)據(jù)，這非常耗費(fèi)計(jì)算機(jī)系統(tǒng)的資源。按照這個(gè)程序模板來(lái)開發(fā)程序，完全避免了上述缺點(diǎn)，取而代之的是簡(jiǎn)單的提取狀態(tài)特征值的運(yùn)算和一個(gè)高效的SQL語(yǔ)句的執(zhí)行運(yùn)算，大大提高了應(yīng)用程序的工作效率。新擴(kuò)展出來(lái)的有效的狀態(tài)也被不斷地添加到tblAStar表中，為隨后的擴(kuò)展所需要進(jìn)行的狀態(tài)比較操作準(zhǔn)備好了數(shù)據(jù)。

4.程序模板的應(yīng)用實(shí)例——中小學(xué)排課系統(tǒng)

由于約束條件非?？量?，全部合理地安排好學(xué)校的課程表是一個(gè)非常困難并且耗時(shí)的工作。目前，在排課工作中，計(jì)算機(jī)排課軟件一般只起輔助作用，大部分工作都由人工完成。開發(fā)能夠完全自動(dòng)排課的應(yīng)用軟件很有必要。自動(dòng)排課應(yīng)用軟件屬于數(shù)據(jù)庫(kù)系統(tǒng)軟件。以下介紹套用這兩個(gè)程序模板開發(fā)自動(dòng)排課系統(tǒng)的幾個(gè)技術(shù)要點(diǎn)。

(1)排課工作的切入點(diǎn)和數(shù)據(jù)前處理。中小學(xué)的課程表是一種二維表，由星期一到星期五組成課程表的列，由第1節(jié)到第8節(jié)組成課程表的行。用wd表示行，用ln表示列，用wlCell表示課程表中的某一節(jié)課。表3是某個(gè)老師課程表的一個(gè)樣例。

表3 某個(gè)老師的課程表

中小學(xué)的特點(diǎn)是：學(xué)生固定在班級(jí)中上課；每一節(jié)課占用的時(shí)間段是固定的；每一節(jié)課在特定的教室上課；班級(jí)的每一門課程由固定的老師任課；每一個(gè)任課老師可以負(fù)責(zé)多個(gè)班級(jí)。綜合上述因素，得出結(jié)論：首先，中小學(xué)的課程表問(wèn)題是由學(xué)生、任課老師和教室這三個(gè)資源共同約束的同時(shí)段任務(wù)安排問(wèn)題；其次，任課老師、課程、班級(jí)(學(xué)生)和教室的組合數(shù)據(jù)是排課工作的切入點(diǎn)。為了保證教學(xué)進(jìn)程同步，必須按照輪次安排任課老師的課程，即合理地平攤每個(gè)輪次的wlCell空間，把任課老師每個(gè)輪次所有班級(jí)的課程都安排在這個(gè)空間之中。把任課老師、課程、班級(jí)和排課輪次綁定在一起的數(shù)據(jù)稱為teacher-topic-class-classroom-turnNo數(shù)據(jù)，簡(jiǎn)稱ttcct。一個(gè)ttcct代表一節(jié)待安排的課。合理地分派ttcct的wlCell空間是實(shí)現(xiàn)同步教學(xué)的保證。圖3是為ttcct分派wlCell空間的一種方案，其中turnNo表示排課輪次，與ttcct相關(guān)的課程每周上3次課[5]。

圖3 分派ttcct的wlCell空間的一種方案Fig.3 An example of assigning wlCell to ttcct

如果wlCell被教師的其他活動(dòng)(“教務(wù)例會(huì)”“市集體備課”“校集體備課”等)占用，或者被班級(jí)的固定課(“班會(huì)”“體鍛”等)占用，或者處于限制排課的范圍之內(nèi)(例如，某些課不能排在上午的第1節(jié)，等等)，那么根據(jù)排課的資源約束條件，該wlCell是不可排課的。因此，ttcct的wlCell空間分為可排課和不可排課兩部分，可排課的wlCell數(shù)量與全體的wlCell數(shù)量的比值稱為排課容易度，記為ISRatio，它的取值范圍是0%～100%，值越大，越容易安排。如果ISRatio等于0，意味著ttcct沒(méi)有地方安排，排課失敗。ttcct是靜態(tài)數(shù)據(jù)，可以預(yù)先處理好，需要時(shí)查表獲取。

從軟件設(shè)計(jì)的角度，把排課的任務(wù)歸結(jié)為以下3個(gè)步驟：

1)構(gòu)造全校的每一節(jié)課對(duì)應(yīng)的ttcct；

2)按照保證教學(xué)進(jìn)程同步的要求，確定每個(gè)ttcct的可排課的wlCell空間；

3)利用A*算法，解決排課資源沖突，把ttcct安排到某個(gè)可以排課的wlCell中。

(2)狀態(tài)與擴(kuò)展。全校的ttcct可以分為已經(jīng)排入課程表和未排入課程表兩個(gè)部分。已經(jīng)排入課程表的記為ttcctwl，未安排入課程表中的還是記為ttcct。把它們分別放在名為tblData_ttcctwl和tblData_ttcct的兩個(gè)數(shù)據(jù)庫(kù)表中。因此，每一個(gè)狀態(tài)的數(shù)據(jù)同時(shí)存放在tblData_ttcctwl表和tblData_ttcct表中。初始狀態(tài)是，tblData_ttcctwl表中的記錄數(shù)為0，所有的ttcct都在tblData_ttcct表中；目標(biāo)狀態(tài)是，tblData_ttcct表中的記錄數(shù)為0，所有的ttcct都在tblData_ttcctwl表中。

自動(dòng)排課系統(tǒng)的基本動(dòng)作是，從tblData_ttcct表中提取一個(gè)ttcct，依次與ttcct的每一個(gè)可排課的wlCell結(jié)合成ttcctwl，并把它放入tblData_ttcctwl表中。實(shí)現(xiàn)這個(gè)過(guò)程的前提是必須滿足排課資源約束條件。所以，執(zhí)行基本動(dòng)作之前，必須根據(jù)具體情況，執(zhí)行以下3個(gè)輔助動(dòng)作：

·如果ttcct對(duì)應(yīng)的班級(jí)在wlCell已經(jīng)排課，那么，要預(yù)先將ttcctwl_c從tblData_ttcctwl表中刪除，將ttcctwl_c對(duì)應(yīng)的ttcct加入到tblData_ttcct表中；

·如果ttcct對(duì)應(yīng)的老師在wlCell已經(jīng)排課，那么，要預(yù)先將ttcctwl_t從tblData_ttcctwl表中刪除，將ttcctwl_t對(duì)應(yīng)的ttcct加入到tblData_ttcct表中；

·如果ttcct對(duì)應(yīng)的教室在wlCell已經(jīng)排課，那么，要預(yù)先將ttcctwl_cr從tblData_ttcctwl表中刪除，將ttcctwl_cr對(duì)應(yīng)的ttcct加入到tblData_ttcct中。

基本動(dòng)作導(dǎo)致tblData_ttcct表中的記錄數(shù)減1，輔助動(dòng)作導(dǎo)致tblData_ttcct表中的記錄數(shù)加1。但是輔助動(dòng)作的執(zhí)行是有條件的，所以一系列動(dòng)作執(zhí)行的結(jié)果可能導(dǎo)致tblData_ttcct表中的記錄數(shù)趨向0，從而達(dá)到目標(biāo)。

上述動(dòng)作將產(chǎn)生新的狀態(tài)，并且可能刪除某個(gè)祖先狀態(tài)的數(shù)據(jù)，因此，可以套用數(shù)據(jù)共享的程序模板進(jìn)行補(bǔ)償。要注意，因?yàn)闋顟B(tài)數(shù)據(jù)保存在兩個(gè)數(shù)據(jù)庫(kù)表中，所以要同時(shí)對(duì)這兩個(gè)數(shù)據(jù)庫(kù)表進(jìn)行補(bǔ)償。

(3)啟發(fā)函數(shù)和次級(jí)啟發(fā)函數(shù)。啟發(fā)函數(shù)f(n)=g(n)+h(n)。排課系統(tǒng)不關(guān)心過(guò)程，只關(guān)心最后結(jié)果，所以可以把啟發(fā)函數(shù)簡(jiǎn)化為f(n)=h(n)，把狀態(tài)n在tblData_ttcct表中的記錄的數(shù)量作為h(n)的值，因?yàn)樗軌蚝饬繝顟B(tài)n與目標(biāo)狀態(tài)之間的距離。應(yīng)該選取h(n)最小的狀態(tài)n進(jìn)行擴(kuò)展。但是，此時(shí)，tblData_ttcct表中還有h(n)條記錄，即還有h(n)個(gè)ttcct，還需要在它們之間選擇一個(gè)最優(yōu)的ttcct進(jìn)行擴(kuò)展。對(duì)于數(shù)據(jù)庫(kù)系統(tǒng)而言，需要進(jìn)行第二次選擇的環(huán)節(jié)具有普遍性，因此，引入次級(jí)啟發(fā)的概念，相應(yīng)地定義次級(jí)啟發(fā)函數(shù)：

f’(i) =h’(i)

i表示構(gòu)成狀態(tài)的數(shù)據(jù)集中的某個(gè)元素，h’(i)表示與這個(gè)元素有關(guān)的數(shù)據(jù)。

ttcct的ISRatio值越小，排課難度越大，越應(yīng)該優(yōu)先被安排，對(duì)安排全部的ttcct越有利。所以，把ISRatio作為h’(i)的值，在h(n)個(gè)的ttcct中，選擇h’(i)最小的ttcct，利用它進(jìn)行狀態(tài)擴(kuò)展。

(4)狀態(tài)特征值。狀態(tài)特征值是一個(gè)字符串，對(duì)它的要求是提取速度快，字符串短。排課系統(tǒng)的狀態(tài)特征值濃縮了某個(gè)狀態(tài)的全校課程表信息。狀態(tài)特征值應(yīng)該只包含課程表中最基本的信息，所以可以從班級(jí)課程表來(lái)提取狀態(tài)特征值。用字符串stateStr表示狀態(tài)特征值，從全校班級(jí)課程表中提取狀態(tài)特征值的偽代碼如下：

Begin

初始化stateStr為空；

按既定順序提取班級(jí)課程表，存放到list中；

For each班級(jí)課程表 in list Do

Begin

For ln=1 to 8 Do

Begin

For wd=1 to 5 Do

Begin

str=wlCell[ln,wd]課程名稱的第一個(gè)字符；

stateStr += str；

End；

End；

End；

End。

如果某個(gè)wlCell還沒(méi)有安排課程，那么課程名稱可以用空格或下劃線等代替。一般情況下，每個(gè)班級(jí)課程表中有40節(jié)課(每周5天，每天8節(jié))，如果所有的課程名稱的第一個(gè)漢字都不相同，可以只提取第一個(gè)漢字加入到狀態(tài)特征值的字符串中。以全校12個(gè)班級(jí)計(jì)，狀態(tài)特征值的字符串長(zhǎng)度是40*12*2=960。如果用一個(gè)英文字母來(lái)表示課程的名稱，狀態(tài)特征值的字符串長(zhǎng)度就會(huì)減半，為480個(gè)字符。

5.結(jié)論與后續(xù)工作

套用本文提供的這兩個(gè)程序模板開發(fā)的自動(dòng)排課軟件已經(jīng)在福州市第36中學(xué)使用。這是一所典型的初級(jí)中學(xué)，有3個(gè)年段，12個(gè)班級(jí)，每個(gè)班級(jí)每周40節(jié)課。設(shè)置好基本數(shù)據(jù)之后，自動(dòng)排課軟件能夠在8分鐘左右的時(shí)間內(nèi)自動(dòng)安排好整個(gè)學(xué)校的課程表，完全滿足學(xué)校的要求。后續(xù)的工作是研究如何選擇最好的狀態(tài)進(jìn)行重構(gòu)，以便更快地搜索到目標(biāo)。另外，狀態(tài)特征值的字符串長(zhǎng)度可能會(huì)很長(zhǎng)，超過(guò)數(shù)據(jù)庫(kù)系統(tǒng)中基本表的字符型字段的長(zhǎng)度限制，目前的做法是把狀態(tài)特征值拆分為若干個(gè)子字符串以適應(yīng)數(shù)據(jù)庫(kù)系統(tǒng)的要求，這會(huì)造成tblAStar的表結(jié)構(gòu)不統(tǒng)一，不利于應(yīng)用程序的通用性的要求。所以，有必要對(duì)狀態(tài)特征值進(jìn)行深入研究。

[1]NILSSON N J. 人工智能[M].北京：機(jī)械工業(yè)出版社， 2000 .

[2]VAN M D. A museum visitors guide with the A～*pathfinding algorithm[C].上海：2011 IEEE International Conference on Computer Science and Automation Engineering(CSAE 2011)，2001.

[3]張程，肖大薇，張盈謙.基于區(qū)域搜索的A*算法在游戲?qū)街械膽?yīng)用研究[J].電子設(shè)計(jì)工程，2014(13)：15-17.

[4]肖自兵，袁冬莉，屈耀紅.基于A～*定長(zhǎng)搜索算法的多無(wú)人機(jī)協(xié)同航跡規(guī)劃[J].飛行力學(xué)， 2012(01)：92-96.

[5]林峰.模板比對(duì)法實(shí)現(xiàn)中小學(xué)自動(dòng)排課[J].福建電腦，2008，24(12)：183-185.

(責(zé)任編輯：楊成平)

The Application of A*Algorithm Program Template for Database System

LIN Feng, ZHENG Ai-yuan

(Department of Information Management & Engineering,Fujian Commercial College, Fuzhou 350012, China)

Database system has been widely applied, dealing with many complex data processing in real life. A*algorithm also has many successful applications, but there is a lot of room for development in using database technology and A*algorithm to tackle practical problems. A*algorithm search space is large and often takes tens of minutes or even longer time to search for the solution. Therefore, a database system using A*algorithm is impractical because it requires considerable time to wait for executive results. Therefore, a set of program template which applies A*algorithm to database is proposed to solve above mentioned problems. An automatic course timetabling system based on program template is designed to solve a typical high school course scheduling problem. The results show that program template demonstrates practical value of proposed method.

A*algorithm; secondary heuristic function; database technology; automatic course timetabling

2017-01-22

2016年福建省中青年教師教育科研項(xiàng)目(科技類)“利用狀態(tài)空間的啟發(fā)式搜索法實(shí)現(xiàn)自動(dòng)排課系統(tǒng)”(JAT160578)。

林峰(1966-)，男，福建福州人，講師，碩士。研究方向：計(jì)算機(jī)軟件編程。

TP311.138

A

2096-3300(2017)01-0094-06