毕业论文 张腾

《毕业论文 张腾》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

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

3、…I目录………………………………………………………………………………………………...1第一章绪论………………………………………………………………………………………..61.1二阶魔方介绍……………………………………………………………………….………61.2广度优先搜索………………………………………………………………………….…….61.3BFS的运用………………………………………………………………………………......6第二章文本远程算法简介82.1什么是文本远程纠错82.2逐行文本比较82.3最大匹配率162.4二分查找纠错162.5影响文本纠错算法的因素………………………

4、………………………………………….17第三章系统开发工具……………………………………………………………………….........…..183.1开发工具python简介………….......………………………………………………………183.2python的基本形式………………………………………………………………………..…183.2.1缩进...........183.2.2语句和控制流183.2.3函数193.2.4面向对象编程19第四章哈希算法...................................................................

5、.......……….…………………...........204.1哈希的概念…....………………………………………………………………..…….......204.2哈希的优越性…..………………………......…………………………………………........204.3字符串哈希算法简介………………………………………………....................….……...204.4滚动哈希算法....234.5哈希算法的应用23第五章两种文本纠错算法的python实现…………………………………………..255.1逐行比较纠错算法…………………………………………………………

6、……………….255.2二分查找纠错算法……………………………………………………………………….....26第六章结论与展望.........................................................................……….…………………..........28致谢………………………………………………………………………………..................................29参考文献………………………………………………………………………....................................

7、...30附录……………………………………………………………………………………………………3119问题提出：对于一个给定的打乱的二阶魔方，通过计算机搜索的方法，问该魔方至少需要转动几次（转动一个面90度，180度，270度均认为是一次转动）才可以最终达到还原的状态？二阶魔方介绍：二阶魔方的英文官方名字叫做PocketRubik'sCube或MiniCube，中文直译叫做“口袋魔方”。它每个边有两个方块。二阶魔方的总变化数为3674160或者大约63.67×10。二阶魔方（Pock