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

魔方求解问题的设计与实现摘要本文介绍一个可以对魔方进行求解的程序。通过采用专家系统理论中的方法，它可以快速地对输入的魔方状态文件求解。本程序是魔方求解与动画演示程序的一部分。程序的核心是一个专家的知识模块。这个模块是关于魔方的旋转序列的表示。程序不断地将当前的魔方状态图与这个模块中的符合要求的状态图对比，如果符合要求就调用相应的旋转序列，得到一个新的魔方的状态图。从而可以快速地找到魔方的求解方法。程序中用到了关于图搜索的A算法。这是一个关于图搜索和结点扩展的通用的算法,但是这个算法并没有规定搜索树的扩展方式。在这里，搜索树的扩展方式采用广度优先搜索，这样可以找到符合要求的状态图的最佳路径。在程序中,将广度优先搜索与A算法相结合来对状态图进行搜索和结点的扩展，在搜索的过程中用到了回朔操作。有时候有些特殊的魔方状态图程序并不能给出求解的过程。但这种情况不是很多，程序在大多数情况下可以顺利对魔方求解。这个问题主要是由采取的专家序列的不同而引起的。好的专家序列可以减少这种情况的出现。关键词魔方；回朔；最佳路径ABSTRACTTHETHESISINTRODUCESAPROGRAMFORQUICKLYRESOLVINGTHERUBIKSCUBEPROBLEMBYEXPLOITINGTHEMETHODSINTHEEXPERTSYSTEMTHEORY,THEPROGRAMCANGIVETHEROTATIONSEQUENCEFORANYINPUTTEDSTATETOTHEDESTINATIONSTATETHEPROGRAMISAPARTOFTHEWHOLEPROGRAMFORAUTOMATICALLYSOLVINGTHERUBIKCUBEANDDEMONSTRATINGITINANIMATIONTHECOREOFTHEPROGRAMISAMODULEOFEXPERTKNOWLEDGE,AREPRESENTATIONOFROTATIONSEQUENCESTHEPROGRAMREPEATEDLYMATCHESTHECURRENTSTATEWITHTHESTATESINTHEREPRESENTATIONIFAMATHHAPPENS,THECORRESPONDINGROTATIONOPERATIONWILLBECALLEDANDANEWSTATEWILLBEOBTAINED,SOTHATTHEDESTINATIONSTATECANBEFOUNDATLASTWITHINASHORTTIMETHEPROGRAMEXPLOITSTHEAALGORITHMFORGRAPHSEARCHINGITISACOMMONALGORITHMBASEDONNODEEXPANSION,BUTITDOESNOTDEFINETHEACTUALEXPANDINGMETHODOFSEARCHTREESHERE,THEBREADTHFIRSTSEARCHISUSEDSOTHATTHEBESTPATHMAYBEFOUNDTHEPROGRAMINTEGRATESTHEBREADTHFIRSTSEARCHWITHTHEAALGORITHMTOTRAVERSETHESTATEGRAPHANDCONDUCTNODEEXPANSIONINPROGRAMMING,BACKTRACKINGISEMPLOYEDINTHEPROCESSOFSEARCHINGSOMETIMETHEPROGRAMCANNOTGIVETHEANSWERTOSOMESPECIALINPUTTEDSTATEITISNOTBECAUSEOFTHEALGORITHMWHICHTHEPROGRAMUSING,BUTBECAUSEOFTHELIMITATIONOFTHEEXPERTKNOWLEDGEKEYWORDSRUBIKCUBEBACKTRACKINGBESTPATH目录第1章概述111魔方问题简介112关于搜索与存储的问题113关于专家系统的简介214文件的输入215本章小结3第2章程序总规划421程序的总体设计422全局变量的定义523各个模块间的调用关系524本章小结7第3章各个模块的详细设计831主模块832文件接收模块933程序执行模块1034旋转操作模块1235搜索模块1436专家系统模块1837本章小结20第4章程序演示21结论24参考文献25致谢26第1章概述11魔方问题简介魔方（RUBIKSCUBE）是由匈牙利的厄尔诺鲁毕克在1979年设计的。他是一个建筑学家，在布达佩斯执教。同时日本的石毛也独立完成了这个设计。两人都取得专利。设计魔方的目的在于帮助人们更好的理解三维空间里的各种运动。魔方是一个看似简单的玩具，它的每个面有九个格。我们目标是使每个面的格子颜色都相同。每个格子实际上是小方块的一部分。小方块的每个面都可以旋转，角方块有三个面，边方块有两个面。一共有八个角块，十二个边块和六个中块。目标是把一个每面都是随机颜色的魔方还原成每面颜色都相同的魔方。问题是，有无数的方法操作魔方，然而只有极少的方法能够达到目的。使用盲目的搜索算法是不行的，即使在最大型的计算机也要用上几年的时间。然而会玩的人在几分钟内就可以将魔方复原，很显然这不是使用盲目搜索算法。解决魔方问题困难之一就是当你想移动一个方块时，不得不移动其它七个方块（中间方块不动）。在求解的早期，这不是大问题，但是当大部分方块都到达正确位置时，新的旋转将会破坏已完成的部分。一些玩魔方的高手都知道许多复杂的旋转方法，这些方法能够只改变少数方块的位置而不影响其它的方块。而由程序来表示魔方求解的难点就在于，如何将这些复杂的旋转序列带到程序中去，因为盲目的搜索不可能解决魔方问题。关于这些后面将有详细的介绍。12关于搜索与存储的问题在魔方问题的解决过程当中离不开搜索，对魔方状态图的搜索。但魔方的状态图很大，以致它们不能通过显示图来表示。正如魔方在求解过程中的状态图。所以，这些只能用隐式状态空间图来解决，而解决这个问题的关键是如何用公式来表示隐式状态空间图搜索的方法。因为在魔方问题中状态图相当大，所以盲目搜索将不起作用。这时必须使用优化算法指导搜索。使用不同的优化方法，搜索空间将极大的减少，从而达到在有限时间内能够找到结果的程度。这个问题和其它人工智能问题一样，分为三个设计阶段。首先我们必须决定如何表示魔方的当前状态。然后还必须表示对魔方的操作。最后必须解决如何把这些操作运用到魔方上。在搜索中也会有一定的优化，由于状态图是按树型结构展开，所以，这里的优化就是指“剪枝”操作。关于搜索的方法，采用的是A算法。在后面回有详细介绍。对于魔方状态图的存储，在本程序中采用了一个二维数组，在用二维数组存储魔方状态图的时候，考虑到存储空间的问题，虽说，在本程序中只在魔方复原的第一阶段用到了搜索，并且搜索的层数不是很多，但还是只用了一个状态图来表示魔方的当前状态1，这样，多少可以节省空间，但在求解时间上可能会长一些，但不是很明显。关于这些在后面会有专门的介绍。13关于专家系统的简介前面已经谈到用盲目搜索的方法对魔方问题求解是毫无办法的，因此，只能将一些复杂的旋转序列嵌到程序中去，这样在魔方问题的求解过程当中就可以节省大量的空间和时间，从而提高程序的效率。这种方法就是我所谈到的专家系统。专家系统就是将某一个领域的知识进行合理的组织，与计算机程序的合理组合。专家系统的应用很广，在医疗、工程和商业上都有广泛的应用。严格地讲，任何具有专家功能的程序都被称为是一个专家系统。在解决问题中，通过运用知识体达到专家级水平的AI程序叫做知识系统或专家系统。一个专家系统的主要部分包括两个方面知识库和推理引擎。在本程序中，由于是一个很简单的专家系统，所以只包含了这两个最主要的方面，但一个完整的专家系统的结构应该是，一个“知识工程师”（经常是一个训练过的AI计算机科学家）与应用领域的一个专家（或几个专家）共同工作以便把专家的相关知识表示成一种形式，以使它能被输入到知识库。这个过程经常由一个知识采集子系统协助1。和其他情况一样，这个子系统检查正在增长的知识库的可能不一致和不完备信息，然后将它们表示给专家以做出决定。当然，由于本程序并没有涉及到专家系统中的各个方面，只是知识在程序中的简单应用，所以对这些并不详细的讨论。一个专家系统的基本结构图图11专家系统的结构。14文件的输入对于魔方文件的输入，在这里简单的介绍一下。输入时，依次输入上面、左面、前面、右面、下面和后面，各面的颜色状态，在这里对颜色有严格的要求，当然，这种要求可能会对程序的灵活性有一定的影响，但我认为还是值得的。标准魔方的颜色，我把红色定为上面，绿色定为左面，黄色定为前面，蓝色定为右面，橙色定为下面，白色定为后面。在这里要注意一点，输入的时候最好是把各面都转到前面来进行输入，在这里只有后面是按照从右到左，从上到下的顺序输入，其它各面当转到前面的时候都是按照从左到右，从上到下的顺序输入。关于输入的这一点，主要是和我采取的存储方式有关，如果这里不是说的很清楚的话，那么，在后面我将会给出我魔方存储的状态图，看到这张图的时候，相信会对输入方式有更深的理解。图11专家系统的结构15本章小结通过本章能看出魔方在编写及实现中基本的概念和实现方法，先介绍了魔方的玩法及原理，以及关于搜索与存储的问题的初步设想，对于专家系统运行模式比较详细简介，也对文件输入方法进行笼统的介绍。专家用户知识采集子系统用户接口知识库事实、启发式知识工程师解释子系统推理引擎第2章程序总规划21程序的总体设计这里我考虑到程序应该有一点游戏性，所以当输入一个魔方状态时也可以试着人工来求解，当然在任何时候都可以像电脑寻求帮助。程序的编写，我更看重的是它的算法，所以采用编写控制台应用程序，可能程序的界面不是很绚丽，但算法的基本功能都能实现，我想这也就算达到了目的。为了增加程序的可读性，同时，也为了使程序的编写更加顺利，将不同功能的代码分别放在了不同的文件中编写（CPP文件）。按照代码功能的不同，将程序分为六个不同的源文件2。其中，MAINCPP文件是程序的入口，它主要是对在程序中用到的各种变量进行定义。在这里有一点需要说明一下，考虑到为了方便程序的编写，我将使用比较频繁的变量定义为全局变量，这样在不同的源文件中，在各个需要它们的地方可以很方便的引用它们。这样的做法可能是不提倡的，但在这里我觉得是值得的。由于这样的变量不是很多，所以应该不会对程序的可读性造成多大的影响。其中，GMCPP文件的主要功能是将从文件中接受到的魔方各个面的颜色状态存放到魔方的状态图中，状态图变量的定义为全局变量。关于魔方状态图的实现在后面将会有详细的介绍，在这里就不过多的涉及这个问题。其中，BEGINCPP文件的主要功能是在控制台中打印出程序的操作界面，接受用户的输入，对合理的输入给出相应的操作，对不合理的操作给出相应的提示。并且，通过调用其它文件中的函数来对魔方进行求解3，同时判断魔方是否被解出。其中，CHANGEMFCPP文件的主要功能是实现当对魔方各个面进行操作后，魔方状态图的变化。可以说，这在程序的设计过程中是个比较费时，但又相当重要的一个环节。因为只有保证这部分的代码准确无误，才能确保魔方顺利的求解。其中，包含对魔方六个面的12种操作，每个面有两种操作。其中，SEARCHCPP文件的主要功能是实现搜索功能，也就是搜索我们想要得到的魔方状态，这主要应用在了魔方复原的第一阶段。这部分设计的难点是它的数据结构，主要是考虑采用何种结构才能实现当前状态的扩展同时又要将不合要求的状态存入扩展序列。这是个难点，关于这些后面会有更详细的介绍。搜索的实现采用了BFS搜索4，这样可以保证搜索到需要的状态图的路径是最短的。在搜索的过程中，会有一定的优化。其中，EXPERTCPP文件的主要功能是将各种魔方复杂的旋转操作序列合理的组织在程序中，以便可以对魔方顺利求解。这个文件就是本程序中提到的专家库，就是魔方具体玩法。关于魔方的玩法有很多，在本程序中我主要研究了所谓的“八角法”，这个文件中就汇集了在这种玩法下的旋转操作序列5。当然，各种玩法都不是健全的，有些极其复杂的情况光靠一种玩法的操作序列是不能求解的，这个我没有考虑，因为，在我目前所实验的魔方的各种状态“八角法”都可以求解。关于这些，这里不在多说（图21给出了程序执行的总体流程图）。22全局变量的定义在程序的执行过程中，有些比较重要的全局变量，在这里我简单的谈谈这些。首先是接受魔方状态文件的数组，用到的是一个129的字符型二维数，这个数组为GRAPHMF129。同时，还有时刻保存魔方当前状态图的数组，也就是在程序的执行过程中实际操作的数组，这个数组为GRAPHSTA129。还有一个记录魔方初始状态的数组，这个数组为GRAPHMF1129，这个数组是为了在程序执行时，开始选择的是由人工来解决魔方问题，但在后来选择了帮助，由电脑解决时可以很方便的将魔方的初始状态传给魔方实际操作的数组GRAPHSTA。在程序执行的初期，当接受到魔方状态文件的时候就将GRAPHMF中的内容复制到GRAPHSTA和GRAPHMF1中6。可能，这么做不是很容易叫人理解，因为，同一种状态却要两个副本，但我这么做只是为了程序编写的方便。还有一个很重要的变量，就是对魔方正确的解决序列进行存储的变量。这里定义了一个队列RC。在程序的执行过程当中，只要是对魔方合理的正确的操作就都存储在这个队列当中，使魔方的正确解决过程得到保存。在魔方复原的第一阶段，为了很方便的将搜索于专家系统联系到一起，用到了一个指向函数的指针，定义的形式为VOIDP。在EXPERTCPP中FIRSTSTAGE函数中可以找到它的具体应用7。23各个模块间的调用关系程序首先由MAINCPP进入，调用BEGINCPP中的SEARCH_BEGIN函数，由这个函数开始真正的对输入的魔方状态进行求解。首先在这个函数中调用GMCPP中的GETGRAPH函数、MAKEGRAPH函数和SEARCHCPP中CHANGE函数，完成对魔方状态文件的接受和两个副本的拷贝。然后调用自身的CHOICE函数，来接收用户的选择，同时，当用户选择的是人工解决的时候，则在用户每一次对魔方操作后，调用CHANGECPP中的相应的魔方操作函数（因为只是对魔方状态图的操作，所以这里的函数会在后面说明），然后调用SEARCHCPP中的COMPARA函数，由此来判断魔方是图21求解程序的流程否已经被复原。如果在CHOICE函数中选择的是由电脑来解决的话，则依次调用EXPERTCPP中的FIRST_STAGE、SECOND_STAGE、THIRD_STAGE、FORTH_STAGE、FIFTH_STAGE、SIXTH_STAGE、SEVENTH_STAGE、EIGHTH_STAGE，这几个函数来对魔方进行求解，在这个几个函数的执行过程中，他们分别调用自身的含有解决特定魔方状态下魔方的旋转序列，同时，也会对CHANGECPP中的魔方操作函数进行调用。值得一提的是，在FIRSTSTAGE函数中需要调用SEARCHCPP中的BFS函数，对魔方的状态图进行搜索，找到符合要求的状态图。最后，调用搜索文件（SEARCHCPP）中的MISSION_COMPELET函数8，来判断魔方是否被解出，并且，给出求解的过程。当然，在这些函数功能的实现过程中，在上面谈到的全局变量都会出现在各自的函数中，在这里就不过多的说明。24本章小结在本章中主要是对程序总体设计的游戏性、可读性在程序中怎样实现的进行了详细的解说，在程序的执行过程中，全局变量是如何定义的，以及说明了各模块间是如何相互调用它们之间的关系。第3章各个模块的详细设计31主模块这个模块比较简单，就是程序的入口和一个简单的操作选择，和一些变量的定义，由于代码不是很长，所以，给出的它的全部代码，其它的在这里就不多说了。INCLUDE“ALL_FUNCTIONH“INCLUDEINCLUDEINCLUDEINCLUDEUSINGNAMESPACESTD/定义魔方矩阵,全局变量CHARGRAPHMF129/接收文件的数组CHARGRAPHSTA129/实际操作的数组CHARGRAPHMF1129/用来记录魔方初始状态的数组QUEUERC/存储魔方操作的步骤BOOLSOLVE_1FALSEVOIDP/函数指针,用在魔方复原第一阶段的BFS中/魔方文件的输入中有六行,对应六个面,必须按照R,G,Y,B,O,W面的顺序输入/VOIDMAINSTRINGCWHILE1SEARCH_BEGIN/求解开始COUTCIFC“N“|C“N“BREAK32文件接收模块文件接收模块GMCPP。这个模块主要是为了实现对魔方状态文件的接收，和它的副本的创建。在这里我想先谈谈魔方的状态图，由于魔方有五十四小面，六个“大面”，“大面”分别是指魔方的上、下、左、右、前、后，六个面。所以，采用一个二维数组来存储这五十四个小面，但它的存储也要遵守一定结构，在这节的最后我会给出它的存储状态图，以方便对存储这个问题的理解。对于文件的接收也没什么太多的说法，就是有一点需要说明，这就是，在魔方状态图文件中的每一行对应魔方的一个“大面”，而每一个“大面”又有九个“小面”。主要是由以下的代码来完成这个功能。CHARS620CHARFILENAME100COUTFILENAMEIFSTREAMINSTUFFILENAME,IOSINIFINSTUFCERR2就为将角块1中的颜色（也就是数组的数据）送到角块2中去。对于边块的操作与角块一样，这里就不多说。VOIDFRONT_1CHARTEMPORARY03/存储角块的临时变量CHARTEMPORARY12/存储边块的临时变量/对角块操作/TEMPORARY00GRAPHSTA35/存储2到临时变量TEMPORARY01GRAPHSTA36TEMPORARY02GRAPHSTA25/12GRAPHSTA35GRAPHSTA33GRAPHSTA36GRAPHSTA23GRAPHSTA25GRAPHSTA32/41GRAPHSTA33GRAPHSTA53GRAPHSTA23GRAPHSTA52GRAPHSTA32GRAPHSTA63/34GRAPHSTA53GRAPHSTA55GRAPHSTA52GRAPHSTA65GRAPHSTA63GRAPHSTA56/23GRAPHSTA55TEMPORARY00GRAPHSTA65TEMPORARY01GRAPHSTA56TEMPORARY02/对边块操作/TEMPORARY10GRAPHSTA34/存储2到临时变量TEMPORARY11GRAPHSTA24/12GRAPHSTA34GRAPHSTA43GRAPHSTA24GRAPHSTA42/41GRAPHSTA43GRAPHSTA54GRAPHSTA42GRAPHSTA64/34GRAPHSTA54GRAPHSTA45GRAPHSTA64GRAPHSTA46/23GRAPHSTA45TEMPORARY10GRAPHSTA46TEMPORARY11相信看过以上的代码后，会很容易理解这个模块的功能和实现的方法。由于，其它函数的操作都与上面给出的例子大体相同，在这里就不过多的说明。这些就需要对魔方的平面状态有一定的了解，只有这样才能准确的想象出魔方每一次旋转后数组中的数据交换的过程。在交换的时候，为了保证数据不丢失，应该将一个角块或边块的数据首先存储到一个变量中去，然后在对这个角块或边块中的数据进行替换。这一切上面的代码都已经写的很清楚。在这里我们还有两个函数并没有提到过，一个是LEFT_FRONT，实现的操作是，LEFTFRONTRIGHTBACKLEFT的各个面间的数据进行转换，而另外一个实现的操作是，FRONT_DOWN，实现FRONTDOWNBACKUPFRONT的各个面间的数据转换14。这些和我给出的例子的操作是一样的，这里就不多说。这两个函数的定义主要是为了和专家系统的融合，因为在“八角法”中有这样的操作。35搜索模块搜索模块SEARCHCPP。这个模块在整个魔方求解的过程中是十分重要的一个模块，主要是实现在魔方复原的第一阶段的搜索，对魔方状态图的搜索。这是程序设计中的一个难点，因为这里涉及到了搜索的方法和一些数据结构的问题。首先，谈谈搜索的问题。就像在概述中提到的那样，在魔方求解的问题中盲目的搜索是起不到任何作用的，必须采用专家系统。但在这里我先不讨论专家系统的问题，就想对搜索的方法和如何优化搜索过程进行说明。搜索方法采用的是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种不同的操作，然后，判断是否找到需要的状态。下面给出它的扩展图，只是两个结点的扩展，其它的由省略号表示。图31节点扩展图关于结点在程序中的实现是由下面的代码定义的。STRUCTNODECINTV/旋转方式NODECPARENT/用来指向父结点NODECNEXT/用来指向扩展结点/父结点的具体指向NODECL_1NODECL_2NODECR_1NODECR_2NODECU_1NODECU_2NODECD_1NODECD_2NODECF_1NODECF_2NODECB_1NODECB_2其中父结点的具体指向就是结点的12种扩展方式，这里你有可能注意到了有几个变量在上面的扩展中没有提到，这些在后面都会有相应的说明，它们在搜索的过程中也是十分重要的。下面谈谈如何构造扩展结点的链表，在A算法中用到了两个表，一个是OPEN表，一个是CLOSED表，再一个是表示还没有扩展的结点集，一个是表示已经被扩展过的结点集。在这里我只用了一个链表，然后用一个上面定义的结构体类型的指针（NODECHERE）指向链表中需要扩展的结点，当前的结点被扩展，则HERE指向当前结点的NEXT所指向的结点。至于什么样的结点需要加入到扩展链表中，在这里，每当当前结点被扩展的时候，其中不符合要求的结点就都进入的扩展链表中去。这里还有一个问题，就是PARENT指针的应用，它并不是要找到正确求解路径的指针，我在这里引用它主要是由于魔方状态图在搜索的过程中会用到大量的存储空间，所以，为了节省空间，我在搜索的时候始终只用了一个数组（GRAPHSTA）。那么，如何实现用这一个数组就可以准确的找到当前要扩展结点的正确状态图的呢这就是PARENT指针的用处，在这里我采用了回朔的方法，一个在程序设计中经常用到的方法。每当要扩展当前结点的时候，就通过PARENT指针将当前结点的父结点的旋转方式（也就是变量V中的数据）存储到一个堆栈中去，然后在将弹出堆栈中的数据，然后采取相应的旋转操作（对魔方初始状态图的操作）15，这样就可以很顺利的找到当前要扩展的结点的正确的状态图。下面给出这部分的代码，其中，变量的定义为STACKRB恢复当前结点状态，其中，V的数据分别用112这些数字表示，它代表魔方状态图的具体旋转操作。/找到当前要扩展的结点的旋转过程/VOIDREBACKNODECPPHEREWHILEPV0RBPUSHPVPPPARENT/将扩展的旋转序列转换成具体的旋转操作,得到魔方当前的状态图/VOIDNODE_OPERATIONINTIWHILERBSIZE0IRBTOPSWITCHICASE1FRONT_1BREAKCASE2FRONT_2BREAKCASE3BACK_1BREAKCASE4BACK_2BREAKCASE5LEFT_1BREAKCASE6LEFT_2BREAKCASE7RIGHT_1BREAKCASE8RIGHT_2BREAKCASE9UP_1BREAKCASE10UP_2BREAKCASE11DOWN_1BREAKCASE12DOWN_2BREAKRBPOP以上就是这部分搜索实现的关键，搜索过程采用的是广度优先搜索，只要对以上的问题有了了解，搜索起来就不是很困难，但在搜索过程中涉及到搜索优化的问题。由于结点的扩展采用的是树型结构，所以，优化就是对搜索树的剪枝。在魔方的操作中有这么两种情况值得注意一种是，如果上次的操作是某个面的顺时针操作，这次操作如果是这个面的逆时针操作的话，就会回到魔方的初始状态，以根结点为例，当对根结点的某个面进行一次顺时针操作，再进行一次逆时针操作，这个时候的魔方的状态就是根结点的状态，也就是说，在对这个结点进行扩展是毫无意义的。这是在不断的重复根结点的扩展。也就是说，对同一个面的两次相邻的操作不能是互逆的，也就是，不能对它进行顺时针（逆时针）操作后，在进行逆时针（顺时针）操作。所以，在搜索树的扩展中，对这种操作应该采取剪枝。另一种情况是，每当对同一个面进行四次相同的操作后（四次顺时针或四次逆时针）也会回到最初的状态，如果对上面的剪枝有了了解，这个就不是很难理解。所以，对这部分操作也要采取剪枝操作。下面给出剪枝和和搜索的一部分代码，是对前面顺时针旋转操作扩展的代码，其它面的进行搜索时扩展的代码和这些基本相同。其中，RE_CHECK来判断是否需要剪枝。/不扩展上次旋转的逆操作IFRE_CHECK2FRONT_1PIFSOLVE_1TRUENEWNODENEWNODEC/申请新结点NEWNODENEXTNULLNEWNODEV1/旋转方式NEWNODEPARENTHERE/指向父结点HEREF_1NEWNODE/父结点前面顺时针指针指向新结点NEXTNODENEXTNEWNODE/新结点插入队尾，构造扩展链表NEXTNODENEWNODEBREAKELSENEWNODENEWNODEC/申请新结点NEWNODENEXTNULLNEWNODEV1/旋转方式NEWNODEPARENTHERE/指向父结点HEREF_1NEWNODE/父结点前面顺时针指针指向新结点NEXTNODENEXTNEWNODE/新结点插入队尾，构造扩展链表NEXTNODENEWNODEFRONT_2/恢复到扩展前的状态REPUSH1/剪枝序列在这里还有一点要说明，虽说第二种剪枝按理说是应该执行的，但由于搜索只是应用在了解决魔方问题的第一部分，并且，在这里搜索树的层数不会达到四层，所以，在程序里我就没有对这种情况进行剪枝的操作。到这里搜索部分就算是结束了，剩下的就是如何将它应用到解决到魔方复原的第一段，关于这个会在谈论专家系统的时候给出。36专家系统模块专家系统模块EXPERTCPP。这是程序中最为关键的一个模块，在这里将魔方中复杂的旋转序列与程序结合到了一起，从而完成了对魔方的求解。这部分的程序并不是很难写，关键是知道如何解决魔方问题，也就是知道按照什么样的规律来解决魔方问题。每当找到符合要求的状态时就调用专家序列给出正确的求解步骤。这种方法很多，由于方法的不同，会影响到魔方求解时的步骤多少问题。我在这里选择的是“八角法”，这种方法解决魔方问题在求解的步骤上并不是很好，也就是步骤会比较多，选择它只是因为它学起来比较容易，因为我也是才接触魔方，所以选择了一个比较容易学习的方法来处理这个问题。在这里有一点需要说明，虽然求解的步骤比较多，但是在求解的速度上并没有什么太大的不同，一般来说用不上一秒就可以求解。下面就我所采用的专家方法“八角法”给以说明。由于，并不是魔方玩法的教学，所以，我只是简单的介绍，重点是这个方法在程序中是如何表示出来的。“八角法”，就是在解决魔方问题的时候，首先复原魔方的八个角块。然后在复原其它的小块。“八角法”解决魔方问题一共分为八个阶段。在进行“八角法”之前要恢复魔方的八个角块的位置，但颜色不对，这个过程是用另一种方法完成的，因为在“八角法”中并没有给出这部分的是如何解决的。接下来介绍一下“八角法”解决魔方问题的八个阶段。第一阶段是在魔方的顶面构建出一个“X”，可以任意指定魔方的顶面，在我的程序中我指定的这个阶段的顶面为白色。所谓“X”就是顶面的角块向上的颜色与中块的颜色相同。第二阶段是在魔方的底面构建出一个“X”，在第一阶段后，所有含底面颜色的角块，应该都在底面，只可能色向不对。这个过程与上面的过程相似，只要把底面转到顶面，然后把底面当做顶面来处理。第三阶段是复原所有的角块，通过前两个阶段后魔方的顶面和底面的角块都已经在自己的位置，而且向上面的颜色都已经符合要求，只剩下角块的边色没有对上。而这个阶段就是要解决这个问题。在这里需要为成对的上角快和下角块分别记数，如果每个侧面上两个上角块或两个下角块的颜色相同就为一对。然后根据成对的情况来选择合适的魔方旋转序列。第四阶段是在顶面恢复三个正确的边块。在这里边块的位置和色向都要考虑，每次只考虑一块，直到这个阶段的完成。在这个阶段只恢复三个边块，当然，有的时候很碰巧第四个边块也在正确的位置，这个先不用过多的考虑，在下面的阶段会给这种情况的处理方法。第五阶段是恢复底面的所有边块。在第四阶段有一个边块没有恢复，在这里就要用到这个边块，把他当作“洞”，如果在上个阶段碰巧四个边块都恢复了，那么在这里就以任意一个上边块当作“洞”。把这个“洞”转到前面，然后寻找要到要恢复的下边块的位置套用具体的旋转序列。重复这阶段的操作，直到底面的边块都复原。第六阶段是恢复顶面的最后一个边块。当然，如果在第四阶段已经恢复的话在这里就不需要这个过程，直接进入第七阶段。在这里旋转魔方，把有“洞”的顶面转到左面或者右面，然后选择合适的旋转序列，恢复这最后一个边块。第七阶段是恢复魔方中间边块的过程。在上面几个阶段过后，魔方基本上已经被复原了，只剩下魔方的中间块没有被复原。这没有什么难度，只需要找出没有被复原的中间块的具体状态后，就可以套用固定的旋转序列来求解。当然，有的时候由于情况比较特殊，没有符合的专家操作序列。不过只要通过旋转魔方就可以找到符合要求的状态。第八阶段是恢复魔方中间边块的色向。在这里和上面一样，魔方原来的顶面和底面依然摆放到魔方的左右两面，然后找到符合要求的状态，套用专家操作序列。通过上面的八个阶段，魔方在大部分情况下就已经被复原了。因为有些极其特殊的情况用这种方法没有办法求解，这个问题在前面已经谈过。通过上面对“八角法”的叙述可以看出，这个部分没有什么多大的难度，只要把魔方状态考虑完全就可以了。只是在魔方第一阶段前的八个角块的复原有些需要说明的。在复原魔方八个角块的时候，用到了在上节提到的搜索技术。因为，复原八个角块的专家序列也是在要恢复的角块在某些固定的位置的时候才能够起到作用。但是在魔方的初始状态中，要恢复的角块不一定是符合要求的，这就需要旋转魔方将要恢复的角块转到符合要求的位置。这个过程如果考虑各个可能的情况是很难的，所以用到了搜索，这样可以很快的将要恢复的角块转到符合要求的位置，从而很快的对魔方求解。恢复八个角块的过程是由这个模块中的FIRSTSTAGE函数实现的，因为在这里在搜索的过程中要时刻对比搜索到的魔方状态是否符合那几种固定的要求，所以，为了方便操作，用到了一个指向函数的指针P，关于它的定义在前面已给出说明，这样是可以很方便的来调用对比函数（COMPARA1、COMPARA2、COMPARA3和COMPARA4）。关于其它几个阶段的实现分别是由SECONDSTAGE、THIRDSTAGE、FORTHSTAGE、FIFTHSTAGE、SIXTHSTAGE、SEVENSTAGE和EIGHTSTAGE来完成的16。由于在这个模块的各个函数中都是一些专家序列，程序无外就是将魔方的状态与它们比较，如果符合要求就调用专家序列，不符合要求就通过旋转魔方，使魔方的状态符合要求再调用专家序列。所以在这里不给出任何代码。37本章小结通过以上可以看出主模块是建立在各个分模块相互调用的基础上，对文件接收模块、程序执行模块、旋转操作模块、搜索模块以及专拣模块分别进行说明，并给出基本求解过程和图解。第4章程序演示1程序开始运行后的显示。图41程序启动后的界面2输入魔方文件后的显示。图42魔方的初始状态3选择人工解决后的显示。图43人工操作界面4在选择人工解决后输入F后的显示。图44人工选择一个操作后的状态5在输入“H”后的显示。图45人工操作中间选择H后由电脑自动求解6在程序一开始就输入电脑。图46在程序开始选择电脑自动求解到这里已经把程序的执行过程简单地做了演示。结论这次毕业设计所选的题目对我来说是一个很大的挑战，因为在以前从来没有写过任何与专家系统有关的程序。刚开使拿到这个题目的时候，没有考虑很多，也没有想到这个问题会那么不容易解决。在慢慢开始着手做这个程序的时候才发现有很多东西是我没有接触过的，这些都需要通过自己来学习。在程序的编写过成中遇到了很多的困难，有些困难曾让我有放弃的念头，因为在当时真的不知道如何来解决这些问题。所以本打算在假期就将这个题目彻底解决的念头也随着这些困难消失了，而且无论怎么想也找不到很好的解决办法。这些困难主要是在如何构建魔方的状态图，如何完成对魔方各个面的旋转操作，如何在搜索中如何解决数据结构的问题等等。在假期快要结束的时候，找到了构建魔方状态图的方法，也完成了对魔方各个面旋转操作的函数的编写。在这个时候，我以为只要将搜索部分完成，这个题目就可以顺利的解决，根本没有考虑到专家系统的问题。在开学后，开始着手搜索部分程序的编写，当这部分程序编写完以后，新的问题又出现了。这就是由于魔方状态图很大，而我采用的是盲目搜索，这样的话在搜索树每增加一层的时候魔方的状态图会以几何数级增长，这需要大量的存储空间，占用大量的内存。所以我改变的了对魔方状态图的存储方法，采用了不存储状态数组，而是存储魔方的旋转方式的，再通过回朔来找到要扩展的状态图的当前状态。但是这样也没有解决这个问题，并且我发现在我的机器上搜索树最多也就能扩展到七层，当到七层的时候我的内存就被耗尽了。这也就说明我的程序只能解决在七步之内找到复原路径的魔方，而且速度相当的慢。在那个时候这是另我最头痛的问题。在没有办法用盲目搜索解决这个问题的时候我考虑到了专家系统。于是找了很多关于魔方的玩法的资料，在这些资料中只有“八角法”是最适合初学者的。但是，新的问题又出现了，这个方法是在复原了八个角块以后才可以用的，但它并没有给出如何恢复八个角块的序列。不过还好，在同学的帮助下找到了如何复原八个角块的操作方法。在这个时候我认识到，如果想解决这个题目自己必须要学习玩魔方，于是就照着我找到的资料开始学习如何玩魔方，还好在几天后终于将魔方复原了。于是开始着手专家系统的编写，在一个礼拜左右后我将这个题目基本上解决了，只是有些特殊的情况是无法解决的，在几次改进后有些特殊的情况也的到了解决。现在的程序基本上可以解决大部分魔方状态。参考文献1NJNILSSON人工智能M北京机械工业出版社,2000362BECKELC编程思想（第二版）,第1卷标准C引导M北京机械工业出版社,20027193罗斌VISUALC编程技巧精选500例M北京中国水利水电出版社,20051224BECKELC编程思想,第2卷实用编程技术M北京机械工业出版社,20061115肖宏伟VISUALC实效编程百例M北京人民邮电出版社,2004836SCOTTMEYERSEFFECTIVEC（第三版）（中文版）改善程序技术与设计思维的55个有效做法M电子工业出版社,2006997朱战立,张玉祥C面向对象程序设计M人民邮电出版社,20064208许家珆,曾翎软件工程理论与实践J北京高等教育出版社,20057169艾德才C程序设计简明教程M中国水利水电出版社,20006310SMEFFECTIVEC英文版M北京机械工业出版社,20064711朱福喜,朱三元,伍春香人工智能基础教程M北京清华大学出社,200631212肖永亮VISUALC游戏编程基础M北京电子工业出版社,200553313贲可荣,张彦铎人工智能M北京清华大学出版社,2006320114雷英杰人工智能（AI）程序设计（面向对象语言）M北京清华大学出版社,200536515JDRILEY专家系统原理与编程（英文版第四版）M北京机械工业出版社,200571916WALTERSAVITCHC面向对象程序设计基础、数据结构与编程思想M清华大学出版社,200467致谢到此论文暂告收尾，回首往昔，在设计毕业设计这段时间，我参考了大量国内外宝贵文献资料，不仅将以前的知识学以致用，同时我接又触了很多以前没有接触过的理论，学会了很多实用的知识，相信对我以后的学习上和思想上都受益匪浅。在设计期间，我遇到了很多自己无法解决的问题，多亏老师、同学的帮忙，才能使我顺利完成设计。在此，我要谢谢李静、孙玲老师的悉心教导，谢谢各位同学的热心帮忙，在以后的学习工作的道路上，我会更加努力，更上一层楼请您删除一下内容，O_O谢谢MANYPEOPLEHAVETHESAMEMIXEDFEELINGSWHENPLANNINGATRIPDURINGGOLDENWEEKWITHHEAPSOFTIME,THESEVENDAYCHINESE请您删除一下内容，O_O谢谢NATIONALDAYHOLIDAYCOULDBETHEBESTOCCASIONTOENJOYADESTINATIONHOWEVER,ITCANALSOBETHEEASIESTWAYTORUINHOWYOUFEELABOUTAPLACEANDYOUMAYBECOMEMOREFATIGUEDAFTERTHEHOLIDAY,DUETOBATTLINGTHELARGECROWDSDURINGPEAKSEASON,ADREAMABOUTAPLACECANTURNTONIGHTMAREWITHOUTCAREFULPLANNING,ESPECIALLYIFYOUTRAVELWITHCHILDRENANDOLDERPEOPLEASMOSTCHINESEPEOPLEWILLTAKETHEHOLIDAYTOVISITDOMESTICTOURISTDESTINATIONS,CROWDSANDBUSYTRAFFICAREINEVITABLEATMOSTPLACESALSOTOBEEXPECTEDAREINCREASINGTRANSPORTANDACCOMMODATIONPRICES,WITHTHEPOSSIBILITYTHATTHEREWILLBENOROOMSAVAILABLEITISALSOCOMMONTHATYOULLWAITINTHELINEFORONEHOURTOGETATICKET,ANDANOTHERTWOHOURSATTHESITE,TOONLYSEEATINYBITOFTHEPLACEDUETOTHECROWDSLASTYEAR,428MILLIONTOURISTSTRAVELEDINCHINAOVERTHEWEEKLONGHOLIDAYINOCTOBERTRAVELINGDURINGTHISPERIODISAMATTERTHATNEEDSTHOROUGHPREPARATIONIFYOUARESHORTONTIMETOPLANTHEUPCOMING“GOLDENWEEK“ITMAYNOTBEABADIDEATOAVOIDSOMEOFTHEMOSTCROWDEDPLACESFORNOWTHEREISALWAYSAPLACESOFASCINATINGTHATEVERYONEYEARNSFORARXANISAPLACELIKETHISTHEBEAUTYOFARXANISEVERLASTINGREGARDLESSOFTHECHANGINGOFFOURSEASONSBESTOWEDBYNATURE,ITSSPECTACULARSEASONALLANDSCAPEANDMOUNTAINSAREJUSTBEYONDWORDARXANISACRUCIALDESTINATIONFORTHERECOMMENDEDTRAVELLINGROUTE,“CHINAINNERMONGOLIAARXANHAILARMANZHOULI“ITISALSOTHEJOINTOFTHEFOURPRAIRIESACROSSTHESINOMONGOLIANBORDER,WHEREPEOPLEGRAVITATETOWARDSTHEEXOTICATMOSPHEREMIXEDWITHCHINESE,RUSSIAN,ANDMONGOLIAELEMENTSASAHISTORICSITEFORTHEYITIANBATTLE,ARXANSTILLEMBODIESTHESPIRITOFGENGHISKHANWALKINGINTOARXAN,YOUWILLBEAMAZEDBYAKALEIDOSCOPEOFGORGEOUSCOLORSALLTHEYEARROUNDTHESPRINGAZALEASBLOOMINGREDINTHESNOW,THESUMMERSEAWAVERINGBLUEINTHEBREEZE,THEAUTUMNLEAVESPAINTEDINYELLOWCOVERINGVOLCANICTRACES,ANDTHEWINTERWOODSSHININGWHITEONTHEVASTALPINESNOWSCAPEHINGGANLEAGUEARXANCITYISSITUATEDINTHEFAREASTERNAREAOFINNERMONGOLIAAUTONOMOUSREGIONITSFULLNAME“HARENARXAN“MEANS“HOTHOLYWATER“INTHEMONGOLIANLANGUAGEARXANISATOURISMCITYINTHENORTHERNFRONTIERWITHABLENDOFLARGEFOREST,GRANDPRAIRIES,VASTSNOWFIELD,HEAVENLAKECLUSTER,THERMIUM,ASWELLASVOLCANICCLUSTERITISARAREANDUNIQUEECOTOURISMBASEFILLEDWITHHEALTHYSUNSHINE,CLEANAIRANDUNSPOILEDGREENNESTLEDCLOSETOTHECOUNTRYSLARGESTVIRGINFOREST,