【正文】 因此，只能將一些復(fù)雜的旋轉(zhuǎn)序列嵌到程序中去，這樣在魔方問題的求解過程當中就可以節(jié)省大量的空間和時間，從而提高程序的效率。對于魔方狀態(tài)圖的存儲，在本程序中采用了一個二維數(shù)組，在用二維數(shù)組存儲魔方狀態(tài)圖的時候，考慮到存儲空間的問題，雖說，在本程序中只在魔方復(fù)原的第一階段用到了搜索，并且搜索的層數(shù)不是很多，但還是只用了一個狀態(tài)圖來表示魔方的當前狀態(tài) [1]，這樣，多少可以節(jié)省空間，但在求解時間上可能會長一些，但不是很明顯。關(guān)于搜索的方法，采用的是 A＊ 算法。最后必須解決如何把這些操作運用到魔方上。首先我們必須決定如何表示魔方的當前狀態(tài)。使用不同的優(yōu)化方法，搜索空間將極大的減少，從而達到在有限時間內(nèi)能夠找到結(jié)果的程度。因為在魔方問題中狀態(tài)圖相當大，所以盲目搜索將不起作用。正如魔方在求解過程中的狀態(tài)圖。　關(guān)于搜索與存儲的問題在魔方問題的解決過程當中離不開搜索，對魔方狀態(tài)圖的搜索。而由程序來表示魔方求解的難點就在于，如何將這些復(fù)雜的旋轉(zhuǎn)序列帶到程序中去，因為盲目的搜索不可能解決魔方問題。在求解的早期，這不是大問題，但是當大部分方塊都到達正確位置時，新的旋轉(zhuǎn)將會破壞已完成的部分。然而會玩的人在幾分鐘內(nèi)就可以將魔方復(fù)原，很顯然這不是使用盲目搜索算法。問題是，有無數(shù)的方法操作魔方，然而只有極少的方法能夠達到目的。一共有八個角塊，十二個邊塊和六個中塊。每個格子實際上是小方塊的一部分。魔方是一個看似簡單的玩具，它的每個面有九個格。兩人都取得專利。他是一個建筑學(xué)家，在布達佩斯執(zhí)教。S CUBE）是由匈牙利的厄爾諾 backtracking。好的專家序列可以減少這種情況的出現(xiàn)。但這種情況不是很多，程序在大多數(shù)情況下可以順利對魔方求解。在程序中,將廣度優(yōu)先搜索與 A＊ 算法相結(jié)合來對狀態(tài)圖進行搜索和結(jié)點的擴展，在搜索的過程中用到了回朔操作。這是一個關(guān)于圖搜索和結(jié)點擴展的通用的算法,但是這個算法并沒有規(guī)定搜索樹的擴展方式。從而可以快速地找到魔方的求解方法。這個模塊是關(guān)于魔方的旋轉(zhuǎn)序列的表示。本程序是魔方求解與動畫演示程序的一部分。東北石油大學(xué)華瑞學(xué)院本科生畢業(yè)設(shè)計（論文）魔 方 求 解 問 題 的 設(shè) 計 與 實 現(xiàn)摘 　 要本文介紹一個可以對魔方進行求解的程序。通過采用專家系統(tǒng)理論中的方法，它可以快速地對輸入的魔方狀態(tài)文件求解。程序的核心是一個專家的知識模塊。程序不斷地將當前的魔方狀態(tài)圖與這個模塊中的符合要求的狀態(tài)圖對比，如果符合要求就調(diào)用相應(yīng)的旋轉(zhuǎn)序列，得到一個新的魔方的狀態(tài)圖。程序中用到了關(guān)于圖搜索的 A＊ 算法。在這里，搜索樹的擴展方式采用廣度優(yōu)先搜索，這樣可以找到符合要求的狀態(tài)圖的最佳路徑。有時候有些特殊的魔方狀態(tài)圖程序并不能給出求解的過程。這個問題主要是由采取的專家序列的不同而引起的。關(guān)鍵詞：魔方；回朔；最佳路徑東北石油大學(xué)華瑞學(xué)院本科生畢業(yè)設(shè)計（論文）AbstractThe 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 knowledgeKey　words ：rubik cube。 best path東北石油大學(xué)華瑞學(xué)院本科生畢業(yè)設(shè)計（論文）I目　錄第 1 章 　 概 述 .........................................................................................................................................1 魔方問題簡介 .........................................................................................................1　 關(guān)于搜索與存儲的問題 ......................................................................................1　 關(guān)于專家系統(tǒng)的簡介 ..........................................................................................2　 文件的輸入 ..........................................................................................................2　 本章小結(jié) ..............................................................................................................3第 2 章　 程序總規(guī)劃 ............................................................................................................................4　 程序的總體設(shè)計 ..................................................................................................4　 全局變量的定義 ..................................................................................................5　 各個模塊間的調(diào)用關(guān)系 ......................................................................................5　 本章小結(jié) ..............................................................................................................7第 3 章　 各個模塊的詳細設(shè)計 .........................................................................................................8　 主模塊 ..................................................................................................................8　 文件接收模塊 ......................................................................................................9　 程序執(zhí)行模塊 ....................................................................................................10　 旋轉(zhuǎn)操作模塊 ....................................................................................................12　 搜索模塊 ............................................................................................................14　 專家系統(tǒng)模塊 ....................................................................................................18　 本章小結(jié) ............................................................................................................20第 4 章　 程序演示 ..............................................................................................................................21結(jié)　 論 ......................................................................................................................................................24參 考 文 獻 .................................................................................................................................................25致 　 謝 ......................................................................................................................................................26東北石油大學(xué)華瑞學(xué)院本科生畢業(yè)設(shè)計（論文）1第 1 章 　 概 述 魔方問題簡介魔方（RUBIK39。魯畢克在 1979 年設(shè)計的。同時日本的石毛也獨立完成了這個設(shè)計。設(shè)計魔方的目的在于幫助人們更好的理解三維空間里的各種運動。我們目標是使每個面的格子顏色都相同。小方塊的每個面都可以旋轉(zhuǎn)，角方塊有三個面，邊方塊有兩個面。目標是把一個每面都是隨機顏色的魔方還原成每面顏色都相同的魔方。使用盲目的搜索算法是不行的，即使在最大型的計算機也要用上幾年的時間。解決魔方問題困難之一就是當你想移動一個方塊時，不得不移動其它七個方塊（中間方塊不動）。一些玩魔方的高手都知道許多復(fù)雜的旋轉(zhuǎn)方法，這些方法能夠只改變少數(shù)方塊的位置而不影響其它的方塊。關(guān)于這些后面將有詳細的介紹。但魔方的狀態(tài)圖很大，以致它們不能通過顯示圖來表示。所以，這些只能用隱式狀態(tài)空間圖來解決，而解決這個問題