【精品】毕业论文张腾

《【精品】毕业论文张腾》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、学号14082200137基于广搜解Rubick魔方（2012届）课题名称:基于广搜解Rubick魔方姓名：张腾学号：14082200137专业：信息工程所在班级:电信08-2BF指导教师：姓名：张振时间：二零一二年六月一日作为主流的动态语言，python不仅简单易学、移植性好，而且拥有强大丰富的库的支持。此外,python强大的可扩展性,让开发人员既可以非常容易地利用c/c++编写python的扩展模块，还能将python嵌入到C/C++程序中，为自己的系统添加动态扩展和动态编程的能力。通过基于广搜Rubik魔方来更深入的了解这门语

2、言。本文对二阶魔方进行初步介绍、分析需要解决的问题并给出了一个简单的搜索算法后，通过深入分析问题的本质，从减少搜索量、优化判重算法、节省内存空间、消除冗余等方面分别对程序进行了一步步的优化，同吋从代码的紧凑性方面进行深入地分析了算法复杂度前所隐含的系数，并针对这方面进行了有效的系数优化，最终得到了一个平均每秒能够解数百个二阶魔方的高效算法。关键词双向BFS,二叉排序树，哈希表，魔方的表示方式，初始化打表，位置与状态分治口录摘要I关键词1目录1第一章绪论61.1二阶魔方介绍61.2广度优先搜索61.3BFS的运用6第二章文本远程算法简介

3、82.1什么是文本远程纠错82.2逐行文本比较82.3最大匹配率162.4二分查找纠错162.5影响文本纠错算法的因索17第三章系统开发工具183.1开发T具python简介183.2python的基木形式183.2.1缩进183.2.2语句和控制流18323函数193.2.4面向对象编程19第四章哈希算法204.1哈希的概念204.2哈希的优越性204.3字符串哈希算法简介204.4滚动哈希算法234.5哈希算法的应用23第五章两种文本纠错算法的python实现255.1逐行比较纠错算法255.2二分查找纠错算法26第六章结论与展望

4、28致谢29参考文献30附录31问题提出：对于一个给定的打乱的二阶魔方，通过计算机搜索的方法，问该魔方至少需要转动几次（转动一个而90度，180度，270度均认为是一次转动）才可以最终达到还原的状态？二阶魔方介绍：二阶魔方的英文官方名字叫做PocketRubik'sCube或MiniCube,中文直译叫做“口袋魔方”。它每个边有两个方块。二阶魔方的总变化数为3674160或者大约63.67X10o二阶魔方（PocketCube）乂称口袋魔方、迷你魔方、小魔方、冰块魔方，为2X2X2的立方体结构。身只有8个角块，没有其他结构的方块。基木

5、思想：由于题H要求的是要求出二阶魔方从某个打乱状态到述原态的最短路径，所以通常用来求某个解的递归算法——深度优先算法并不可行，所以在解决这个问题的过程屮我决定采用广度优先搜索。（BFS）广度优先搜索宽度优先搜索算法（又称广度优先搜索）是最简便的图的搜索算法乞一，这一算法也是很多重要的图的算法的原型。Dijkstra单源最短路径算法和Prim最小生成树算法都采用了和宽度优先搜索类似的思想。已知图G=（V,E）和一个源顶点s,宽度优先搜索以一种系统的方式探寻G的边，从而“发现”s所能到达的所有顶点，并计算s到所有这些顶点的距离（最少边数）

6、，该算法同时能生成一•棵根为s且包括所有可达顶点的宽度优先树。对从s可达的任意顶点v,宽度优先树中从s到v的路径对应于图G中从s到v的最矩路径，即包含最小边数的路径。该算法有向图和无向图同样适用。Z所以称Z为宽度优先算法，是因为算法口始至终一直通过已找到和末找到顶点Z间的边界向外扩展，就是说，算法首先搜索和s距离为k的所有顶点，然示再去搜索和S距离为k+1的其他顶点。为了保持搜索的轨迹，宽度优先搜索为每个顶点着色：白色、灰色或黑色。算法开始前所有顶点都是白色，随着搜索的进行，各顶点会逐渐变成灰色，然示成为黑色。在搜索中第一次碰到一顶点

7、吋，我们说该顶点被发现，此吋该顶点变为非口色顶点。因此，灰色和黑色顶点都已被发现，但是，宽度优先搜索算法对它们加以区分以保证搜索以宽度优先的方式执行。若（u,v）Ee且顶点u为黑色，那么顶点v耍么是灰色，耍么是黑色，就是说，所有利黑色顶点邻接的顶点都已被发现。灰色顶点可以与一些口色顶点相邻接，它们代表着已找到和术找到顶点Z间的边界。在宽度优先搜索过程屮建立了一棵宽度优先树，起始时只包含根节点，即源顶点s.在扫描已发现顶点U的邻接表的过程中每发现一个白色顶点V,该顶点V及边(u,v)就被添加到树屮。在宽度优先树屮，我们称结点U是结点V的

8、先辈或父母结点。因为一个结点至多只能被发现一次，因此它最多只能有-个父母结点。相对根结点来说祖先和后裔关系的定义和通常一样：如果U处于树屮从根S到结点V的路径屮，那么U称为V的祖先，V是U的示裔。BFS的运用对于应用广度