【正文】 的關(guān)鍵是如何用公式來表示隱式狀態(tài)空間圖搜索的方法。這時必須使用優(yōu)化算法指導(dǎo)搜索。這個問題和其它人工智能問題一樣，分為三個東北石油大學(xué)華瑞學(xué)院本科生畢業(yè)設(shè)計（論文）2設(shè)計階段。然后還必須表示對魔方的操作。在搜索中也會有一定的優(yōu)化，由于狀態(tài)圖是按樹型結(jié)構(gòu)展開，所以，這里的優(yōu)化就是指“剪枝”操作。在后面回有詳細(xì)介紹。關(guān)于這些在后面會有專門的介紹。這種方法就是我所談到的專家系統(tǒng)。專家系統(tǒng)的應(yīng)用很廣，在醫(yī)療、工程和商業(yè)上都有廣泛的應(yīng)用。在解決問題中，通過運用知識體達(dá)到專家級水平的 AI 程序叫做知識系統(tǒng)或?qū)＜蚁到y(tǒng)。在本程序中，由于是一個很簡單的專家系統(tǒng)，所以只包含了這兩個最主要的方面，但一個完整的專家系統(tǒng)的結(jié)構(gòu)應(yīng)該是，一個“知識工程師” （經(jīng)常是一個訓(xùn)練過的 AI 計算機(jī)科學(xué)家）與應(yīng)用領(lǐng)域的一個專家（或幾個專家）共同工作以便把專家的相關(guān)知識表示成一種形式，以使它能被輸入到知識庫。和其他情況一樣，這個子系統(tǒng)檢查正在增長的知識庫的可能不一致和不完備信息，然后將它們表示給專家以做出決定。一個專家系統(tǒng)的基本結(jié)構(gòu)圖(圖 11　專家系統(tǒng)的結(jié)構(gòu))。輸入時，依次輸入上面、左面、前面、右面、下面和后面，各面的顏色狀態(tài)，在這里對顏色有嚴(yán)格的要求，當(dāng)然，這種要求可能會對程序的靈活性有一定的影東北石油大學(xué)華瑞學(xué)院本科生畢業(yè)設(shè)計（論文）3響，但我認(rèn)為還是值得的。在這里要注意一點，輸入的時候最好是把各面都轉(zhuǎn)到前面來進(jìn)行輸入，在這里只有后面是按照從右到左，從上到下的順序輸入，其它各面當(dāng)轉(zhuǎn)到前面的時候都是按照從左到右，從上到下的順序輸入。圖 11　專家系統(tǒng)的結(jié)構(gòu)　本章小結(jié)通過本章能看出魔方在編寫及實現(xiàn)中基本的概念和實現(xiàn)方法，先介紹了魔方的玩法及原理，以及關(guān)于搜索與存儲的問題的初步設(shè)想，對于專家系統(tǒng)運行模式比較詳細(xì)簡介，也對文件輸入方法進(jìn)行籠統(tǒng)的介紹。程序的編寫，我更看重的是它的算法，所以采用編寫控制臺應(yīng)用程序，可能程序的界面不是很絢麗，但算法的基本功能都能實現(xiàn)，我想這也就算達(dá)到了目的。按照代碼功能的不同，將程序分為六個不同的源文件 [2]。在這里有一點需要說明一下，考慮到為了方便程序的編寫，我將使用比較頻繁的變量定義為全局變量，這樣在不同的源文件中，在各個需要它們的地方可以很方便的引用它們。由于這樣的變量不是很多，所以應(yīng)該不會對程序的可讀性造成多大的影響。關(guān)于魔方狀態(tài)圖的實現(xiàn)在后面將會有詳細(xì)的介紹，在這里就不過多的涉及這個問題。并且，通過調(diào)用其它文件中的函數(shù)來對魔方進(jìn)行求解 [3]，同時判斷魔方是否被解出?？梢哉f，這在程序的設(shè)計過程中是個比較費時，但又相當(dāng)重要的一個環(huán)節(jié)。其中，包含對魔方六個面的 12 種操作，每個面有兩種操作。這部分設(shè)計的難點是它的數(shù)據(jù)結(jié)構(gòu)，主要是考慮采用何種結(jié)構(gòu)才能實現(xiàn)當(dāng)前狀態(tài)的擴(kuò)展同時又要將不合要求的狀態(tài)存入擴(kuò)展序列。搜索的實現(xiàn)采用了 bfs 搜索 [4]，這樣可以保證搜索到需要的狀態(tài)圖的路徑是最短的。其中， 文件的主要功能是將各種魔方復(fù)雜的旋轉(zhuǎn)操作序列合理的組織在程序中，以便可以對魔方順利求解。關(guān)于魔方的玩法有很多，在本程序中我主要研究了所謂的“八角法” ，這個文件中就匯集了在這種玩法下的旋轉(zhuǎn)操作序列 [5]。關(guān)于這些，這里不在多說（圖 21 給出了程序執(zhí)行的總體流程圖） 。首先是接受魔方狀態(tài)文件的數(shù)組，用到的是一個 129 的字符型二維數(shù)，這個數(shù)組為 graphmf[12][9]。還有一個記錄魔方初始狀態(tài)的數(shù)組，這個數(shù)組為 graphmf1[12][9]，這個數(shù)組是為了在程序執(zhí)行時，開始選擇的是由人工來解決魔方問題，但在后來選擇了幫助，由電腦解決時可以很方便的將魔方的初始狀態(tài)傳給魔方實際操作的數(shù)組 graphsta。可能，這么做不是很容易叫人理解，因為，同一種狀態(tài)卻要兩個副本，但我這么做只是為了程序編寫的方便。這里定義了一個隊列rc。在魔方復(fù)原的第一階段，為了很方便的將搜索 于專家系統(tǒng)聯(lián)系到一起，用到了一個指向函數(shù)的指針，定義的形式為void (*p)()。　各個模塊間的調(diào)用關(guān)系，()。getgraph()函數(shù)、makegraph() 中change()函數(shù)，完成對魔方狀態(tài)文件的接受和兩個副本的拷貝。如果在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)序列，同時。最后，調(diào)用搜索文件（）中的mission_pelet()函數(shù) [8]，來判斷魔方是否被解出，并且，給出求解的過程?！”菊滦〗Y(jié)在本章中主要是對程序總體設(shè)計的游戲性、可讀性在程序中怎樣實現(xiàn)的進(jìn)行了詳細(xì)的解說，在程序的執(zhí)行過程中，全局變量是如何定義的，以及說明了各模塊間是如何相互調(diào)用它們之間的關(guān)系。includeincludeiostreamincludequeueincludestackincludestringusing namespace std。//接收文件的數(shù)組char graphsta[12][9]。 //用來記錄魔方初始狀態(tài)的數(shù)組queueint rc。void (*p)()。while(1){ search_begin()。 cinc。}}東北石油大學(xué)華瑞學(xué)院本科生畢業(yè)設(shè)計（論文）9　文件接收模塊文件接收模塊()。在這里我想先談?wù)勀Х降臓顟B(tài)圖，由于魔方有五十四小面，六個“大面”，“大面”分別是指魔方的上、下、左、右、前、后，六個面。對于文件的接收也沒什么太多的說法，就是有一點需要說明，這就是，在魔方狀態(tài)圖文件中的每一行對應(yīng)魔方的一個“大面”，而每一個“大面”又有九個“小面”。char s[6][20]。cout請輸入魔方文件名:endl。 ifstream instuf(filename,ios::in)。h=1。 } (s[0],20)。 //魔方左面數(shù)據(jù) (s[2],20)。 //魔方右面數(shù)據(jù) (s[4],20)。 //魔方后面數(shù)據(jù)當(dāng)魔方文件成功接受后，就將接受數(shù)組中的狀態(tài)存放到保存魔方狀態(tài)圖的數(shù)組中去，由于這部分代碼很相似，所以，只給出一部分代碼。由以下代碼完成這部分功能。 //魔方上面狀態(tài)圖的構(gòu)建graphmf[0][4]=s[0][1]。graphmf[1][3]=s[0][3]。graphmf[1][5]=s[0][5]。graphmf[2][4]=s[0][7]。以上這部分代碼就是將每一個“大面”中的狀態(tài)拷貝到九個數(shù)組元素中去，也就是對應(yīng)的九個“小面”。的change()函數(shù)中完成，代碼如下：void change() {int i,j。i12。j9。}下面是第二個副本對魔方上面狀態(tài)的拷貝：for(i=0。i++)for(j=0。j++) graphmf1[i][j]=graphmf[i][j]。下面在給出魔方狀態(tài)的構(gòu)造圖之前，先對圖中的標(biāo)記進(jìn)行簡單的說明，表格中的行號和列號分別代表數(shù)組中的行標(biāo)和列標(biāo)。以下就是魔方狀態(tài)的構(gòu)造圖（表 31　魔方狀態(tài)構(gòu)造圖），在程序中一個很重要的部分。這個模塊被設(shè)計成界面的打印和對用戶的輸入執(zhí)行相應(yīng)的操作，同時，它也是整個程序執(zhí)行的第一部分，其它的函數(shù)調(diào)用都是在它的search_begin()函數(shù)中來實現(xiàn)的 [10]。其它的操作方法東北石油大學(xué)華瑞學(xué)院本科生畢業(yè)設(shè)計（論文）11會在用戶選擇界面中有相應(yīng)的提示。每當(dāng)用戶選擇自己操作的時候，每輸入一次操作字符串，程序就會調(diào)用，例如：輸入[f+] ，則調(diào)用front_1()函數(shù)，這個函數(shù)主要是通過對魔方狀態(tài)圖中的各個面的顏色以及它在數(shù)組中的存儲位置的變換來達(dá)到動態(tài)表示魔方旋轉(zhuǎn)后的正確的狀態(tài)的目的。關(guān)于front_1()。然后，執(zhí)行主函數(shù)中其它的操作。直到魔方被解決，或者用戶在程序的執(zhí)行過程中選擇了幫助操作。在這里有一點需要說明，由于魔方的旋轉(zhuǎn)操作都是對graphsta[12][9]這個數(shù)組的操作，并且，在自動求解的過程中也要用到這個數(shù)組，但是，由于用戶一開始并沒有選擇自動求解，所以，數(shù)組中的狀態(tài)并不是魔方狀態(tài)圖的初始狀態(tài)，所以，需要將graphsta 這個數(shù)組在次轉(zhuǎn)換到魔方狀態(tài)圖的初始狀態(tài) [12]。這部分的功能也十分簡單，實現(xiàn)的過程也不是很復(fù)雜，只是對輸入的判斷和對其它函數(shù)的調(diào)用，這里不給出它的源代碼。這個模塊的設(shè)計可以說是程序中的一個比較重要的環(huán)節(jié)，因為，只有對魔方狀態(tài)圖操作的準(zhǔn)確才能保證求解的順利完成，下面對這不分加以詳細(xì)的說明?？梢哉f，這是個比較復(fù)雜的過程，因為，這個部分的實現(xiàn)沒有什么復(fù)雜的操作和特殊的結(jié)構(gòu)，只是數(shù)組內(nèi)部各個數(shù)據(jù)間的變換，需要的是細(xì)心和耐心。所以說，對魔方應(yīng)有12種操作方式，所以，在這里為每種操作都定義了一個相應(yīng)的函數(shù)，這個函數(shù)的功能就是完成在這種操作下，魔方狀態(tài)圖中顏色應(yīng)有的變換，以準(zhǔn)確的表現(xiàn)出當(dāng)前魔方的狀態(tài)。這十二個函數(shù)分別是：front_1()，前面順時針操作；front_2() ，前面逆時針操作；back_1() ，后面順時針操作；back_2() ，后面逆時針操作； up_1()，上面順時針操作；up_2()，上面逆時針操作；down_1()，下面順時針操作；down_2()，下面逆時針操作；left_1()，左面順時針操作；left_2() ，左面逆時針操作；right_1()，右面順時針操作；right_2()，右面逆時針操作 [13]。下面我給出這個函數(shù)執(zhí)行過程中狀態(tài)圖中數(shù)據(jù)交換的過程，也就是這個函數(shù)實現(xiàn)的源代碼，在代碼中我都標(biāo)上了注釋，對于這個問題的理解會很有幫助。例如：在對角塊的操作的過程中12就為將角塊1中的顏色（也就是數(shù)組的數(shù)據(jù)）送到角塊2中去。void front_1(){char temporary0[3]。 //存儲邊塊的臨時變量/*對角塊操作*/temporary0[0]=graphsta[3][5]。 temporary0[2]=graphsta[2][5]。東北石油大學(xué)華瑞學(xué)院本科生畢業(yè)設(shè)計（論文）13graphsta[3][6]=graphsta[2][3]。//41graphsta[3][3]=graphsta[5][3]。graphsta[3][2]=graphsta[6][3]。graphsta[5][2]=graphsta[6][5]。//23graphsta[5][5]=temporary0[0]。 graphsta[5][6]=temporary0[2]。 //存儲2到臨時變量temporary1[1]=graphsta[2][4]。graphsta[2][4]=graphsta[4][2]。graphsta[4][2]=graphsta[6][4]。graphsta[6][4]=graphsta[4][6]。 graphsta[4][6]=temporary1[1]。由于，其它函數(shù)的操作都與上面給出的例子大體相同，在這里就不過多的說明。在交換的時候，為了保證數(shù)據(jù)不丟失，應(yīng)該將一個角塊或邊塊的數(shù)據(jù)首先存儲到一個變量中去，然后在對這個角塊或邊塊中的數(shù)據(jù)進(jìn)行替換。在這里我們還有兩個函數(shù)并沒有提到過，一個是left_front()，實現(xiàn)的操作是，leftfrontrightbackleft的各個面間的數(shù)據(jù)進(jìn)行轉(zhuǎn)換，而另外一個實現(xiàn)的操作是，front_down()，實現(xiàn)frontdownbackupfront的各個面間的數(shù)據(jù)轉(zhuǎn)換 [14]。這兩個函數(shù)的定義主要是為了和專東北石油大學(xué)華瑞學(xué)院本科生畢業(yè)設(shè)計（論文）14家系統(tǒng)的融合，因為在“八角法”中有這樣的操作。這個模塊在整個魔方求解的過程中是十分重要的一個模塊，主要是實現(xiàn)在魔方復(fù)原的第一階段的搜索，對魔方狀態(tài)圖的搜索。首先，談?wù)勊阉鞯膯栴}。但在這里我先不討論專家系統(tǒng)的問題，就想對搜索的方法和如何優(yōu)化搜索過程進(jìn)行說明。這是一個比較通用的圖的搜索算法，下面給出它具體的定義和實現(xiàn)方法。(1)生成一個列表CLOSED ，它的初始值為空。(3)選擇OPEN上的第一個結(jié)點，把它從OPEN中移入CLOSED ，稱該結(jié)點為n1。(5)擴(kuò)展結(jié)點n1 ，生成其后繼結(jié)點集M，在G中，n1的祖先不能在M 中。(6)從M 的每一個不在G中的成員建立一個指向n1的指針。對M的每一個已在OPEN中或CLOSED中的成員m，如果到目前為止找到的到達(dá)m的最好路徑通過n1，就把它的指針指向 n1。(7)重排OPEN表。在本程序中的搜索并沒有嚴(yán)格的按照這個算法，但也是受到這個算法的啟發(fā)。由于魔方有六個面，每個面有兩種操作，這在前面提過，一共是12種旋轉(zhuǎn)方式。下面給出它的擴(kuò)展圖，只是兩個結(jié)點的擴(kuò)展，其它的由省略號表示。struct nodec{int v。 //用來指向父結(jié)點nodec *next。nodec *l_2。nodec *r_2。nodec *u_2。nodec *d_2。nodec *f_2。nodec *b_2。其中父結(jié)點的具體指向就是結(jié)點的12種擴(kuò)展方式，這里你有可能注意到了有幾個變量在上面的擴(kuò)展中沒有提到，這些在后面都會有相應(yīng)的說明，它們在搜索的過程中也是十分重要的。在這里我只用了一個鏈表，然后用一個上面定義的結(jié)構(gòu)體類型的指針（nod