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