【正文】 ，我在這里引用它主要是由于魔方狀態(tài)圖在搜索的過程中會用到大量的存儲空間，所以，為了節(jié)省空間，我 在搜索的時候始終只用了一個數(shù)組（ graphsta）。 東北石油大學(xué)華瑞學(xué)院本科生畢業(yè)設(shè)計（論文） 16 下面 談?wù)?如何構(gòu) 造擴展結(jié)點的鏈表，在 A＊算法中用到了兩個表，一個是 OPEN表 ， 一個是 CLOSED表， 再 一個是表示還沒有擴展的結(jié)點集，一個是表示已經(jīng)被擴展過的結(jié)點集。nodec *b_1。nodec *d_1。nodec *r_1。 //旋轉(zhuǎn)方式 nodec *parent。所以，在每當(dāng)一個結(jié)點（這里的結(jié)點指的就是魔方狀態(tài)圖）要擴展的時候，就要分別對同一結(jié)點采取 12種不同的操作，然后，判斷是否找到需要的狀態(tài)。 (8)返回第 3步 。把 M的這些成員加到OPEN中。 (4)如果 n1是目標結(jié)點，順著 G中，從 n1到 n的指針找到一條路徑，獲得解決方案，成功退出（該指針定義了一個搜索樹，在第七步建立）。 生成一個只包含開始接點 n的搜索圖 G，把 n放在一個叫 OPEN的列表上。 就像在概述中提到的那樣，在魔方求解的問題中盲目的搜索是起不到任何作用的，必須采用專家系統(tǒng)。 搜索模塊 搜索模塊 ()。這一切上面的代碼都已經(jīng)寫的很清楚。 } 相信看過以上的代碼后，會很容易理解這個模塊的功能和實現(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]。 //存儲 2到臨時變量 temporary0[1]=graphsta[3][6]。對于邊塊的操作與角塊一樣，這里就不多說。 下面我以 front_1()操作來簡單的說明一下數(shù)組間的數(shù)據(jù)是如何交換的，因為，這部分與我前面給出的狀態(tài)圖有十分密切的關(guān)系，所以，一定要理解前面的狀態(tài)圖的基礎(chǔ)上來解決這個問題。 這里數(shù)組間數(shù)據(jù)的變換關(guān)系都與前面給出的魔方狀態(tài)構(gòu)造圖有關(guān)，由于魔方有六個面，每個面都有兩種旋轉(zhuǎn)方式，順時針旋轉(zhuǎn)和逆時針旋轉(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（藍） 邊塊 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í)行魔方的自動求解程序。 在用戶輸入旋轉(zhuǎn)字符串，并且程序執(zhí)行相應(yīng)的操作后，程序調(diào)用 的 para()函數(shù)，來判斷魔方是否被用戶解出，如果解出則給出相應(yīng)的提示，并且返 回到 searchbegin()函數(shù)的調(diào)用處，也就是主函數(shù)中去。并且，會對錯誤的輸入給出相應(yīng)的提示。 程序執(zhí)行模塊 程序執(zhí)行模塊 ()。 到這里這個模塊的主要問題基本已經(jīng)解決了，當(dāng)然，由于完成的功能比較簡單，只是簡單 的給出了代碼，并簡單的說明。i12。i++) for(j=0。 當(dāng)魔方狀態(tài)文件被成功的接收以后，并且，被保存到魔方狀態(tài)圖數(shù)組中后，接下來就是將這個狀態(tài)拷貝到兩個副本中去，由于第一個副本的拷貝并沒有在這個模塊中出現(xiàn)，所以，先不給出這部分的代碼。 東北石油大學(xué)華瑞學(xué)院本科生畢業(yè)設(shè)計（論文） 10 graphmf[2][3]=s[0][6]。 graphmf[0][5]=s[0][2]。 其中 ， 唯一的不同就是數(shù)組的下標不同 [9]， 這主要由存儲魔方的狀態(tài)圖的 構(gòu)建 決定 ， 圖在最后給出 。 //魔方前面數(shù)據(jù) (s[3],20)。 abort()。 cinfilename。主要是由以下的代碼來完成這個功能。 這個模塊主要是為了實現(xiàn)對魔方狀態(tài)文 件的接收，和它的副本的創(chuàng)建。 //求解開始 coutN/n 退出 ,任意鍵執(zhí)行下一個魔方文件 endl。 //存儲魔方操作的步驟 bool solve_1=false。 //定義魔方矩陣 ,全局變量 char graphmf[12][9]。 當(dāng)然，在這些函數(shù)功能的實現(xiàn)過程中，在上面談到的全局變量都會出現(xiàn)在各自的函數(shù)中，在這里就不過多的說明。然后調(diào)用自身的 choice()函數(shù)，來接收用戶的選擇，同時，當(dāng)用戶選擇的是人工解決的時候，則在用戶每一次對魔方操作后，調(diào)用（因為只是對魔方狀態(tài)圖的操作，所以這里的函數(shù)會在后面說明），然后調(diào)用 para()函數(shù)，由此來判斷魔方是 東北石油大學(xué)華瑞學(xué)院本科生畢業(yè)設(shè)計（論文） 6 圖 21 求解程序的流程 否已經(jīng)被復(fù)原。在 firststage()函數(shù)中可以找到它的具體應(yīng)用 [7]。 還有一個很重要的變 量，就是對魔方正確的解決序列進行存儲的變量。同時，還有時刻保存魔方當(dāng)前狀態(tài)圖的數(shù)組，也就是在程序的執(zhí)行過程中實際操作的數(shù)組，這個數(shù)組為 graphsta[12][9]。當(dāng)然，各種玩法都不是健全的，有些極其復(fù)雜的情況光靠一種玩法的操作序列是不能求解的，這個我沒有考 慮，因為，在我目前所實驗的魔方的各種狀態(tài)“八角法”都可以求解。在搜索的過程中，會有一定的優(yōu)化。 其中， 文件的主要功能是實現(xiàn)搜索功能，也就是搜索我們想要得到的魔方狀態(tài)，這主要應(yīng)用在了魔方復(fù)原的第一階段。 其中， 文件的主要功能是實現(xiàn)當(dāng)對魔方各個面進行操作后，魔方狀態(tài)圖的變化。 其中， 文件的主要功能是將從文件中接受到的魔方各個面的顏色狀態(tài)存放到魔方的狀態(tài)圖中，狀態(tài)圖變量的定義為全局變量。 其中， 文件是程序的入口，它主要是對在程序中用到的各種變量進行定義。 專家 用戶 知識采集子系統(tǒng) 用戶接口 知識庫 事實、啟發(fā)式 知識工程師 解釋子系統(tǒng) 推理引擎 東北石油大學(xué)華瑞學(xué)院本科生畢業(yè)設(shè)計（論文） 4 第 2 章 程序總規(guī)劃 程序的總體設(shè)計 這里我考慮到程序應(yīng)該有一 點游戲性，所以當(dāng)輸入一個魔方狀態(tài)時也可以試著人工來求解，當(dāng)然 在任何時 候都可以像電腦尋求幫助。標準魔方的顏色，我把紅色定為上面，綠色定為左面，黃色定為前面，藍色定為右面，橙色定為下面，白色定為后面。當(dāng)然，由于本程序并沒 有涉及到專家系統(tǒng)中的各個方面，只是知識在程序中的簡單應(yīng)用，所以 對這些并不詳細的討論。一個專家系統(tǒng)的主要部分包括兩個方面： 知識庫和推理引擎。 專家系統(tǒng)就是將某一個領(lǐng)域的知 識進行合理的組織，與計算機程序的合理組合。 對于魔方狀態(tài)圖的存儲，在本程序中采用了一個二維數(shù)組，在用二維數(shù)組存儲魔方狀態(tài)圖的時候 ，考慮到存儲空間的問題，雖說，在本程序中只在魔方復(fù)原的第一階段用到了搜索，并且搜索的層數(shù)不是很多，但還是只用了一個狀態(tài)圖來表示魔方的當(dāng)前狀態(tài) [1]，這樣，多少可以節(jié)省空間，但在求解時間上可能會長一些，但不是很明顯。最后必須解決如何把這些操作運用到魔方上。使用不同的優(yōu)化方法，搜索空間將極大的減少，從而達到在有限時間內(nèi)能夠找到結(jié)果的程度。正如魔方在求解過程中的狀態(tài)圖。 而由程序來表示魔 方求解的難點就在于，如何將這些復(fù)雜的旋轉(zhuǎn)序列帶到程序中去，因為 盲目的搜索不可能解決魔方 問題。然而會玩的人在幾分鐘內(nèi)就可以將魔方復(fù)原，很顯然這不是使用盲目搜索算法。一共 有八個角塊，十二個邊塊和六個中塊。 魔方是一個看似簡單的玩具，它的每個面有九個格。他是一個建筑學(xué)家，在布達佩斯執(zhí)教。 backtracking。但這種情況不是很多，程序在大多數(shù)情況下可以順利對魔方求解。這是一個關(guān)于圖搜索和結(jié)點擴展的通用的算法 ,但是這個算法并沒有規(guī)定搜索 樹的擴展方式。這個模塊是關(guān)于魔方的旋轉(zhuǎn)序列的表示。東北石油大學(xué)華瑞學(xué)院本科生畢業(yè)設(shè)計（論文） 魔方求解問題的設(shè)計與實現(xiàn) 摘 要 本文介紹一個可以對魔方進行求解的程序。 程序的核心是一個專家的知識模塊。 程序中用到了關(guān)于圖搜索的 A＊ 算法。 有時候有些特殊的魔方狀態(tài)圖程序并不能給出求解的過程。 關(guān)鍵詞 ： 魔方；回朔；最佳路徑 東北石油大學(xué)華瑞學(xué)院本科生畢業(yè)設(shè)計（論文） 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è)計的。設(shè)計魔方的目的在于幫助人們更好的理解三維空間里的各種運動。小方塊的每個面都可以旋轉(zhuǎn)，角方塊有三個面，邊方塊有兩個面。使用盲目的搜索算法是不行的，即使在最大型的計算機也要用上幾年的時間。一些玩魔方的高手都知道許多復(fù)雜的旋轉(zhuǎn) 方法，這些方法能夠只改變少數(shù)方塊的位置而不影響其它的方塊。但魔方的狀態(tài)圖很大，以致它們不能通過顯示圖來表示。這時必須使用優(yōu)化算法指導(dǎo)搜索。然后還必須表示對魔方東北石油大學(xué)華瑞學(xué)院本科生畢業(yè)設(shè)計（論文） 2 的操作。在后面回有詳細介紹。這種方法 就是我所談到的專家系統(tǒng)。在解決問題中，通過運用知識體達到專家級水平的 AI 程序叫做知識系統(tǒng)或?qū)＜蚁到y(tǒng)。 和其他情況一樣，這個子系統(tǒng)檢查正在增長的知識庫的可能不一致和不完備信息，然后將它們表示給專家以做出決定。 輸入時，依次輸入上面、左面、前面、右面、下面和后面，各面的顏色狀態(tài)，在