【正文】 考慮到存儲空間的問題，雖說，在本程序中只在魔方復(fù)原的第一階段用到了搜索，并且搜索的層數(shù)不是很多，但還是只用了一個狀態(tài)圖來表示魔方的當(dāng)前狀態(tài) [1]，這樣，多少可以節(jié)省空間，但在求解時間上可能會長一些，但不是很明顯。關(guān)于這些在后面會有專門的介紹?！￡P(guān)于專家系統(tǒng)的簡介前面已經(jīng)談到用盲目搜索的方法對魔方問題求解是毫無辦法的，因此，只能將一些復(fù)雜的旋轉(zhuǎn)序列嵌到程序中去，這樣在魔方問題的求解過程當(dāng)中就可以節(jié)省大量的空間和時間，從而提高程序的效率。這種方法就是我所談到的專家系統(tǒng)。專家系統(tǒng)就是將某一個領(lǐng)域的知識進(jìn)行合理的組織，與計算機程序的合理組合。專家系統(tǒng)的應(yīng)用很廣，在醫(yī)療、工程和商業(yè)上都有廣泛的應(yīng)用。嚴(yán)格地講，任何具有專家功能的程序都被稱為是一個專家系統(tǒng)。在解決問題中，通過運用知識體達(dá)到專家級水平的 AI 程序叫做知識系統(tǒng)或?qū)＜蚁到y(tǒng)。一個專家系統(tǒng)的主要部分包括兩個方面：知識庫和推理引擎。在本程序中，由于是一個很簡單的專家系統(tǒng)，所以只包含了這兩個最主要的方面，但一個完整的專家系統(tǒng)的結(jié)構(gòu)應(yīng)該是，一個“知識工程師” （經(jīng)常是一個訓(xùn)練過的 AI 計算機科學(xué)家）與應(yīng)用領(lǐng)域的一個專家（或幾個專家）共同工作以便把專家的相關(guān)知識表示成一種形式，以使它能被輸入到知識庫。這個過程經(jīng)常由一個知識采集子系統(tǒng)協(xié)助 [1]。和其他情況一樣，這個子系統(tǒng)檢查正在增長的知識庫的可能不一致和不完備信息，然后將它們表示給專家以做出決定。當(dāng)然，由于本程序并沒有涉及到專家系統(tǒng)中的各個方面，只是知識在程序中的簡單應(yīng)用，所以對這些并不詳細(xì)的討論。一個專家系統(tǒng)的基本結(jié)構(gòu)圖(圖 11　專家系統(tǒng)的結(jié)構(gòu))?！∥募妮斎雽τ谀Х轿募妮斎?，在這里簡單的介紹一下。輸入時，依次輸入上面、左面、前面、右面、下面和后面，各面的顏色狀態(tài)，在這里對顏色有嚴(yán)格的要求，當(dāng)然，這種要求可能會對程序的靈活性有一定的影東北石油大學(xué)華瑞學(xué)院本科生畢業(yè)設(shè)計（論文）3響，但我認(rèn)為還是值得的。標(biāo)準(zhǔn)魔方的顏色，我把紅色定為上面，綠色定為左面，黃色定為前面，藍(lán)色定為右面，橙色定為下面，白色定為后面。在這里要注意一點，輸入的時候最好是把各面都轉(zhuǎn)到前面來進(jìn)行輸入，在這里只有后面是按照從右到左，從上到下的順序輸入，其它各面當(dāng)轉(zhuǎn)到前面的時候都是按照從左到右，從上到下的順序輸入。關(guān)于輸入的這一點，主要是和我采取的存儲方式有關(guān)，如果這里不是說的很清楚的話，那么，在后面我將會給出我魔方存儲的狀態(tài)圖，看到這張圖的時候，相信會對輸入方式有更深的理解。圖 11　專家系統(tǒng)的結(jié)構(gòu)　本章小結(jié)通過本章能看出魔方在編寫及實現(xiàn)中基本的概念和實現(xiàn)方法，先介紹了魔方的玩法及原理，以及關(guān)于搜索與存儲的問題的初步設(shè)想，對于專家系統(tǒng)運行模式比較詳細(xì)簡介，也對文件輸入方法進(jìn)行籠統(tǒng)的介紹。專家 用戶知識采集子系統(tǒng) 用戶接口知識庫事實、啟發(fā)式知識工程師解釋子系統(tǒng)推理引擎東北石油大學(xué)華瑞學(xué)院本科生畢業(yè)設(shè)計（論文）4第 2 章　程序總規(guī)劃　程序的總體設(shè)計這里我考慮到程序應(yīng)該有一點游戲性，所以當(dāng)輸入一個魔方狀態(tài)時也可以試著人工來求解，當(dāng)然在任何時候都可以像電腦尋求幫助。程序的編寫，我更看重的是它的算法，所以采用編寫控制臺應(yīng)用程序，可能程序的界面不是很絢麗，但算法的基本功能都能實現(xiàn)，我想這也就算達(dá)到了目的。為了增加程序的可讀性，同時，也為了使程序的編寫更加順利，將不同功能的代碼分別放在了不同的文件中編寫（.cpp 文件） 。按照代碼功能的不同，將程序分為六個不同的源文件 [2]。其中， 文件是程序的入口，它主要是對在程序中用到的各種變量進(jìn)行定義。在這里有一點需要說明一下，考慮到為了方便程序的編寫，我將使用比較頻繁的變量定義為全局變量，這樣在不同的源文件中，在各個需要它們的地方可以很方便的引用它們。這樣的做法可能是不提倡的，但在這里我覺得是值得的。由于這樣的變量不是很多，所以應(yīng)該不會對程序的可讀性造成多大的影響。其中， 文件的主要功能是將從文件中接受到的魔方各個面的顏色狀態(tài)存放到魔方的狀態(tài)圖中，狀態(tài)圖變量的定義為全局變量。關(guān)于魔方狀態(tài)圖的實現(xiàn)在后面將會有詳細(xì)的介紹，在這里就不過多的涉及這個問題。其中， 文件的主要功能是在控制臺中打印出程序的操作界面，接受用戶的輸入，對合理的輸入給出相應(yīng)的操作，對不合理的操作給出相應(yīng)的提示。并且，通過調(diào)用其它文件中的函數(shù)來對魔方進(jìn)行求解 [3]，同時判斷魔方是否被解出。其中， 文件的主要功能是實現(xiàn)當(dāng)對魔方各個面進(jìn)行操作后，魔方狀態(tài)圖的變化?？梢哉f，這在程序的設(shè)計過程中是個比較費時，但又相當(dāng)重要的一個環(huán)節(jié)。因為只有保證這部分的代碼準(zhǔn)確無誤，才能確保魔方順利的求解。其中，包含對魔方六個面的 12 種操作，每個面有兩種操作。其中， 文件的主要功能是實現(xiàn)搜索功能，也就是搜索我們想要得到的魔方狀態(tài)，這主要應(yīng)用在了魔方復(fù)原的第一階段。這部分設(shè)計的難點是它的數(shù)據(jù)結(jié)構(gòu)，主要是考慮采用何種結(jié)構(gòu)才能實現(xiàn)當(dāng)前狀態(tài)的擴(kuò)展同時又要將不合要求的狀態(tài)存入擴(kuò)展序列。這是個難點，關(guān)于這些后面會有更詳細(xì)的介紹。搜索的實現(xiàn)采用了 bfs 搜索 [4]，這樣可以保證搜索到需要的狀態(tài)圖的路徑是最短的。在搜東北石油大學(xué)華瑞學(xué)院本科生畢業(yè)設(shè)計（論文）5索的過程中，會有一定的優(yōu)化。其中， 文件的主要功能是將各種魔方復(fù)雜的旋轉(zhuǎn)操作序列合理的組織在程序中，以便可以對魔方順利求解。這個文件就是本程序中提到的專家?guī)?，就是魔方具體玩法。關(guān)于魔方的玩法有很多，在本程序中我主要研究了所謂的“八角法” ，這個文件中就匯集了在這種玩法下的旋轉(zhuǎn)操作序列 [5]。當(dāng)然，各種玩法都不是健全的，有些極其復(fù)雜的情況光靠一種玩法的操作序列是不能求解的，這個我沒有考慮，因為，在我目前所實驗的魔方的各種狀態(tài)“八角法”都可以求解。關(guān)于這些，這里不在多說（圖 21 給出了程序執(zhí)行的總體流程圖） ?！∪肿兞康亩x在程序的執(zhí)行過程中，有些比較重要的全局變量，在這里我簡單的談?wù)勥@些。首先是接受魔方狀態(tài)文件的數(shù)組，用到的是一個 129 的字符型二維數(shù)，這個數(shù)組為 graphmf[12][9]。同時，還有時刻保存魔方當(dāng)前狀態(tài)圖的數(shù)組，也就是在程序的執(zhí)行過程中實際操作的數(shù)組，這個數(shù)組為 graphsta[12][9]。還有一個記錄魔方初始狀態(tài)的數(shù)組，這個數(shù)組為 graphmf1[12][9]，這個數(shù)組是為了在程序執(zhí)行時，開始選擇的是由人工來解決魔方問題，但在后來選擇了幫助，由電腦解決時可以很方便的將魔方的初始狀態(tài)傳給魔方實際操作的數(shù)組 graphsta。在程序執(zhí)行的初期，當(dāng)接受到魔方狀態(tài)文件的時候就將 graphmf 中的內(nèi)容復(fù)制到 graphsta和 graphmf1 中 [6]。可能，這么做不是很容易叫人理解，因為，同一種狀態(tài)卻要兩個副本，但我這么做只是為了程序編寫的方便。還有一個很重要的變量，就是對魔方正確的解決序列進(jìn)行存儲的變量。這里定義了一個隊列rc。在程序的執(zhí)行過程當(dāng)中，只要是對魔方合理的正確的操作就都存儲在這個隊列當(dāng)中，使魔方的正確解決過程得到保存。在魔方復(fù)原的第一階段，為了很方便的將搜索 于專家系統(tǒng)聯(lián)系到一起，用到了一個指向函數(shù)的指針，定義的形式為void (*p)()。()函數(shù)中可以找到它的具體應(yīng)用 [7]?！「鱾€模塊間的調(diào)用關(guān)系，()。函數(shù)，由這個函數(shù)開始真正的對輸入的魔方狀態(tài)進(jìn)行求解。getgraph()函數(shù)、makegraph() 中change()函數(shù)，完成對魔方狀態(tài)文件的接受和兩個副本的拷貝。然后調(diào)用自身的choice()函數(shù)，來接收用戶的選擇，同時，當(dāng)用戶選擇的是人工解決的時候，則在用戶每一次對魔方操作后，調(diào)用東北石油大學(xué)華瑞學(xué)院本科生畢業(yè)設(shè)計（論文）6（因為只是對魔方狀態(tài)圖的操作，所以這里的函數(shù)會在后面說明）， 中的para()函數(shù)，由此來判斷魔方是圖 21　求解程序的流程否已經(jīng)被復(fù)原。如果在choice()函數(shù)中選擇的是由電腦來解決的話，則依次調(diào)用東北石油大學(xué)華瑞學(xué)院本科生畢業(yè)設(shè)計（論文）7()、second_stage()、third_stage()、forth_stage() 、fifth_stage()、sixth_stage()、seventh_stage()、eighth_stage()，這幾個函數(shù)來對魔方進(jìn)行求解，在這個幾個函數(shù)的執(zhí)行過程中，他們分別調(diào)用自身的含有解決特定魔方狀態(tài)下魔方的旋轉(zhuǎn)序列，同時。值得一提的是，在firststage()()函數(shù)，對魔方的狀態(tài)圖進(jìn)行搜索，找到符合要求的狀態(tài)圖。最后，調(diào)用搜索文件（）中的mission_pelet()函數(shù) [8]，來判斷魔方是否被解出，并且，給出求解的過程。當(dāng)然，在這些函數(shù)功能的實現(xiàn)過程中，在上面談到的全局變量都會出現(xiàn)在各自的函數(shù)中，在這里就不過多的說明?！”菊滦〗Y(jié)在本章中主要是對程序總體設(shè)計的游戲性、可讀性在程序中怎樣實現(xiàn)的進(jìn)行了詳細(xì)的解說，在程序的執(zhí)行過程中，全局變量是如何定義的，以及說明了各模塊間是如何相互調(diào)用它們之間的關(guān)系。東北石油大學(xué)華瑞學(xué)院本科生畢業(yè)設(shè)計（論文）8第 3 章　各個模塊的詳細(xì)設(shè)計　主模塊這個模塊比較簡單，就是程序的入口和一個簡單的操作選擇，和一些變量的定義，由于代碼不是很長，所以，給出的它的全部代碼，其它的在這里就不多說了。includeincludeiostreamincludequeueincludestackincludestringusing namespace std。//定義魔方矩陣,全局變量char graphmf[12][9]。//接收文件的數(shù)組char graphsta[12][9]。//實際操作的數(shù)組char graphmf1[12][9]。 //用來記錄魔方初始狀態(tài)的數(shù)組queueint rc。 //存儲魔方操作的步驟bool solve_1=false。void (*p)()。 //函數(shù)指針,用在魔方復(fù)原第一階段的bfs中/*魔方文件的輸入中有六行,對應(yīng)六個面,必須按照R,G,Y,B,O,W 面的順序輸入.*/void main(){string c。while(1){ search_begin()。 //求解開始 coutN/n 退出,任意鍵執(zhí)行下一個魔方文件endl。 cinc。 if(c==N||c==n) break。}}東北石油大學(xué)華瑞學(xué)院本科生畢業(yè)設(shè)計（論文）9　文件接收模塊文件接收模塊()。這個模塊主要是為了實現(xiàn)對魔方狀態(tài)文件的接收，和它的副本的創(chuàng)建。在這里我想先談?wù)勀Х降臓顟B(tài)圖，由于魔方有五十四小面，六個“大面”，“大面”分別是指魔方的上、下、左、右、前、后，六個面。所以，采用一個二維數(shù)組來存儲這五十四個小面，但它的存儲也要遵守一定結(jié)構(gòu)，在這節(jié)的最后我會給出它的存儲狀態(tài)圖，以方便對存儲這個問題的理解。對于文件的接收也沒什么太多的說法，就是有一點需要說明，這就是，在魔方狀態(tài)圖文件中的每一行對應(yīng)魔方的一個“大面”，而每一個“大面”又有九個“小面”。主要是由以下的代碼來完成這個功能。char s[6][20]。char filename[100]。cout請輸入魔方文件名:endl。 cinfilename。 ifstream instuf(filename,ios::in)。 if(!instuf) {cerrFile could not be open.endl。h=1。abort()。 } (s[0],20)。 //魔方上面數(shù)據(jù) (s[1],20)。 //魔方左面數(shù)據(jù) (s[2],20)。 //魔方前面數(shù)據(jù) (s[3],20)。 //魔方右面數(shù)據(jù) (s[4],20)。 //魔方下面數(shù)據(jù) (s[5],20)。 //魔方后面數(shù)據(jù)當(dāng)魔方文件成功接受后，就將接受數(shù)組中的狀態(tài)存放到保存魔方狀態(tài)圖的數(shù)組中去，由于這部分代碼很相似，所以，只給出一部分代碼。其中，唯一的不同就是數(shù)組的下標(biāo)不同 [9]，這主要由存儲魔方的狀態(tài)圖的構(gòu)建決定，圖在最后給出。由以下代碼完成這部分功能。graphmf[0][3]=s[0][0]。 //魔方上面狀態(tài)圖的構(gòu)建graphmf[0][4]=s[0][1]。graphmf[0][5]=s[0][2]。graphmf[1][3]=s[0][3]。graphmf[1][4]=s[0][4]。graphmf[1][5]=s[0][5]。東北石油大學(xué)華瑞學(xué)院本科生畢業(yè)設(shè)計（論文）10graphmf[2][3]=s[0][6]。graphmf[2][4]=s[0][7]。graphmf[2][5]=s[0][8]。以上這部分代碼就是將每一個“大面”中的狀態(tài)拷貝到九個數(shù)組元素中去，也就是對應(yīng)的九個“小面”。當(dāng)魔方狀態(tài)文件被成功的接收以后，并且，被保存到魔方狀態(tài)圖數(shù)組中后，接下來就是將這個狀態(tài)拷貝到兩個副本中去，由于第一個副本的拷貝并沒有在這個模塊中出現(xiàn)，所以，先不給出這部分的代碼。的change()函數(shù)中完成，代碼如下：void change() {int i,j。for(i=0。i12。i++) for(j=0。j9。j++) graphsta[i][j]=graphmf[i][j]。}下面是第二個副本對魔方上面狀態(tài)的拷貝：for(i=0。i12。i++)for(j=0。j9。j++) graphmf1[i][j]=graphmf[i][j]。 到這里這個模塊的主要問題基本已經(jīng)解決了，當(dāng)然，由于完成的功能比較簡單，只是簡單的給出了代碼，并簡單的說明。下面在給出魔方狀態(tài)的構(gòu)造圖