【正文】 意：一種是，如果上次的操作是某個面的順時針操作，這次操作如果是這個面的逆時針操作的話，就會回到魔方的初始狀態(tài)，以根結(jié)點(diǎn)為例，當(dāng)對根結(jié)點(diǎn)的某個面進(jìn)行一次順時針操作，再進(jìn)行一次逆時針操作，這個時候的魔方的狀態(tài)就是根結(jié)點(diǎn)的狀態(tài)，也就是說，在對這個結(jié)點(diǎn)進(jìn)行擴(kuò)展是毫無意義的。}} 以上就是這部分搜索實(shí)現(xiàn)的關(guān)鍵，搜索過程采用的是廣度優(yōu)先搜索，只要對以上的問題有了了解，搜索起來就不是很困難，但在搜索過程中涉及到搜索優(yōu)化的問題。break。break。break。break。break。break。break。break。break。break。break。break。while(()!=0){i=()?！=pparent。p=here?；謴?fù)當(dāng)前結(jié)點(diǎn)狀態(tài)，其中，v的數(shù)據(jù)分別用112這些數(shù)字表示，它代表魔方狀態(tài)圖的具體旋轉(zhuǎn)操作。每當(dāng)要擴(kuò)展當(dāng)前結(jié)點(diǎn)的時候，就通過parent指針將當(dāng)前結(jié)點(diǎn)的父結(jié)點(diǎn)的旋轉(zhuǎn)方式（也就是變量v中的數(shù)據(jù)）存儲到一個堆棧中去，然后在將彈出堆棧中的數(shù)據(jù)，然后采取相應(yīng)的旋轉(zhuǎn)操作（對魔方初始狀態(tài)圖的操作） [15]，這樣就可以很順利的找到當(dāng)前要擴(kuò)展的結(jié)點(diǎn)的正確的狀態(tài)圖。這里還有一個問題，就是parent指針的應(yīng)用，它并不是要找到正確求解路徑的指針，我在這里引用它主要是由于魔方狀態(tài)圖在搜索的過程中會用到大量的存儲空間，所以，為了節(jié)省空間，我在搜索的時候始終只用了一個數(shù)組（graphsta）。）指向鏈表中需要擴(kuò)展的結(jié)點(diǎn)，當(dāng)前的結(jié)點(diǎn)被擴(kuò)展，則here 指向當(dāng)前結(jié)點(diǎn)的 next所指向的結(jié)點(diǎn)。東北石油大學(xué)華瑞學(xué)院本科生畢業(yè)設(shè)計(jì)（論文）16下面談?wù)勅绾螛?gòu)造擴(kuò)展結(jié)點(diǎn)的鏈表，在A＊算法中用到了兩個表，一個是OPEN表，一個是CLOSED表，再一個是表示還沒有擴(kuò)展的結(jié)點(diǎn)集，一個是表示已經(jīng)被擴(kuò)展過的結(jié)點(diǎn)集。}。nodec *b_1。nodec *f_1。nodec *d_1。nodec *u_1。nodec *r_1。//用來指向擴(kuò)展結(jié)點(diǎn)//父結(jié)點(diǎn)的具體指向nodec *l_1。 //旋轉(zhuǎn)方式nodec *parent。東北石油大學(xué)華瑞學(xué)院本科生畢業(yè)設(shè)計(jì)（論文）15圖31　節(jié)點(diǎn)擴(kuò)展圖關(guān)于結(jié)點(diǎn)在程序中的實(shí)現(xiàn)是由下面的代碼定義的。所以，在每當(dāng)一個結(jié)點(diǎn)（這里的結(jié)點(diǎn)指的就是魔方狀態(tài)圖）要擴(kuò)展的時候，就要分別對同一結(jié)點(diǎn)采取12種不同的操作，然后，判斷是否找到需要的狀態(tài)。在搜索的問題中，我想先談?wù)勱P(guān)于結(jié)點(diǎn)的擴(kuò)展問題。(8)返回第3步。對已在CLOSED 中的M的每一個成員，重定向它在G中的每一個后繼，以使它們順著到目前為止發(fā)現(xiàn)的最好的路徑指向它們的祖先。把M 的這些成員加到OPEN 中。在G中安置M 的成員，使它們成為n1的后繼。(4)如果n1是目標(biāo)結(jié)點(diǎn)，順著G中，從n1到n的指針找到一條路徑，獲得解決方案，成功退出（該指針定義了一個搜索樹，在第七步建立）。(2)如果OPEN為空，則失敗退出。生成一個只包含開始接點(diǎn)n的搜索圖G，把n放在一個叫 OPEN的列表上。搜索方法采用的是A ＊ 算法。就像在概述中提到的那樣，在魔方求解的問題中盲目的搜索是起不到任何作用的，必須采用專家系統(tǒng)。這是程序設(shè)計(jì)中的一個難點(diǎn)，因?yàn)檫@里涉及到了搜索的方法和一些數(shù)據(jù)結(jié)構(gòu)的問題?！∷阉髂K搜索模塊()。這些和我給出的例子的操作是一樣的，這里就不多說。這一切上面的代碼都已經(jīng)寫的很清楚。這些就需要對魔方的平面狀態(tài)有一定的了解，只有這樣才能準(zhǔn)確的想象出魔方每一次旋轉(zhuǎn)后數(shù)組中的數(shù)據(jù)交換的過程。}相信看過以上的代碼后，會很容易理解這個模塊的功能和實(shí)現(xiàn)的方法。//23graphsta[4][5]=temporary1[0]。//34graphsta[5][4]=graphsta[4][5]。//41graphsta[4][3]=graphsta[5][4]。//12graphsta[3][4]=graphsta[4][3]。/*對邊塊操作*/temporary1[0]=graphsta[3][4]。 graphsta[6][5]=temporary0[1]。graphsta[6][3]=graphsta[5][6]。//34graphsta[5][3]=graphsta[5][5]。graphsta[2][3]=graphsta[5][2]。graphsta[2][5]=graphsta[3][2]。//12graphsta[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ù)是如何交換的，因?yàn)?，這部分與我前面給出的狀態(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 90 角塊5 邊塊6 角塊61 邊塊5 U（紅） 邊塊72 角塊1 邊塊2 角塊23 角塊5 邊塊5 角塊1 角塊1 邊塊2 角塊2 角塊2 邊塊7 角塊64 邊塊12 L（綠） 邊塊1 邊塊1 F（黃） 邊塊3 邊塊3 R（藍(lán)） 邊塊85 角塊8 邊塊11 角塊4 角塊4 邊塊4 角塊3 角塊3 邊塊9 角塊76 角塊4 邊塊4 角塊37 邊塊11 D（橙） 邊塊98 角塊8 邊塊10 角塊79 角塊5 邊塊6 角塊610 邊塊12 B（白） 邊塊811 角塊8 邊塊10 角塊7東北石油大學(xué)華瑞學(xué)院本科生畢業(yè)設(shè)計(jì)（論文）12　旋轉(zhuǎn)操作模塊旋轉(zhuǎn)操作模塊()。然后，開始電腦自動求解。當(dāng)用戶選擇了幫助操作的時候，則程序自動跳出接收用戶操作的循環(huán)，轉(zhuǎn)向執(zhí)行魔方的自動求解程序。如果，魔方還沒有被用戶解決，則在給出相應(yīng)操作的的顯示后，程序自動等待用戶的下一次輸入。在用戶輸入旋轉(zhuǎn)字符串，并且程序執(zhí)行相應(yīng)的操作后，的para()函數(shù)，來判斷魔方是否被用戶解出，如果解出則給出相應(yīng)的提示，并且返回到searchbegin()函數(shù)的調(diào)用處，也就是主函數(shù)中去。然后，()函數(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è)計(jì)（論文）10graphmf[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)圖，以方便對存儲這個問題的理解。這個模塊主要是為了實(shí)現(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í)際操作的數(shù)組char graphmf1[12][9]。//定義魔方矩陣,全局變量char graphmf[12][9]。東北石油大學(xué)華瑞學(xué)院本科生畢業(yè)設(shè)計(jì)（論文）8第 3 章　各個模塊的詳細(xì)設(shè)計(jì)　主模塊這個模塊比較簡單，就是程序的入口和一個簡單的操作選擇，和一些變量的定義，由于代碼不是很長，所以，給出的它的全部代碼，其它的在這里就不多說了。當(dāng)然，在這些函數(shù)功能的實(shí)現(xiàn)過程中，在上面談到的全局變量都會出現(xiàn)在各自的函數(shù)中，在這里就不過多的說明。值得一提的是，在firststage()()函數(shù)，對魔方的狀態(tài)圖進(jìn)行搜索，找到符合要求的狀態(tài)圖。然后調(diào)用自身的choice()函數(shù)，來接收用戶的選擇，同時，當(dāng)用戶選擇的是人工解決的時候，則在用戶每一次對魔方操作后，調(diào)用東北石油大學(xué)華瑞學(xué)院本科生畢業(yè)設(shè)計(jì)（論文）6（因?yàn)橹皇菍δХ綘顟B(tài)圖的操作，所以這里的函數(shù)會在后面說明）， 中的para()函數(shù)，由此來判斷魔方是圖 21　求解程序的流程否已經(jīng)被復(fù)原。函數(shù)，由這個函數(shù)開始真正的對輸入的魔方狀態(tài)進(jìn)行求解。()函數(shù)中可以找到它的具體應(yīng)用 [7]。在程序的執(zhí)行過程當(dāng)中，只要是對魔方合理的正確的操作就都存儲在這個隊(duì)列當(dāng)中，使魔方的正確解決過程得到保存。還有一個很重要的變量，就是對魔方正確的解決序列進(jìn)行存儲的變量。在程序執(zhí)行的初期，當(dāng)接受到魔方狀態(tài)文件的時候就將 graphmf 中的內(nèi)容復(fù)制到 graphsta和 graphmf1 中 [6]。同時，還有時刻保存魔方當(dāng)前狀態(tài)圖的數(shù)組，也就是在程序的執(zhí)行過程中實(shí)際操作的數(shù)組，這個數(shù)組為 graphsta[12][9]?！∪肿兞康亩x在程序的執(zhí)行過程中，有些比較重要的全局變量，在這里我簡單的談?wù)勥@些。當(dāng)然，各種玩法都不是健全的，有些極其復(fù)雜的情況光靠一種玩法的操作序列是不能求解的，這個我沒有考慮，因?yàn)椋谖夷壳八鶎?shí)驗(yàn)的魔方的各種狀態(tài)“八角法”都可以求解。這個文件就是本程序中提到的專家?guī)?，就是魔方具體玩法。在搜東北石油大學(xué)華瑞學(xué)院本科生畢業(yè)設(shè)計(jì)（論文）5索的過程中，會有一定的優(yōu)化。這是個難點(diǎn)，關(guān)于這些后面會有更詳細(xì)的介紹。其中， 文件的主要功能是實(shí)現(xiàn)搜索功能，也就是搜索我們想要得到的魔方狀態(tài)，這主要應(yīng)用在了魔方復(fù)原的第一階段。因?yàn)橹挥斜ＷC這部分的代碼準(zhǔn)確無誤，才能確保魔方順利的求解。其中， 文件的主要功能是實(shí)現(xiàn)當(dāng)對魔方各個面進(jìn)行操作后，魔方狀態(tài)圖的變化。其中， 文件的主要功能是在控制臺中打印出程序的操作界面，接受用戶的輸入，對合理的輸入給出相應(yīng)的操作，對不合理的操作給出相應(yīng)的提示。其中， 文件的主要功能是將從文件中接受到的魔方各個面的顏色狀態(tài)存放到魔方的狀態(tài)圖中，狀態(tài)圖變量的定義為全局變量。這樣的做法可能是不提倡的，但在這里我覺得是值得的。其中， 文件是程序的入口，它主要是對在程序中用到的各種變量進(jìn)行定義。為了增加程序的可讀性，同時，也為了使程序的編寫更加順利，將不同功能的代碼分別放在了不同的文件中編寫（.cpp 文件） 。專家 用戶知識采集子系統(tǒng) 用戶接口知識庫事實(shí)、啟發(fā)式知識工程師解釋子系統(tǒng)推理引擎東北石油大學(xué)華瑞學(xué)院本科生畢業(yè)設(shè)計(jì)（論文）4第 2 章　程序總規(guī)劃　程序的總體設(shè)計(jì)這里我考慮到程序應(yīng)該有一點(diǎn)游戲性，所以當(dāng)輸入一個魔方狀態(tài)時也可以試著人工來求解，當(dāng)然在任何時候都可以像電腦尋求幫助。關(guān)于輸入的這一點(diǎ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ì)算機(jī)程序的合理組合。　關(guān)于專家系統(tǒng)的簡介前面已經(jīng)談到用盲目搜索的方法對魔方問題求解是毫無辦法的，