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