毕业论文《基于广搜解Rubick魔方》.doc

学号 14082200137期鬲理王学吃基于广搜解Rub i ck魔方课题名称：基于广搜解Rubick魔方姓 名：—学 号：14082200137专 业：信息工程所在班级：电信 08-2BF 指导教师：姓名： 时 间：二零一二年六月一日摘要作为主流的动态语言，python不仅简单易学、移植性好，而且拥有强大丰富的库的 支持此外,python强大的可扩展性,让开发人员既可以非常容易地利用c/c++编写python 的扩展模块，还能将python嵌入到C/C++程序中，为自己的系统添加动态扩展和动态编 程的能力通过基于广搜Rubik魔方来更深入的了解这门语言本文对二阶魔方进行初步介绍、分析需要解决的问题并给出了一个简单的搜索算法 后，通过深入分析问题的本质，从减少搜索量、优化判重算法、节省内存空间、消除冗 余等方面分别对程序进行了一步步的优化，同时从代码的紧凑性方面进行深入地分析了 算法复杂度前所隐含的系数，并针对这方面进行了有效的系数优化，最终得到了一个平 均每秒能够解数百个二阶魔方的高效算法关键词 双向BFS,二叉排序树，哈希表，魔方的表示方式，初始化打表，位置 与状态分治目录摘要 I关键词 I目录 1第一章绪论 61.1二阶魔方介绍 61.2广度优先搜索 61.3BFS的运用 6第二章文本远程算法简介 82. 1什么是文本远程纠错 82.2逐行文本比较 82. 3最大匹配率 162.4二分查找纠错 162.5影响文本纠错算法的因素 17第三章系统开发工具 183. 1开发工具 python 简介 183. 2python 的基本形式 183. 2. 1 缩进 183.2. 2语句和控制流 183.2.3 函数 193.2.4面向对象编程 19第四章哈希算法 204. 1哈希的概念 204. 2哈希的优越性 204. 3字符串哈希算法简介 204. 4滚动哈希算法 234. 5哈希算法的应用 23第五章两种文本纠错算法的python实现 255.1逐行比较纠错算法 255.2二分查找纠错算法 26第六章结论与展望 28致谢 29参考文献 30附录 31问题提出：对于一个给定的打乱的二阶魔方，通过计算机搜索的方法，问该魔方至少 需要转动几次（转动一个面90度，180度，270度均认为是一次转动）才可以最终达到还 原的状态？二阶魔方介绍：二阶魔方的英文官方名字叫做Pocket Rubiks Cube或Mini Cube,中文直译叫做“口袋 魔方”。

它每个边有两个方块二阶魔方的总变化数为3674160或者大约63.67 X 10 o 二阶魔方（PocketCube）又称口袋魔方、迷你魔方、小魔方、冰块魔方，为2X2X2的立方体结构身只有8个角块，没有其他结构的方块基本思想：由于题目要求的是要求出二阶魔方从某个打乱状态到还原态的最短路径，所以通常用来求某个解的递归算法一深度优先算法并不可行，所以在解决这个问题的过程中我决定 采用广度优先搜索BFS）广度优先搜索宽度优先搜索算法（又称广度优先搜索）是最简便的图的搜索算法之一，这一算法也是很多重要的图的算法的原型Dijkstra单源最短路径算法和Prim最小生成树算法都采用了 和宽度优先搜索类似的思想已知图G=（V,E）和一个源顶点s,宽度优先搜索以一种系统的方式探寻G的边，从而“发现” s所能到达的所有顶点，并计算s到所有这些顶点的距离（最少边数），该算法同时 能生成一棵根为s且包括所有可达顶点的宽度优先树对从s可达的任意顶点v,宽度优先 树中从s到v的路径对应于图G中从s到v的最短路径，即包含最小边数的路径该算法有向图和无向图同样适用之所以称之为宽度优先算法，是因为算法自始至终一直通过已找到和末找到顶点之间的边界向外扩展，就是说，算法首先搜索和S距离为k的所有顶点，然后再去搜索和S距 离为k+1的其他顶点。

为了保持搜索的轨迹，宽度优先搜索为每个顶点着色：白色、灰色或黑色算法开始前 所有顶点都是白色，随着搜索的进行，各顶点会逐渐变成灰色，然后成为黑色在搜索中第 一次碰到一顶点时，我们说该顶点被发现，此时该顶点变为非白色顶点因此，灰色和黑色 顶点都已被发现，但是，宽度优先搜索算法对它们加以区分以保证搜索以宽度优先的方式 执行若（u,v） E e且顶点u为黑色，那么顶点v要么是灰色，要么是黑色，就是说，所有和 黑色顶点邻接的顶点都已被发现灰色顶点可以与一些白色顶点相邻接，它们代表着已找到 和未找到顶点之间的边界在宽度优先搜索过程中建立了一棵宽度优先树，起始时只包含根节点，即源顶点s.在 扫描已发现顶点U的邻接表的过程中每发现一个白色顶点V,该顶点V及边(u,v)就被添加到 树中在宽度优先树中，我们称结点U是结点V的先辈或父母结点因为一个结点至多只能被发现一次，因此它最多只能有-个父母结点相对根结点来说祖先和后裔关系的定义和通常一样：如果U处于树中从根S到结点V的路径中，那么U称为V的祖先，V是U的后裔BFS的运用对于应用广度优先搜索二阶魔方，很自然的想法就是将二阶的每个状态作为一个节点，如果两 个状态可以通过1步转化，那么就在这两个节点之间连一条边。

但是很容易想到，二阶在转动若干步之后必然会出现很多重复的转动，如果不判定是否重复，可以预想到会有 多少状态搜索了好多次为了解决重复的问题必须要判定当前搜索到的状态是否在之前已经 出现过，一个很简单的想法就是每次搜索到一个节点，都将此节点与之前所有搜索到的节 点进行一一比较即可满足题目要求转动方式的定义对于计算机解魔方这一问题，每个状态单独构成节点在描述表示二阶魔方的状态前，首先定义二阶魔方的每个面的称呼以及转动方式称呼，以方便之后的叙述面与转动的定义定义二阶魔方靠近自己的这面为F (Front)面，上面为U (Up)面，下面为D (Down)面，左边为L (Left)面，右面为R (Right)面，与F面对着的为B (Back) 面定义顺时针转动二阶魔方的某个面90度的动作的称呼与面的称呼相同，逆时针转动90度的称呼为顺时针转动的称呼后加上“’转动180度的称呼为顺时针的称呼后面加 上 “2”例：顺时针转动B面90度，记作：“B”；逆时针转动L面90度“L'”；转动R面180度：“R2”,转 动R面180度后再逆时针转动U面90度记为：“R2U'”以此类推无效的多余转动这时候我们发现，由于二阶魔方的对称性，同时转动“L‘ R”后的效果相当于整体转动 了二阶魔方，这个过程在搜索中是没有意义的(因为只要目标的魔方六面颜色一样即可， 至于是哪个面什么颜色我们不关心)。

所以为了简化搜索过程及数据规模，我们不妨省略 L,B,D三面的转动(L,L‘，L2,B,B' ,B2,D,D' ,D2),这样每个状态就可以有9种转动方法， 即：R,R' ,R2,U,U' ,U2,F,F' ,F2需要解决的问题总结一下，对于用广度优先搜索二阶魔方，主要是要解决以下几个问题：魔方的状态如何储存对于魔方这一抽象事物，在计算机中不可能直接模拟，需要通过建立一些类似状态数组来表示二阶魔方的每个状态，同时状态的储存要尽量节省计算机的空间，并且方便计算机进行存取魔方状态与状态之间如何迅速完成的转化由于用到了广度优先搜索算法，在搜索过程中，之前出现在搜索队列中的点如果直接按常规方式储存，必然会导致内存的大量浪费甚至系统无法承受，故可以仿效状态的贮存 方式，将状态对应的数字"压缩”储存在内存中很显然我们暂时只能知道魔方的转动对状 态的影响，而不能直接知道魔方的转动对数字的直接作用，所以在转动之前还需要将储存 的数字“解压”为相应的状态，再做转动如何快速有效的判断当前搜索状态之前是否被搜索过当搜索状态数达到一定规模后，魔方将出现很多重复的状态，如果不进行重复的判定，必然会出现相当多的无效节点，这不仅仅是对系统资源的浪费，同时也大量影响了程序的 执行效率。

第三个问题中隐含着一个同样关键的问题：搜索量很自然的知道，判定状态是否重叠这一问题的难度是与搜索量成正关系的，如果搜索量得到非常有效的控制，那么第三个问题的解决将会变得相对容易，同时广度优先搜索队列的 大小也可以得到有效的控制一个简单的解决方案问题解决方案如何储存魔方状态在这之前我们首先要确定魔方状态的表示，一个很自然的想法就是将每个面上每个颜 色块存储起来即可比如我们可以定义F面上的4个颜色块分别为：左上F11,右上F12,左下F21,右下F22,其他面以此类推根据上面的定义，每个状态，除了 L,B,D面夹着的三个颜色块，其 余的一共4*3+3*3=12+9=21个颜色块每个颜色块一共有6种可能的情况为了节省空间， 又由于计算机是2进制，不妨每3个bit来表示一个块的颜色，这样总共需要： 21*3=63bit,可令每个状态最终占用8各字节的空间即可达到表示的目的状态转移根据上述状态储存方案，很容易想到只要每次提取3个bit的空间，最后就得到了状态的表示，而在这一表示形式下，对于魔方的转动就变成了几个块之间的相互变换比如转了F,那对于F面上的块，就是一个F11<-F21<-F22<-F12<-F11的循环变换，在计算机实现起 来十分容易。

判重一一比较即可，对于队列，由于元素先后之间没有任何大小关系，只能通过一个个比较的方案来实现判重的目的这一方案虽然效率不高，但是在准确性方面可以得到很确定的 回答搜索量根据前面的介绍，二阶总状态数在610数量级，故搜索量应该也在这一数量级附近方案效率分析在这一方案下应用广度优先搜索解二阶魔方，根据问题4可知这一方案总共需要搜索 的状态数n约为：610左右，每次搜到第i个状态，都需要和前面已经搜索到的i-1个状态进行耗时为0(1) 一一对比判重，又由于转动的过程不需要复杂的解码，耗时也是0(1)的， 故最后的总时间复杂度为：(1)()211 2 12+ + +n- = nn- = On空间复杂度：由于没有应用外部空间，其额外复杂度为0(1) O对于6n = 10的数量级，很显然()2On已经超过了计算机能承受的范围搜索量方面的改进通过上面这个简单的策略的初步分析，我很快意识到，要用计算机实现高效解二阶魔 方，首要解决的就是问题3和问题4对于问题4,即搜索规模的控制，由于二阶状态数是给定的，如何才能并不搜索完所有状态，甚至只搜索少部分状态就得到解呢？对于魔方这一问题，很自然的就想到了双向 广度优先搜索算法，即可在保证答案正确性的前提下大大缩小搜索量。

双向广度优先搜索 广度优先搜索遵循从初始结点开始一层层扩展直到找到目标结点的搜索规则，它只能 较好地解决状态不是太多的情况，承受力很有限如果扩展结点较多，而目标结点又处在较 深层，采用前文叙述的广度搜索解题，搜索量巨大是可想而知的，往往就会出现内存空间 不够用的情况有些问题按照广度优先搜索法则扩展结点的规则，既适合顺序，也适合逆序，于是我们考虑在寻找目标结点或路径的搜索过程中，初始结点向目标结点和目标结点向初始结点 同时进行扩展一，直至在两个扩展方向上出现同一个子结点，搜索结束，这就是双向搜索 过程出现的这个同一子结点，我们称为相交点，如果确实存在一条从初始结点到目标结点 的最佳路径，那么按双向搜索进行搜索必然会在某层出现“相交”，即有相交点，初始结点一相交点一目标结点所形成的一条路径即是所求路径。