毕业论文-魔方求解问题的设计与实现.doc

东北石油大学华瑞学院本科生毕业设计（论文） 魔魔方方求求解解问问题题的的设设计计与与实实现现 摘 要 本文介绍一个可以对魔方进行求解的程序。通过采用专家系统理论中的方法， 它可以快速地对输入的魔方状态文件求解。本程序是魔方求解与动画演示程序的 一部分。 程序的核心是一个专家的知识模块。这个模块是关于魔方的旋转序列的表示。 程序不断地将当前的魔方状态图与这个模块中的符合要求的状态图对比，如果符 合要求就调用相应的旋转序列，得到一个新的魔方的状态图。从而可以快速地找 到魔方的求解方法。 程序中用到了关于图搜索的 A 算法。这是一个关于图搜索和结点扩展的通用 的算法,但是这个算法并没有规定搜索树的扩展方式。在这里，搜索树的扩展方式 采用广度优先搜索，这样可以找到符合要求的状态图的最佳路径。在程序中,将广 度优先搜索与 A 算法相结合来对状态图进行搜索和结点的扩展，在搜索的过程中 用到了回朔操作。 有时候有些特殊的魔方状态图程序并不能给出求解的过程。但这种情况不是 很多，程序在大多数情况下可以顺利对魔方求解。这个问题主要是由采取的专家 序列的不同而引起的。好的专家序列可以减少这种情况的出现。 关键词：魔方；回朔；最佳路径 东北石油大学华瑞学院本科生毕业设计（论文） Abstract The thesis introduces a program for quickly resolving the Rubiks 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 common algorithm based on node expansion, but it does not define the actual expanding method of search trees. Here, the breadth-first search is used so that the best path may be found. The program integrates the breadth-first 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 东北石油大学华瑞学院本科生毕业设计（论文） I 目目 录录 第第 1 章章 概概述述.1 1.1 魔方问题简介.1 1.2 关于搜索与存储的问题1 1.3 关于专家系统的简介2 1.4 文件的输入2 1.5 本章小结3 第第 2 章章 程序总规划程序总规划4 2.1 程序的总体设计4 2.2 全局变量的定义5 2.3 各个模块间的调用关系5 2.4 本章小结7 第第 3 章章 各个模块的详细设计各个模块的详细设计.8 3.1 主模块8 3.2 文件接收模块9 3.3 程序执行模块10 3.4 旋转操作模块12 3.5 搜索模块14 3.6 专家系统模块18 3.7 本章小结20 第第 4 章章 程序演示程序演示21 结结 论论24 参参考考文文献献.25 致致 谢谢26 东北石油大学华瑞学院本科生毕业设计（论文） 1 第 1 章 概述 1.1 魔方问题简介 魔方（RUBIKS CUBE）是由匈牙利的厄尔诺鲁毕克在 1979 年设计的。他 是一个建筑学家，在布达佩斯执教。同时日本的石毛也独立完成了这个设计。两 人都取得专利。设计魔方的目的在于帮助人们更好的理解三维空间里的各种运动。 魔方是一个看似简单的玩具，它的每个面有九个格。我们目标是使每个面的 格子颜色都相同。每个格子实际上是小方块的一部分。小方块的每个面都可以旋 转，角方块有三个面，边方块有两个面。一共有八个角块，十二个边块和六个中 块。 目标是把一个每面都是随机颜色的魔方还原成每面颜色都相同的魔方。问题 是，有无数的方法操作魔方，然而只有极少的方法能够达到目的。使用盲目的搜 索算法是不行的，即使在最大型的计算机也要用上几年的时间。然而会玩的人在 几分钟内就可以将魔方复原，很显然这不是使用盲目搜索算法。解决魔方问题困 难之一就是当你想移动一个方块时，不得不移动其它七个方块（中间方块不动）。 在求解的早期，这不是大问题，但是当大部分方块都到达正确位置时，新的旋转 将会破坏已完成的部分。一些玩魔方的高手都知道许多复杂的旋转方法，这些方 法能够只改变少数方块的位置而不影响其它的方块。 而由程序来表示魔方求解的难点就在于，如何将这些复杂的旋转序列带到程 序中去，因为盲目的搜索不可能解决魔方问题。关于这些后面将有详细的介绍。 1.2 关于搜索与存储的问题 在魔方问题的解决过程当中离不开搜索，对魔方状态图的搜索。但魔方的状 态图很大，以致它们不能通过显示图来表示。正如魔方在求解过程中的状态图。 所以，这些只能用隐式状态空间图来解决，而解决这个问题的关键是如何用公式 来表示隐式状态空间图搜索的方法。 因为在魔方问题中状态图相当大，所以盲目搜索将不起作用。这时必须使用 优化算法指导搜索。使用不同的优化方法，搜索空间将极大的减少，从而达到在 有限时间内能够找到结果的程度。这个问题和其它人工智能问题一样，分为三个 东北石油大学华瑞学院本科生毕业设计（论文） 2 设计阶段。首先我们必须决定如何表示魔方的当前状态。然后还必须表示对魔方 的操作。最后必须解决如何把这些操作运用到魔方上。 在搜索中也会有一定的优化，由于状态图是按树型结构展开，所以，这里的 优化就是指“剪枝”操作。关于搜索的方法，采用的是 A 算法。在后面回有详 细介绍。 对于魔方状态图的存储，在本程序中采用了一个二维数组，在用二维数组存 储魔方状态图的时候，考虑到存储空间的问题，虽说，在本程序中只在魔方复原 的第一阶段用到了搜索，并且搜索的层数不是很多，但还是只用了一个状态图来 表示魔方的当前状态 1，这样，多少可以节省空间，但在求解时间上可能会长一 些，但不是很明显。关于这些在后面会有专门的介绍。 1.3 关于专家系统的简介 前面已经谈到用盲目搜索的方法对魔方问题求解是毫无办法的，因此，只能 将一些复杂的旋转序列嵌到程序中去，这样在魔方问题的求解过程当中就可以节 省大量的空间和时间，从而提高程序的效率。这种方法就是我所谈到的专家系统。 专家系统就是将某一个领域的知识进行合理的组织，与计算机程序的合理组 合。专家系统的应用很广，在医疗、工程和商业上都有广泛的应用。严格地讲， 任何具有专家功能的程序都被称为是一个专家系统。在解决问题中，通过运用知 识体达到专家级水平的 AI 程序叫做知识系统或专家系统。一个专家系统的主要 部分包括两个方面：知识库和推理引擎。在本程序中，由于是一个很简单的专家 系统，所以只包含了这两个最主要的方面，但一个完整的专家系统的结构应该是， 一个“知识工程师” （经常是一个训练过的 AI 计算机科学家）与应用领域的一个 专家（或几个专家）共同工作以便把专家的相关知识表示成一种形式，以使它能 被输入到知识库。这个过程经常由一个知识采集子系统协助 1。和其他情况一样， 这个子系统检查正在增长的知识库的可能不一致和不完备信息，然后将它们表示 给专家以做出决定。当然，由于本程序并没有涉及到专家系统中的各个方面，只 是知识在程序中的简单应用，所以对这些并不详细的讨论。一个专家系统的基本 结构图(图 1-1 专家系统的结构)。 1.4 文件的输入 对于魔方文件的输入，在这里简单的介绍一下。 输入时，依次输入上面、左面、前面、右面、下面和后面，各面的颜色状态， 在这里对颜色有严格的要求，当然，这种要求可能会对程序的灵活性有一定的影 东北石油大学华瑞学院本科生毕业设计（论文） 3 响，但我认为还是值得的。标准魔方的颜色，我把红色定为上面，绿色定为左面， 黄色定为前面，蓝色定为右面，橙色定为下面，白色定为后面。在这里要注意一 点，输入的时候最好是把各面都转到前面来进行输入，在这里只有后面是按照从 右到左，从上到下的顺序输入，其它各面当转到前面的时候都是按照从左到右， 从上到下的顺序输入。关于输入的这一点，主要是和我采取的存储方式有关，如 果这里不是说的很清楚的话，那么，在后面我将会给出我魔方存储的状态图，看 到这张图的时候，相信会对输入方式有更深的理解。 图 1-1 专家系统的结构 1.5 本章小结 通过本章能看出魔方在编写及实现中基本的概念和实现方法，先介绍了魔方 的玩法及原理，以及关于搜索与存储的问题的初步设想，对于专家系统运行模式 比较详细简介，也对文件输入方法进行笼统的介绍。 专家用户 知识采集子系统用户接口 知识库 事实、启发式 知识工程师 解释子系统 推理引擎 东北石油大学华瑞学院本科生毕业设计（论文） 4 第 2 章 程序总规划 2.1 程序的总体设计 这里我考虑到程序应该有一点游戏性，所以当输入一个魔方状态时也可以试 着人工来求解，当然在任何时候都可以像电脑寻求帮助。程序的编写，我更看重 的是它的算法，所以采用编写控制台应用程序，可能程序的界面不是很绚丽，但 算法的基本功能都能实现，我想这也就算达到了目的。 为了增加程序的可读性，同时，也为了使程序的编写更加顺利，将不同功能 的代码分别放在了不同的文件中编写（.cpp 文件）。按照代码功能的不同，将程 序分为六个不同的源文件 2。 其中，main.cpp 文件是程序的入口，它主要是对在程序中用到的各种变量进 行定义。在这里有一点需要说明一下，考虑到为了方便程序的编写，我将使用比 较频繁的变量定义为全局变量，这样在不同的源文件中，在各个需要它们的地方 可以很方便的引用它们。这样的做法可能是不提倡的，但在这里我觉得是值得的。 由于这样的变量不是很多，所以应该不会对程序的可读性造成多大的影响。 其中，gm.cpp 文件的主要功能是将从文件中接受到的魔方各个面的颜色状 态存放到魔方的状态图中，状态图变量的定义为全局变量。关于魔方状态图的实 现在后面将会有详细的介绍，在这里就不过多的涉及这个问题。 其中，begin.cpp 文件的主要功能是在控制台中打印出程序的操作界面，接受 用户的输入，对合理的输入给出相应的操作，对不合理的操作给出相应的提示。 并且，通过调用其它文件中的函数来对魔方进行求解 3，同时判断魔方是否被解 出。 其中，changemf.cpp 文件的主要功能是实现当对魔方各个面进行操作后，魔 方状态图的变化。可以说，这在程序的设计过程中是个比较费时，但又相当重要 的一个环节。因为只有保证这部分的代码准确无误，才能确保魔方顺利的求解。 其中，包含对魔方六个面的 12 种操作，每个面有两种操作。 其中，search.cpp 文件的主要功能是实现搜索功能，也就是搜索我们想要得 到的魔方状态，这主要应用在了魔方复原的第一阶段。这部分设计的难点是它的 数据结构，主要是考虑采用何种结构才能实现当前状态的扩展同时又要将不合要 求的状态存入扩展序列。这是个难点，关于这些后面会有更详细的介绍。搜索的 实现采用了 bfs 搜索 4，这样可以保证搜索到需要的状态图的路径是最短的。在搜 东北石油大学华瑞学院本科生毕业设计（论文） 5 索的过程中，会有一定的优化。 其中，expert.cpp 文件的主要功能是将各种魔方复杂的旋转操作序列合理的 组织在程序中，以便可以对魔方顺利求解。这个文件就是本程序中提到的专家库， 就是魔方具体玩法。关于魔方的玩法有很多，在本程序中我主要研究了所谓的 “八角法” ，这个文件中就汇集了在这种玩法下的旋转操作序列 5。当然，各种玩 法都不是健全的，有些极其复杂的情况光靠一种玩法的操作序列是不能求解的， 这个我没有考虑，因为，在我目前所实验的魔方的各种状态“八角法”都可以求 解。关于这些，这里不在多说（图 2-1 给出了程序执行的总体流程图） 。 2.2 全局变量的定义 在程序的执行过程中，有些比较重要的全局变量，在这里我简单的谈谈这些。 首先是接受魔方状态文件的数组，用到的是一个 129 的字符型二维数，这 个数组为 graphmf129。同时，还有时刻保存魔方当前状态图的数组，也就是 在程序的执行过程中实际操作的数组，这个数组为 graphsta129。还有一个记 录魔方初始状态的数组，这个数组为 graphmf1129，这个数组是为了在程序执 行时，开始选择的是由人工来解决魔方问题，但在后来选择了帮助，由电脑解决 时可以很方便的将魔方的初始状态传给魔方实际操作的数组 graphsta。在程序执 行的初期，当接受到魔方状态文件的时候就将 graphmf 中的内容复制到 graphsta 和 graphmf1 中 6。可能，这么做不是很容易叫人理解，因为，同一种状态却要两 个副本，但我这么做只是为了程序编写的方便。 还有一个很重要的变量，就是对魔方正确的解决序列进行存储的变量。这里 定义了一个队列rc。在程序的执行过程当中，只要是对魔方合理的正确的操作就 都存储在这个队列当中，使魔方的正确解决过程得到保存。 在魔方复原的第一阶段，为了很方便的将搜索 于专家系统联系到一起，用 到了一个指向函数的指针，定义的形式为void (*p)();。在expert.cpp中first-stage() 函数中可以找到它的具体应用 7。 2.3 各个模块间的调用关系 程序首先由main.cpp进入，调用begin.cpp中的search_begin();函数，由这个函 数开始真正的对输入的魔方状态进行求解。首先在这个函数中调用gm.cpp中的 getgraph()函数、makegraph()函数和search.cpp中change()函数，完成对魔方状态文 件的接受和两个副本的拷贝。然后调用自身的choice()函数，来接收用户的选择， 同时，当用户选择的是人工解决的时候，则在用户每一次对魔方操作后，调用 东北石油大学华瑞学院本科生毕业设计（论文） 6 change.cpp中的相应的魔方操作函数（因为只是对魔方状态图的操作，所以这里 的函数会在后面说明），然后调用search.cpp中的compara()函数，由此来判断魔方 是 图 2-1 求解程序的流程 否已经被复原。如果在choice()函数中选择的是由电脑来解决的话，则依次调用 东北石油大学华瑞学院本科生毕业设计（论文） 7 expert.cpp中的first_stage()、second_stage()、third_stage()、forth_stage()、 fifth_stage()、sixth_stage()、seventh_stage()、eighth_stage()，这几个函数来对魔方 进行求解，在这个几个函数的执行过程中，他们分别调用自身的含有解决特定魔 方状态下魔方的旋转序列，同时，也会对change.cpp中的魔方操作函数进行调用。 值得一提的是，在first-stage()函数中需要调用search.cpp中的bfs()函数，对魔方的 状态图进行搜索，找到符合要求的状态图。最后，调用搜索文件（search.cpp）中 的mission_compelet()函数 8，来判断魔方是否被解出，并且，给出求解的过程。 当然，在这些函数功能的实现过程中，在上面谈到的全局变量都会出现在各 自的函数中，在这里就不过多的说明。 2.4 本章小结 在本章中主要是对程序总体设计的游戏性、可读性在程序中怎样实现的进行 了详细的解说，在程序的执行过程中，全局变量是如何定义的，以及说明了各模 块间是如何相互调用它们之间的关系。 东北石油大学华瑞学院本科生毕业设计（论文） 8 第 3 章 各个模块的详细设计 3.1 主模块 这个模块比较简单，就是程序的入口和一个简单的操作选择，和一些变量的 定义，由于代码不是很长，所以，给出的它的全部代码，其它的在这里就不多说 了。 #include“All_Function.h“ #include #include #include #include using namespace std; /定义魔方矩阵,全局变量 char graphmf129;/接收文件的数组 char graphsta129;/实际操作的数组 char graphmf1129;/用来记录魔方初始状态的数组 queue rc;/存储魔方操作的步骤 bool solve_1=false; void (*p)();/函数指针,用在魔方复原第一阶段的bfs中 /*魔方文件的输入中有六行,对应六个面,必须按照R,G,Y,B,O,W面的顺序输入. */ void main() string c; while(1) search_begin(); /求解开始 coutc; if(c=“N“|c=“n“) break; 东北石油大学华瑞学院本科生毕业设计（论文） 9 3.2 文件接收模块 文件接收模块(gm.cpp)。这个模块主要是为了实现对魔方状态文件的接收， 和它的副本的创建。在这里我想先谈谈魔方的状态图，由于魔方有五十四小面， 六个“大面”，“大面”分别是指魔方的上、下、左、右、前、后，六个面。所 以，采用一个二维数组来存储这五十四个小面，但它的存储也要遵守一定结构， 在这节的最后我会给出它的存储状态图，以方便对存储这个问题的理解。 对于文件的接收也没什么太多的说法，就是有一点需要说明，这就是，在魔 方状态图文件中的每一行对应魔方的一个“大面”，而每一个“大面”又有九个 “小面”。主要是由以下的代码来完成这个功能。 char s620; char filename100; coutfilename; ifstream instuf(filename,ios:in); if(!instuf) cerr2就为将角块1中的颜色（也就是数组的数 据）送到角块2中去。对于边块的操作与角块一样，这里就不多说。 void front_1() char temporary03;/存储角块的临时变量 char temporary12;/存储边块的临时变量 /*对角块操作*/ temporary00=graphsta35;/存储2到临时变量 temporary01=graphsta36; temporary02=graphsta25; /1-2 graphsta35=graphsta33; 东北石油大学华瑞学院本科生毕业设计（论文） 13 graphsta36=graphsta23; graphsta25=graphsta32; /4-1 graphsta33=graphsta53; graphsta23=graphsta52; graphsta32=graphsta63; /3-4 graphsta53=graphsta55; graphsta52=graphsta65; graphsta63=graphsta56; /2-3 graphsta55=temporary00; graphsta65=temporary01; graphsta56=temporary02; /*对边块操作*/ temporary10=graphsta34; /存储2到临时变量 temporary11=graphsta24; /1-2 graphsta34=graphsta43; graphsta24=graphsta42; /4-1 graphsta43=graphsta54; graphsta42=graphsta64; /3-4 graphsta54=graphsta45; graphsta64=graphsta46; /2-3 graphsta45=temporary10; graphsta46=temporary11; 相信看过以上的代码后，会很容易理解这个模块的功能和实现的方法。由于， 其它函数的操作都与上面给出的例子大体相同，在这里就不过多的说明。这些就 需要对魔方的平面状态有一定的了解，只有这样才能准确的想象出魔方每一次旋 转后数组中的数据交换的过程。在交换的时候，为了保证数据不丢失，应该将一 个角块或边块的数据首先存储到一个变量中去，然后在对这个角块或边块中的数 据进行替换。这一切上面的代码都已经写的很清楚。 在这里我们还有两个函数并没有提到过，一个是left_front()，实现的操作是， left-front-right-back-left的各个面间的数据进行转换，而另外一个实现的操作是， front_down()，实现front-down-back-up-front的各个面间的数据转换 14。这些和我 给出的例子的操作是一样的，这里就不多说。这两个函数的定义主要是为了和专 东北石油大学华瑞学院本科生毕业设计（论文） 14 家系统的融合，因为在“八角法”中有这样的操作。 3.5 搜索模块 搜索模块(search.cpp)。这个模块在整个魔方求解的过程中是十分重要的一个 模块，主要是实现在魔方复原的第一阶段的搜索，对魔方状态图的搜索。这是程 序设计中的一个难点，因为这里涉及到了搜索的方法和一些数据结构的问题。 首先，谈谈搜索的问题。 就像在概述中提到的那样，在魔方求解的问题中盲目的搜索是起不到任何作 用的，必须采用专家系统。但在这里我先不讨论专家系统的问题，就想对搜索的 方法和如何优化搜索过程进行说明。 搜索方法采用的是A 算法。这是一个比较通用的图的搜索算法，下面给出它 具体的定义和实现方法。 生成一个只包含开始接点n的搜索图G，把n放在一个叫OPEN的列表上。 (1)生成一个列表CLOSED，它的初始值为空。 (2)如果OPEN为空，则失败退出。 (3)选择OPEN上的第一个结点，把它从OPEN中移入CLOSED，称该结点为 n1。 (4)如果n1是目标结点，顺着G中，从n1到n的指针找到一条路径，获得解决方 案，成功退出（该指针定义了一个搜索树，在第七步建立）。 (5)扩展结点n1，生成其后继结点集M，在G中，n1的祖先不能在M中。在G中 安置M的成员，使它们成为n1的后继。 (6)从M的每一个不在G中的成员建立一个指向n1的指针。把M的这些成员加 到OPEN中。对M的每一个已在OPEN中或CLOSED中的成员m，如果到目前为止 找到的到达m的最好路径通过n1，就把它的指针指向n1。对已在CLOSED中的M 的每一个成员，重定向它在G中的每一个后继，以使它们顺着到目前为止发现的 最好的路径指向它们的祖先。 (7)重排OPEN表。 (8)返回第3步。 在本程序中的搜索并没有严格的按照这个算法，但也是受到这个算法的启发。 在搜索的问题中，我想先谈谈关于结点的扩展问题。由于魔方有六个面，每 个面有两种操作，这在前面提过，一共是12种旋转方式。所以，在每当一个结点 （这里的结点指的就是魔方状态图）要扩展的时候，就要分别对同一结点采取12 种不同的操作，然后，判断是否找到需要的状态。下面给出它的扩展图，只是两 个结点的扩展，其它的由省略号表示。 东北石油大学华瑞学院本科生毕业设计（论文） 15 图3-1 节点扩展图 关于结点在程序中的实现是由下面的代码定义的。 struct nodec int v;/旋转方式 nodec *parent;/用来指向父结点 nodec *next;/用来指向扩展结点 /父结点的具体指向 nodec *l_1;nodec *l_2;nodec *r_1;nodec *r_2; nodec *u_1;nodec *u_2;nodec *d_1;nodec *d_2; nodec *f_1;nodec *f_2;nodec *b_1;nodec *b_2; ; 其中父结点的具体指向就是结点的12种扩展方式，这里你有可能注意到了有 几个变量在上面的扩展中没有提到，这些在后面都会有相应的说明，它们在搜索 的过程中也是十分重要的。 东北石油大学华瑞学院本科生毕业设计（论文） 16 下面谈谈如何构造扩展结点的链表，在A算法中用到了两个表，一个是 OPEN表，一个是CLOSED表，再一个是表示还没有扩展的结点集，一个是表示 已经被扩展过的结点集。在这里我只用了一个链表，然后用一个上面定义的结构 体类型的指针（nodec *here;）指向链表中需要扩展的结点，当前的结点被扩展， 则here指向当前结点的next所指向的结点。 至于什么样的结点需要加入到扩展链表中，在这里，每当当前结点被扩展的 时候，其中不符合要求的结点就都进入的扩展链表中去。 这里还有一个问题，就是parent指针的应用，它并不是要找到正确求解路径 的指针，我在这里引用它主要是由于魔方状态图在搜索的过程中会用到大量的存 储空间，所以，为了节省空间，我在搜索的时候始终只用了一个数组 （graphsta）。那么，如何实现用这一个数组就可以准确的找到当前要扩展结点 的正确状态图的呢？这就是parent指针的用处，在这里我采用了回朔的方法，一 个在程序设计中经常用到的方法。每当要扩展当前结点的时候，就通过parent指 针将当前结点的父结点的旋转方式（也就是变量v中的数据）存储到一个堆栈中 去，然后在将弹出堆栈中的数据，然后采取相应的旋转操作（对魔方初始状态图 的操作） 15，这样就可以很顺利的找到当前要扩展的结点的正确的状态图。 下面给出这部分的代码，其中，变量的定义为stack rb;恢复当前结点状 态，其中，v的数据分别用1-12这些数字表示，它代表魔方状态图的具体旋转操作。 /*找到当前要扩展的结点的旋转过程*/ void reback() nodec *p; p=here; while(p-v!=0) rb.push(p-v); p=p-parent; /*将扩展的旋转序列转换成具体的旋转操作,得到魔方当前的状态图*/ void node_operation() int i; while(rb.size()!=0) i=rb.top(); switch(i) 东北石油大学华瑞学院本科生毕业设计（论文） 17 case 1:front_1();break; case 2:front_2();break; case 3:back_1();break; case 4:back_2();break; case 5:left_1();break; case 6:left_2();break; case 7:right_1();break; case 8:right_2();break; case 9:up_1();break; case 10:up_2();break; case 11:down_1();break; case 12:down_2();break; rb.pop(); 以上就是这部分搜索实现的关键，搜索过程采用的是广度优先搜索，只要对 以上的问题有了了解，搜索起来就不是很困难，但在搜索过程中涉及到搜索优化 的问题。由于结点的扩展采用的是树型结构，所以，优化就是对搜索树的剪枝。 在魔方的操作中有这么两种情况值得注意：一种是，如果上次的操作是某个面的 顺时针操作，这次操作如果是这个面的逆时针操作的话，就会回到魔方的初始状 态，以根结点为例，当对根结点的某个面进行一次顺时针操作，再进行一次逆时 针操作，这个时候的魔方的状态就是根结点的状态，也就是说，在对这个结点进 行扩展是毫无意义的。这是在不断的重复根结点的扩展。也就是说，对同一个面 的两次相邻的操作不能是互逆的，也就是，不能对它进行顺时针（逆时针）操作 后，在进行逆时针（顺时针）操作。所以，在搜索树的扩展中，对这种操作应该 采取剪枝。另一种情况是，每当对同一个面进行四次相同的操作后（四次顺时针 或四次逆时针）也会回到最初的状态，如果对上面的剪枝有了了解，这个就不是 很难理解。所以，对这部分操作也要采取剪枝操作。 下面给出剪枝和和搜索的一部分代码，是对前面顺时针旋转操作扩展的代码， 其它面的进行搜索时扩展的代码和这些基本相同。其中，re_check来判断是否需 要剪枝。 /不扩展上次旋转的逆操作 if(re_check!=2) front_1(); (*p)(); if(solve_1=true) 东北石油大学华瑞学院本科生毕业设计（论文） 18 newnode=new nodec;/申请新结点 newnode-next=NULL; newnode-v=1;/旋转方式 newnode-parent=here; /指向父结点 here-f_1=newnode;/父结点前面顺时针指针指 向新结点 nextnode-next=newnode;/新结点插入队尾，构造 扩展链表 nextnode=newnode; break; else newnode=new nodec;/申请新结点 newnode-next=NULL; newnode-v=1;/旋转方式 newnode-parent=here;/指向父结点 here-f_1=newnode;/父结点前面顺时针指针指 向新结点 nextnode-next=newnode;/新结点插入队尾，构造 扩展链表 nextnode=newnode; front_2();/恢复到扩展前的状态 re.push(1);/剪枝序列 在这里还有一点要说明，虽说第二种剪枝按理说是应该执行的，但由于搜索 只是应用在了解决魔方问题的第一部分，并且，在这里搜索树的层数不会达到四 层，所以，在程序里我就没有对这种情况进行剪枝的操作。 到这里搜索部分就算是结束了，剩下的就是如何将它应用到解决到魔方复原 的第一段，关于这个会在谈论专家系统的时候给出。 3.6 专家系统模块 专家系统模块(expert.cpp)。这是程序中最为关键的一个模块，在这里将魔方 中复杂的旋转序列与程序结合到了一起，从而完成了对魔方的求解。这部分的程 东北石油大学华瑞学院本科生毕业设计（论文） 19 序并不是很难写，关键是知道如何解决魔方问题，也就是知道按照什么样的规律 来解决魔方问题。每当找到符合要求的状态时就调用专家序列给出正确的求解步 骤。这种方法很多，由于方法的不同，会影响到魔方求解时的步骤多少问题。我 在这里选择的是“八角法”，这种方法解决魔方问题在求解的步骤上并不是很好， 也就是步骤会比较多，选择它只是因为它学起来比较容易，因为我也是才接触魔 方，所以选择了一个比较容易学习的方法来处理这个问题。在这里有一点需要说 明，虽然求解的步骤比较多，但是在求解的速度上并没有什么太大的不同，一般 来说用不上一秒就可以求解。 下面就我所采用的专家方法“八角法”给以说明。由于，并不是魔方玩法 的教学，所以，我只是简单的介绍，重点是这个方法在程序中是如何表示出来的。 “八角法”，就是在解决魔方问题的时候，首先复原魔方的八个角块。然后 在复原其它的小块。“八角法”解决魔方问题一共分为八个阶段。在进行“八角 法”之前要恢复魔方的八个角块的位置，但颜色不对，这个过程是用另一种方法 完成的，因为在“八角法”中并没有给出这部分的是如何解决的。接下来介绍一 下“八角法”解决魔方问题的八个阶段。 第一阶段是在魔方的顶面构建出一个“X”，可以任意指定魔方的顶面，在 我的程序中我指定的这个阶段的顶面为白色。所谓“X”就是顶面的角块向上的 颜色与中块的颜色相同。 第二阶段是在魔方的底面构建出一个“X”，在第一阶段后，所有含底面颜 色的角块，应该都在底面，只可能色向不对。这个过程与上面的过程相似，只要 把底面转到顶面，然后把底面当做顶面来处理。 第三阶段是复原所有的角块，通过前两个阶段后魔方的顶面和底面的角块都 已经在自己的位置，而且向上面的颜色都已经符合要求，只剩下角块的边色没有 对上。而这个阶段就是要解决这个问题。在这里需要为成对的上角快和下角块分 别记数，如果每个侧面上两个上角块或两个下角块的颜色相同就为一对。然后根 据成对的情况来选择合适的魔方旋转序列。 第四阶段是在顶面恢复三个正确的边块。在这里边块的位置和色向都要考虑， 每次只考虑一块，直到这个阶段的完成。在这个阶段只恢复三个边块，当然，有 的时候很碰巧第四个边块也在正确的位置，这个先不用过多的考虑，在下面的阶 段会给这种情况的处理方法。 第五阶段是恢复底面的所有边块。在第四阶段有一个边块没有恢复，在这里 就要用到这个边块，把他当作“洞”，如果在上个阶段碰巧四个边块都恢复了， 那么在这里就以任意一个上边块当作“洞”。把这个“洞”转到前面，然后寻找 要到要恢复的下边块的位置套用具体的旋转序列。重复这阶段的操作，直到底面 的边块都复原。 第六阶段是恢复顶面的最后一个边块。当然，如果在第四阶段已经恢复的话 东北石油大学华瑞学院本科生毕业设计（论文） 20 在这里就不需要这个过程，直接进入第七阶段。在这里旋转魔方，把有“洞”的 顶面转到左面或者右面，然后选择合适的旋转序列，恢复这最后一个边块。 第七阶段是恢复魔方中间边块的过程。在上面几个阶段过后，魔方基本上已 经被复原了，只剩下魔方的中间块没有被复原。这没有什么难度，只需要找出没 有被复原的中间块的具体状态后，就可以套用固定的旋转序列来求解。当然，有 的时候由于情况比较特殊，没有符合的专家操作序列。不过只要通过旋转魔方就 可以找到符合要求的状态。 第八阶段是恢复魔方中间边块的色向。在这里和上面一样，魔方原来的顶面 和底面依然摆放到魔方的左右两面，然后找到符合要求的状态，套用专家操作序 列。 通过上面的八个阶段，魔方在大部分情况下就已经被复原了。因为有些极其 特殊的情况用这种方法没有办法求解，这个问题在前面已经谈过。通过上面对 “八角法”的叙述可以看出，这个部分没有什么多大的难度，只要把魔方状态考 虑完全就可以了。只是在魔方第一阶段前的八个角块的复原有些需要说明的。 在复原魔方八个角块的时候，用到了在上节提到的搜索技术。因为，复原八 个角块的专家序列也是在要恢复的角块在某些固定的位置的时候才能够起到作用。 但是在魔方的初始状态中，要恢复的角块不一定是符合要求的，这就需要旋转魔 方将要恢复的角块转到符合要求的位置。这个过程如果考虑各个可能的情况是很 难的，所以用到了搜索，这样可以很快的将要恢复的角块转到符合要求的位置， 从而很快的对魔方求解。 恢复八个角块的过程是由这个模块中的first-stage()函数实现的，因为在这里 在搜索的过程中要时刻对比搜索到的魔方状态是否符合那几种固定的要求，所以， 为了方便操作，用到了一个指向函数的指针(p)，关于它的定义在前面已给出说明， 这样是可以很方便的来调用对比函数（compara1()、compara2()、compara3()和 compara4()）。关于其它几个阶段的实现分别是由second-stage()、third-stage()、 forth-stage()、fifth-stage()、sixth-stage()、seven-stage()和eight-stage()来完成的 16。 由于在这个模块的各个函数中都是一些专家序列，程序无外就是将魔方的状 态与它们比较，如果符合要求就调用专家序列，不符合要求就通过旋转魔方，使 魔方的状态符合要求再调用专家序列。所以在这里不给出任何代码。 3.7 本章小结 通过以上可以看出主模块是建立在各个分模块相互调用的基础上，对文件接 收模块、程序执行模块、旋转操作模块、搜索模块以及专拣模块分别进行说明， 并给出基本求解过程和图解。 东北石油大学华瑞学院本科生毕业设计（论文） 21 第 4 章 程序演示 (1)程序开始运行后的显示。 图 4-1 程序启动后的界面 (2)输入魔方文件后的显示。 图 4-2 魔方的初始状态 (3)选择人工解决后的显示。 东北石油大学华瑞学院本科生毕业设计（论文） 22 图 4-3 人工操作界面 (4)在选择人工解决后输入f+后的显示。 图4-4 人工选择一个操作后的状态 (5)在输入“h”后的显示。 图 4-5 人工操作中间选择 h 后由电脑自动求解 (6)在程序一开始就输入电脑。 东北石油大学华瑞学院本科生毕业设计（论文） 23 图 4-6 在程序开始选择电脑自动求解 到这里已经把程序的执行过程简单地做了演示。 东北石油大学华瑞学院本科生毕业设计（论文） 24 结 论 这次毕业设计所选的题目对我来说是一个很大的挑战，因为在以前从来没有 写过任何与专家系统有关的程序。刚开使拿到这个题目的时候，没有考虑很多， 也没有想到这个问题会那么不容易解决。 在慢慢开始着手做这个程序的时候才发现有很多东西是我没有接触过的，这 些都需要通过自己来学习。在程序的编写过成中遇到了很多的困难，有些困难曾 让我有放弃的念头，因为在当时真的不知道如何来解决这些问题。所以本打算在 假期就将这个题目彻底解决的念头也随着这些困难消失了，而且无论怎么想也找 不到很好的解决办法。这些困难主要是在如何构建魔方的状态图，如何完成对魔 方各个面的旋转操作，如何在搜索中如何解决数据结构的问题等等。在假期快要 结束的时候，找到了构建魔方状态图的方法，也完成了对魔方各个面旋转操作的 函数的编写。在这个时候，我以为只要将搜索部分完成，这个题目就可以顺利的 解决，根本没有考虑到专家系统的问题。 在开学后，开始着手搜索部分程序的编写，当这部分程序编写完以后，新的 问题又出现了。这就是由于魔方状态图很大，而我采用的是盲目搜索，这样的话 在搜索树每增加一层的时候魔方的状态图会以几何数级增长，这需要大量的存储 空间，占用大量的内存。所以我改变的了对魔方状态图的存储方法，采用了不存 储状态数组，而是存储魔方的旋转方式的，再通过回朔来找到要扩展的状态图的 当前状态。但是这样也没有解决这个问题，并且我发现在我的机器上搜索树最多 也就能扩展到七层，当到七层的时候我的内存就被耗尽了。这也就说明我的程序 只能解决在七步之内找到复原路径的魔方，而且速度相当的慢。在那个时候这是 另我最头痛的问题。 在没有办法用盲目搜索解决这个问题的时候我考虑到了专家系统。于是找了 很多关于魔方的玩法的资料，在这些资料中只有“八角法”是最适合初学者的。 但是，新的问题又出现了，这个方法是在复原了八个角块以后才可以用的，但它 并没有给出如何恢复八个角块的序列。不过还好，在同学的帮助下找到了如何复 原八个角块的操作方法。在这个时候我认识到，如果想解决这个题目自己必须要 学习玩魔方，于是就照着我找到的资料开始学习如何玩魔方，还好在几天后终于 将魔方复原了。于是开始着手专家系统的编写，在一个礼拜左右后我将这个题目 基本上解决了，只是有些特殊的情况是无法解决的，在几次改进后有些特殊的情 况也的到了解决。现在的程序基本上可以解决大部分魔方状态。 东北石油大学华瑞学院本科生毕业设计（论文） 25 参考文献 1 N.J.Nilsson.人工智能M.北京:机械工业出版社,2000.3-6 2 B.Eckel.C编程思想（第二版）,第1卷:标准C引导M.北京:机械工业 出版社,2002.7-19 3 罗斌.Visual C+编程技巧精选500例M.北京:中国水利水电出版社,2005.1-22 4 B.Eckel.C编程思想,第2卷:实用编程技术M.北京:机械工业出版社, 2006.1-11 5 肖宏伟.Visual C+实效编程百例M.北京:人民邮电出版社,2004.8-3 6 Scott Meyers.Effective C+（第三版） （中文版）改善程序技术与设计思 维的55个有效做法M.电子工业出版社,2006.9-9 7 朱战立,张玉祥.C+面向对象程序设计M.人民邮电出版社,2006.4-20 8 许家珆,曾翎.软件工程理论与实践J.北京:高等教育出版社,2005.7-16 9 艾德才.C+程序设计简明教程M.中国水利水电出版社,2000.6-3 10 S M. Effective C+(英文版)M.北京:机械工业出版社,2006.4-7 11 朱福喜,朱三元,伍春香.人工智能基础教程M.北京:清华大学出社,2006.3-12 12 肖永亮.Visual C+游戏编程基础M.北京:电子工业出版社,2005.5-33 13 贲可荣,张彦铎.人工智能M.北京:清华大学出版社