【正文】 它們成為 n1的后繼。 (4)如果 n1是目標(biāo)結(jié)點，順著 G中，從 n1到 n的指針找到一條路徑，獲得解決方案，成功退出（該指針定義了一個搜索樹，在第七步建立）。 (2)如果 OPEN為空，則失敗退出。 生成一個只包含開始接點 n的搜索圖 G，把 n放在一個叫 OPEN的列表上。 搜索方法采用的 是 A＊ 算法。 就像在概述中提到的那樣，在魔方求解的問題中盲目的搜索是起不到任何作用的，必須采用專家系統(tǒng)。這是程序設(shè)計中的一個難點，因為這里涉及到了搜索的方法和一些數(shù)據(jù)結(jié)構(gòu)的問題。 搜索模塊 搜索模塊 ()。這些和我給出的例子的操作是一樣的，這里就不多說。這一切上面的代碼都已經(jīng)寫的很清楚。這些就需要對魔方的平面狀態(tài)有一定的了解，只有這樣才能準(zhǔn)確的想象出魔方每一次旋轉(zhuǎn)后數(shù)組中的數(shù)據(jù)交換的過程。 } 相信看過以上的代碼后，會很容易理解這個模塊的功能和實現(xiàn)的方法。 //23 graphsta[4][5]=temporary1[0]。 //34 graphsta[5][4]=graphsta[4][5]。 //41 graphsta[4][3]=graphsta[5][4]。 //12 graphsta[3][4]=graphsta[4][3]。 /*對邊塊操作 */ temporary1[0]=graphsta[3][4]。 graphsta[6][5]=temporary0[1]。 graphsta[6][3]=graphsta[5][6]。 //34 graphsta[5][3]=graphsta[5][5]。 graphsta[2][3]=graphsta[5][2]。 graphsta[2][5]=graphsta[3][2]。 //12 graphsta[3][5]=graphsta[3][3]。 //存儲 2到臨時變量 temporary0[1]=graphsta[3][6]。 //存儲角塊的臨時變量 char temporary1[2]。對于邊塊的操作與角塊一樣，這里就不多說。其中在注釋中的數(shù)字都為我在魔方狀態(tài)圖中標(biāo)出的那些數(shù)字。 下面我以 front_1()操作來簡單的說明一下數(shù)組間的數(shù)據(jù)是如何交換的，因為，這部分與我前面給出的狀態(tài)圖有十分密切的關(guān)系，所以，一定要理解前面的狀態(tài)圖的基礎(chǔ)上來解決這個問題。這里所有的操作都是對數(shù)組 graphsta的操作。 這里數(shù)組間數(shù)據(jù)的變換關(guān)系都與前面給出的魔方狀態(tài)構(gòu)造圖有關(guān)，由于魔方有六個面，每個面都有兩種旋轉(zhuǎn)方式，順時針旋轉(zhuǎn)和逆時針旋轉(zhuǎn)。 這個部分主要是為了響應(yīng)對魔方采取一定的旋轉(zhuǎn)操作后，魔方狀態(tài)圖中的顏色以及它們在數(shù)組中位置的變化。 表 31 魔方狀態(tài)構(gòu)造圖 0 1 2 3 4 5 6 7 9 0 角塊 5 邊塊 6 角塊 6 1 邊塊 5 U（紅） 邊塊 7 2 角塊 1 邊塊 2 角塊 2 3 角塊 5 邊塊 5 角塊 1 角塊 1 邊塊 2 角塊 2 角塊 2 邊塊 7 角 塊 6 4 邊塊 12 L（綠） 邊塊 1 邊塊 1 F（黃） 邊塊 3 邊塊 3 R（藍(lán)） 邊塊 8 5 角塊 8 邊塊 11 角塊 4 角塊 4 邊塊 4 角塊 3 角塊 3 邊塊 9 角塊 7 6 角塊 4 邊塊 4 角塊 3 7 邊塊 11 D（橙） 邊塊 9 8 角塊 8 邊塊 10 角塊 7 9 角塊 5 邊塊 6 角塊 6 10 邊塊 12 B（白） 邊塊 8 11 角塊 8 邊塊 10 角塊 7 東北石油大學(xué)華瑞學(xué)院本科生畢業(yè)設(shè)計（論文） 12 旋轉(zhuǎn)操作模塊 旋轉(zhuǎn)操作模塊 ()。然后，開始電腦自動求解。 當(dāng)用戶選擇了幫助操作的時候，則程序自動跳出接收用戶操作 的循環(huán)，轉(zhuǎn)向執(zhí)行魔方的自動求解程序。如果，魔方還沒有被用戶解決，則在給出相應(yīng)操作 的的顯示后，程序自動等待用戶的下一次輸入。 在用戶輸入旋轉(zhuǎn)字符串，并且程序執(zhí)行相應(yīng)的操作后，程序調(diào)用 的 para()函數(shù)，來判斷魔方是否被用戶解出，如果解出則給出相應(yīng)的提示，并且返 回到 searchbegin()函數(shù)的調(diào)用處，也就是主函數(shù)中去。然后，調(diào)用 display_mf()函數(shù)，來顯示旋轉(zhuǎn)后魔方的狀態(tài)圖 [11]。并且，會對錯誤的輸入給出相應(yīng)的提示。 在 search_begin()函數(shù)被主函數(shù)調(diào)用后，它首先調(diào)用自身的 choice()函數(shù)來打印出界面，同時等待接收用戶的輸入，當(dāng)用戶輸入為人工解決的時候，則給出魔方相應(yīng)旋轉(zhuǎn)的操作方法，例如：前面順時針操作對應(yīng)字符串 [f+]。 程序執(zhí)行模塊 程序執(zhí)行模塊 ()。 U 代表魔方上面， 為 紅色； L 代表魔方左面， 為 綠色； F 代表魔方前面， 為 黃色； R 代表魔方右面， 為 藍(lán)色 ； D 代表魔方下面， 為 橙色； B 代表魔方后面， 為 白色。 到這里這個模塊的主要問題基本已經(jīng)解決了，當(dāng)然，由于完成的功能比較簡單，只是簡單 的給出了代碼，并簡單的說明。j9。i12。j++) graphsta[i][j]=graphmf[i][j]。i++) for(j=0。 for(i=0。 當(dāng)魔方狀態(tài)文件被成功的接收以后，并且，被保存到魔方狀態(tài)圖數(shù)組中后，接下來就是將這個狀態(tài)拷貝到兩個副本中去，由于第一個副本的拷貝并沒有在這個模塊中出現(xiàn)，所以，先不給出這部分的代碼。 graphmf[2][5]=s[0][8]。 東北石油大學(xué)華瑞學(xué)院本科生畢業(yè)設(shè)計（論文） 10 graphmf[2][3]=s[0][6]。 graphmf[1][4]=s[0][4]。 graphmf[0][5]=s[0][2]。 graphmf[0][3]=s[0][0]。 其中 ， 唯一的不同就是數(shù)組的下標(biāo)不同 [9]， 這主要由存儲魔方的狀態(tài)圖的 構(gòu)建 決定 ， 圖在最后給出 。 //魔方下面數(shù)據(jù) (s[5],20)。 //魔方前面數(shù)據(jù) (s[3],20)。 //魔方上面數(shù)據(jù) (s[1],20)。 abort()。 if(!instuf) { cerrFile could not be open.endl。 cinfilename。 char filename[100]。主要是由以下的代碼來完成這個功能。所以，采用一個二維數(shù)組來存儲這五十四個小面，但它的存儲也要遵守一定結(jié)構(gòu)，在這節(jié)的最后我會給出它的存儲狀態(tài)圖，以方 便對存儲這個問題的理解。 這個模塊主要是為了實現(xiàn)對魔方狀態(tài)文 件的接收，和它的副本的創(chuàng)建。 if(c==N||c==n) break。 //求解開始 coutN/n 退出 ,任意鍵執(zhí)行下一個魔方文件 endl。 //函數(shù)指針 ,用在魔方復(fù)原第一階段的 bfs中 /*魔方文件的輸入中有六行 ,對應(yīng)六個面 ,必須按照 R,G,Y,B,O,W面的順序輸入 .*/ void main() { string c。 //存儲魔方操作的步驟 bool solve_1=false。 //實際操作的數(shù)組 char graphmf1[12][9]。 //定義魔方矩陣 ,全局變量 char graphmf[12][9]。 東北石油大學(xué)華瑞學(xué)院本科生畢業(yè)設(shè)計（論文） 8 第 3 章 各個模塊的詳細(xì)設(shè)計 主模塊 這個模塊比較簡單，就是程序的入口和一個簡單的操作選擇，和一些變量的定義，由于代碼不是很長，所以，給出的它的全部代碼，其它的在這里就不多說了。 當(dāng)然，在這些函數(shù)功能的實現(xiàn)過程中，在上面談到的全局變量都會出現(xiàn)在各自的函數(shù)中，在這里就不過多的說明。值得一提的是，在 firststage()函數(shù)中需要調(diào)用 bfs()函數(shù)，對魔方的狀態(tài)圖進(jìn)行搜索，找到符合要求的狀態(tài)圖。然后調(diào)用自身的 choice()函數(shù)，來接收用戶的選擇，同時，當(dāng)用戶選擇的是人工解決的時候，則在用戶每一次對魔方操作后，調(diào)用（因為只是對魔方狀態(tài)圖的操作，所以這里的函數(shù)會在后面說明），然后調(diào)用 para()函數(shù)，由此來判斷魔方是 東北石油大學(xué)華瑞學(xué)院本科生畢業(yè)設(shè)計（論文） 6 圖 21 求解程序的流程 否已經(jīng)被復(fù)原。函數(shù)，由這個函數(shù)開始真正的對輸入的魔方狀態(tài)進(jìn)行求解。在 firststage()函數(shù)中可以找到它的具體應(yīng)用 [7]。在程序的執(zhí)行過程當(dāng)中，只要是對魔方合 理的正確的操作就都存儲在這個隊列當(dāng)中，使魔方的正確解決過程得到保存。 還有一個很重要的變 量，就是對魔方正確的解決序列進(jìn)行存儲的變量。在程序執(zhí)行的初期，當(dāng)接受到魔方狀態(tài)文件的時候就將 graphmf 中的內(nèi)容復(fù)制到 graphsta 和graphmf1 中 [6]。同時，還有時刻保存魔方當(dāng)前狀態(tài)圖的數(shù)組，也就是在程序的執(zhí)行過程中實際操作的數(shù)組，這個數(shù)組為 graphsta[12][9]。 全局變量的定義 在程序的執(zhí)行過程中，有些比較重要的全局變量，在這里我簡單的談?wù)勥@些。當(dāng)然，各種玩法都不是健全的，有些極其復(fù)雜的情況光靠一種玩法的操作序列是不能求解的，這個我沒有考 慮，因為，在我目前所實驗的魔方的各種狀態(tài)“八角法”都可以求解。這個文件就是本程序中提到的專家?guī)?，就是魔方具體玩法。在搜索的過程中，會有一定的優(yōu)化。這是個難點，關(guān)于這些 后面會有更詳細(xì)的介紹。 其中， 文件的主要功能是實現(xiàn)搜索功能，也就是搜索我們想要得到的魔方狀態(tài)，這主要應(yīng)用在了魔方復(fù)原的第一階段。因為只有保證這部分的代碼準(zhǔn)確無誤，才能確保魔方順利的求解。 其中， 文件的主要功能是實現(xiàn)當(dāng)對魔方各個面進(jìn)行操作后，魔方狀態(tài)圖的變化。 其中， 文件的主要功能是在控制臺中打印出程序的操作界面，接受用戶的輸入，對合理的輸入給出相應(yīng)的操作，對不合理的操作給出相應(yīng)的提示。 其中， 文件的主要功能是將從文件中接受到的魔方各個面的顏色狀態(tài)存放到魔方的狀態(tài)圖中，狀態(tài)圖變量的定義為全局變量。這樣的做法可能是 不提倡的，但在這里我覺得是值得的。 其中， 文件是程序的入口，它主要是對在程序中用到的各種變量進(jìn)行定義。 為了增加程序的可讀性，同時，也為了使程序的編寫更加順利，將不同功能的代碼分別放在了不同的文件中編寫 （ .cpp 文件 ） 。 專家 用戶 知識采集子系統(tǒng) 用戶接口 知識庫 事實、啟發(fā)式 知識工程師 解釋子系統(tǒng) 推理引擎 東北石油大學(xué)華瑞學(xué)院本科生畢業(yè)設(shè)計（論文） 4 第 2 章 程序總規(guī)劃 程序的總體設(shè)計 這里我考慮到程序應(yīng)該有一 點游戲性，所以當(dāng)輸入一個魔方狀態(tài)時也可以試著人工來求解，當(dāng)然 在任何時 候都可以像電腦尋求幫助。關(guān)于輸入的這一點，主要是和我采取的存儲方式有關(guān)，如果這里不是說的很清楚的話，那么，在后面我將會給 出 我魔方存儲的狀態(tài)圖，看到這張圖的時候，相信會對輸入方式有更深的理解。標(biāo)準(zhǔn)魔方的顏色，我把紅色定為上面，綠色定為左面，黃色定為前面，藍(lán)色定為右面，橙色定為下面，白色定為后面。 文件的輸入 對于魔方文件的輸入，在這里簡單的介紹一下。當(dāng)然，由于本程序并沒 有涉及到專家系統(tǒng)中的各個方面，只是知識在程序中的簡單應(yīng)用，所以 對這些并不詳細(xì)的討論。這個過程經(jīng)常由一個知識采集子系統(tǒng)協(xié)助 [1]。一個專家系統(tǒng)的主要部分包括兩個方面： 知識庫和推理引擎。嚴(yán)格地講，任何具有專家功能的程序都被稱為是一個專家系統(tǒng)。 專家系統(tǒng)就是將某一個領(lǐng)域的知 識進(jìn)行合理的組織，與計算機(jī)程序的合理組合。 關(guān)于專家系統(tǒng)的簡介 前面已經(jīng)談到用盲目搜索的方法對魔方問題求解是毫無辦法的，因此，只能將一些復(fù)雜的旋轉(zhuǎn)序列嵌到程序中去，這樣在魔方問題的求解過 程當(dāng)中就可以節(jié)省大量的空間和時間，從而提高程序的效率。 對于魔方狀態(tài)圖的存儲，在本程序中采用了一個二維數(shù)組，在用二維數(shù)組存儲魔方狀態(tài)圖的時候 ，考慮到存儲空間的問題，雖說，在本程序中只在魔方復(fù)原的第一階段用到了搜索，并且搜索的層數(shù)不是很多，但還是只用了一個狀態(tài)圖來表示魔方的當(dāng)前狀態(tài) [1]，這樣，多少可以節(jié)省空間，但在求解時間上可能會長一些，但不是很明顯。關(guān)于搜索的方法，采用的是 A＊ 算法。最后必須解決如何把這些操作運用到魔方上。首先我們必須決定如何表示魔方的當(dāng)前狀態(tài)。使用不同的優(yōu)化方法，搜索空間將極大的減少，從而達(dá)到在有限時間內(nèi)能夠找到結(jié)果的程度。 因為在魔方問題中狀態(tài)圖相當(dāng)大，所以盲目搜索將 不起作用。正如魔方在求解過程中的狀態(tài)圖。 關(guān)于搜索與存儲的問題 在魔方問題的解決過程當(dāng)中離不開搜索，對魔方狀態(tài)圖的搜索。 而由程序來表示魔 方求解的難點就在于，如何將這些復(fù)雜的旋轉(zhuǎn)序列帶到程序中去，因為 盲目的搜索不可能解決魔方 問題。在求解的早期，這不是大問題，但是當(dāng)大部分方塊都到達(dá)正確位置時，新的旋轉(zhuǎn)將會破壞已完成的部分。然而會玩的人在幾分鐘內(nèi)就可以將魔方復(fù)原，很顯然這不是使用盲目搜索算法。問題是，有無數(shù)的方法操作魔方，然而只有極少的方法能夠達(dá)到目的。一共 有八個角塊，十二個邊塊和六個中塊。每個格子實際上是小方塊的一部分。 魔方是一個看似簡單的玩具，它的每個面有九個格。