【正文】 ，我在這里引用它主要是由于魔方狀態(tài)圖在搜索的過程中會(huì)用到大量的存儲(chǔ)空間，所以，為了節(jié)省空間，我 在搜索的時(shí)候始終只用了一個(gè)數(shù)組（ graphsta）。 東北石油大學(xué)華瑞學(xué)院本科生畢業(yè)設(shè)計(jì)（論文） 16 下面 談?wù)?如何構(gòu) 造擴(kuò)展結(jié)點(diǎn)的鏈表，在 A＊算法中用到了兩個(gè)表，一個(gè)是 OPEN表 ， 一個(gè)是 CLOSED表， 再 一個(gè)是表示還沒有擴(kuò)展的結(jié)點(diǎn)集，一個(gè)是表示已經(jīng)被擴(kuò)展過的結(jié)點(diǎn)集。nodec *b_1。nodec *d_1。nodec *r_1。 //旋轉(zhuǎn)方式 nodec *parent。所以，在每當(dāng)一個(gè)結(jié)點(diǎn)（這里的結(jié)點(diǎn)指的就是魔方狀態(tài)圖）要擴(kuò)展的時(shí)候，就要分別對(duì)同一結(jié)點(diǎn)采取 12種不同的操作，然后，判斷是否找到需要的狀態(tài)。 (8)返回第 3步 。把 M的這些成員加到OPEN中。 (4)如果 n1是目標(biāo)結(jié)點(diǎn)，順著 G中，從 n1到 n的指針找到一條路徑，獲得解決方案，成功退出（該指針定義了一個(gè)搜索樹，在第七步建立）。 生成一個(gè)只包含開始接點(diǎn) n的搜索圖 G，把 n放在一個(gè)叫 OPEN的列表上。 就像在概述中提到的那樣，在魔方求解的問題中盲目的搜索是起不到任何作用的，必須采用專家系統(tǒng)。 搜索模塊 搜索模塊 ()。這一切上面的代碼都已經(jīng)寫的很清楚。 } 相信看過以上的代碼后，會(huì)很容易理解這個(gè)模塊的功能和實(shí)現(xiàn)的方法。 //34 graphsta[5][4]=graphsta[4][5]。 //12 graphsta[3][4]=graphsta[4][3]。 graphsta[6][5]=temporary0[1]。 //34 graphsta[5][3]=graphsta[5][5]。 graphsta[2][5]=graphsta[3][2]。 //存儲(chǔ) 2到臨時(shí)變量 temporary0[1]=graphsta[3][6]。對(duì)于邊塊的操作與角塊一樣，這里就不多說。 下面我以 front_1()操作來簡(jiǎn)單的說明一下數(shù)組間的數(shù)據(jù)是如何交換的，因?yàn)椋@部分與我前面給出的狀態(tài)圖有十分密切的關(guān)系，所以，一定要理解前面的狀態(tài)圖的基礎(chǔ)上來解決這個(gè)問題。 這里數(shù)組間數(shù)據(jù)的變換關(guān)系都與前面給出的魔方狀態(tài)構(gòu)造圖有關(guān)，由于魔方有六個(gè)面，每個(gè)面都有兩種旋轉(zhuǎn)方式，順時(shí)針旋轉(zhuǎn)和逆時(shí)針旋轉(zhuǎn)。 表 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è)計(jì)（論文） 12 旋轉(zhuǎn)操作模塊 旋轉(zhuǎn)操作模塊 ()。 當(dāng)用戶選擇了幫助操作的時(shí)候，則程序自動(dòng)跳出接收用戶操作 的循環(huán)，轉(zhuǎn)向執(zhí)行魔方的自動(dòng)求解程序。 在用戶輸入旋轉(zhuǎn)字符串，并且程序執(zhí)行相應(yīng)的操作后，程序調(diào)用 的 para()函數(shù)，來判斷魔方是否被用戶解出，如果解出則給出相應(yīng)的提示，并且返 回到 searchbegin()函數(shù)的調(diào)用處，也就是主函數(shù)中去。并且，會(huì)對(duì)錯(cuò)誤的輸入給出相應(yīng)的提示。 程序執(zhí)行模塊 程序執(zhí)行模塊 ()。 到這里這個(gè)模塊的主要問題基本已經(jīng)解決了，當(dāng)然，由于完成的功能比較簡(jiǎn)單，只是簡(jiǎn)單 的給出了代碼，并簡(jiǎn)單的說明。i12。i++) for(j=0。 當(dāng)魔方狀態(tài)文件被成功的接收以后，并且，被保存到魔方狀態(tài)圖數(shù)組中后，接下來就是將這個(gè)狀態(tài)拷貝到兩個(gè)副本中去，由于第一個(gè)副本的拷貝并沒有在這個(gè)模塊中出現(xiàn)，所以，先不給出這部分的代碼。 東北石油大學(xué)華瑞學(xué)院本科生畢業(yè)設(shè)計(jì)（論文） 10 graphmf[2][3]=s[0][6]。 graphmf[0][5]=s[0][2]。 其中 ， 唯一的不同就是數(shù)組的下標(biāo)不同 [9]， 這主要由存儲(chǔ)魔方的狀態(tài)圖的 構(gòu)建 決定 ， 圖在最后給出 。 //魔方前面數(shù)據(jù) (s[3],20)。 abort()。 cinfilename。主要是由以下的代碼來完成這個(gè)功能。 這個(gè)模塊主要是為了實(shí)現(xiàn)對(duì)魔方狀態(tài)文 件的接收，和它的副本的創(chuàng)建。 //求解開始 coutN/n 退出 ,任意鍵執(zhí)行下一個(gè)魔方文件 endl。 //存儲(chǔ)魔方操作的步驟 bool solve_1=false。 //定義魔方矩陣 ,全局變量 char graphmf[12][9]。 當(dāng)然，在這些函數(shù)功能的實(shí)現(xiàn)過程中，在上面談到的全局變量都會(huì)出現(xiàn)在各自的函數(shù)中，在這里就不過多的說明。然后調(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ù)原。在 firststage()函數(shù)中可以找到它的具體應(yīng)用 [7]。 還有一個(gè)很重要的變 量，就是對(duì)魔方正確的解決序列進(jìn)行存儲(chǔ)的變量。同時(shí)，還有時(shí)刻保存魔方當(dāng)前狀態(tài)圖的數(shù)組，也就是在程序的執(zhí)行過程中實(shí)際操作的數(shù)組，這個(gè)數(shù)組為 graphsta[12][9]。當(dāng)然，各種玩法都不是健全的，有些極其復(fù)雜的情況光靠一種玩法的操作序列是不能求解的，這個(gè)我沒有考 慮，因?yàn)椋谖夷壳八鶎?shí)驗(yàn)的魔方的各種狀態(tài)“八角法”都可以求解。在搜索的過程中，會(huì)有一定的優(yōu)化。 其中， 文件的主要功能是實(shí)現(xiàn)搜索功能，也就是搜索我們想要得到的魔方狀態(tài)，這主要應(yīng)用在了魔方復(fù)原的第一階段。 其中， 文件的主要功能是實(shí)現(xiàn)當(dāng)對(duì)魔方各個(gè)面進(jìn)行操作后，魔方狀態(tài)圖的變化。 其中， 文件的主要功能是將從文件中接受到的魔方各個(gè)面的顏色狀態(tài)存放到魔方的狀態(tài)圖中，狀態(tài)圖變量的定義為全局變量。 其中， 文件是程序的入口，它主要是對(duì)在程序中用到的各種變量進(jìn)行定義。 專家 用戶 知識(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í) 候都可以像電腦尋求幫助。標(biāo)準(zhǔn)魔方的顏色，我把紅色定為上面，綠色定為左面，黃色定為前面，藍(lán)色定為右面，橙色定為下面，白色定為后面。當(dāng)然，由于本程序并沒 有涉及到專家系統(tǒng)中的各個(gè)方面，只是知識(shí)在程序中的簡(jiǎn)單應(yīng)用，所以 對(duì)這些并不詳細(xì)的討論。一個(gè)專家系統(tǒng)的主要部分包括兩個(gè)方面： 知識(shí)庫和推理引擎。 專家系統(tǒng)就是將某一個(gè)領(lǐng)域的知 識(shí)進(jìn)行合理的組織，與計(jì)算機(jī)程序的合理組合。 對(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ì)長(zhǎng)一些，但不是很明顯。最后必須解決如何把這些操作運(yùn)用到魔方上。使用不同的優(yōu)化方法，搜索空間將極大的減少，從而達(dá)到在有限時(shí)間內(nèi)能夠找到結(jié)果的程度。正如魔方在求解過程中的狀態(tài)圖。 而由程序來表示魔 方求解的難點(diǎn)就在于，如何將這些復(fù)雜的旋轉(zhuǎn)序列帶到程序中去，因?yàn)?盲目的搜索不可能解決魔方 問題。然而會(huì)玩的人在幾分鐘內(nèi)就可以將魔方復(fù)原，很顯然這不是使用盲目搜索算法。一共 有八個(gè)角塊，十二個(gè)邊塊和六個(gè)中塊。 魔方是一個(gè)看似簡(jiǎn)單的玩具，它的每個(gè)面有九個(gè)格。他是一個(gè)建筑學(xué)家，在布達(dá)佩斯執(zhí)教。 backtracking。但這種情況不是很多，程序在大多數(shù)情況下可以順利對(duì)魔方求解。這是一個(gè)關(guān)于圖搜索和結(jié)點(diǎn)擴(kuò)展的通用的算法 ,但是這個(gè)算法并沒有規(guī)定搜索 樹的擴(kuò)展方式。這個(gè)模塊是關(guān)于魔方的旋轉(zhuǎn)序列的表示。東北石油大學(xué)華瑞學(xué)院本科生畢業(yè)設(shè)計(jì)（論文） 魔方求解問題的設(shè)計(jì)與實(shí)現(xiàn) 摘 要 本文介紹一個(gè)可以對(duì)魔方進(jìn)行求解的程序。 程序的核心是一個(gè)專家的知識(shí)模塊。 程序中用到了關(guān)于圖搜索的 A＊ 算法。 有時(shí)候有些特殊的魔方狀態(tài)圖程序并不能給出求解的過程。 關(guān)鍵詞 ： 魔方；回朔；最佳路徑 東北石油大學(xué)華瑞學(xué)院本科生畢業(yè)設(shè)計(jì)（論文） Abstract The thesis introduces a program for quickly resolving the Rubik’s Cube problem. By exploiting the methods in the expert system theory, the program can give the rotation sequence for any inputted state to the destination state. The program is a part of the whole program for automatically solving the Rubik Cube and demonstrating it in animation. The core of the program is a module of expert knowledge, a representation of rotation sequences. The program repeatedly matches the current state with the states in the representation. If a math happens, the corresponding rotation operation will be called and a new state will be obtained, so that the destination state can be found at last within a short time. The program exploits the A* algorithm for graph searching. It is a mon algorithm based on node expansion, but it does not define the actual expanding method of search trees. Here, the breadthfirst search is used so that the best path may be found. The program integrates the breadthfirst search with the A* algorithm to traverse the state graph and conduct node expansion. In programming, backtracking is employed in the process of searching. Sometime the program cannot give the answer to some special inputted state. It is not because of the algorithm which the program using, but because of the limitation of the expert knowledge Key words： rubik cube。魯畢克在 1979 年設(shè)計(jì)的。設(shè)計(jì)魔方的目的在于幫助人們更好的理解三維空間里的各種運(yùn)動(dòng)。小方塊的每個(gè)面都可以旋轉(zhuǎn)，角方塊有三個(gè)面，邊方塊有兩個(gè)面。使用盲目的搜索算法是不行的，即使在最大型的計(jì)算機(jī)也要用上幾年的時(shí)間。一些玩魔方的高手都知道許多復(fù)雜的旋轉(zhuǎn) 方法，這些方法能夠只改變少數(shù)方塊的位置而不影響其它的方塊。但魔方的狀態(tài)圖很大，以致它們不能通過顯示圖來表示。這時(shí)必須使用優(yōu)化算法指導(dǎo)搜索。然后還必須表示對(duì)魔方東北石油大學(xué)華瑞學(xué)院本科生畢業(yè)設(shè)計(jì)（論文） 2 的操作。在后面回有詳細(xì)介紹。這種方法 就是我所談到的專家系統(tǒng)。在解決問題中，通過運(yùn)用知識(shí)體達(dá)到專家級(jí)水平的 AI 程序叫做知識(shí)系統(tǒng)或?qū)＜蚁到y(tǒng)。 和其他情況一樣，這個(gè)子系統(tǒng)檢查正在增長(zhǎng)的知識(shí)庫的可能不一致和不完備信息，然后將它們表示給專家以做出決定。 輸入時(shí)，依次輸入上面、左面、前面、右面、下面和后面，各面的顏色狀態(tài)，在