《算法设计与分析》课程设计任务书.doc

《《算法设计与分析》课程设计任务书.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、课程设计《算法设计与分析》课程设计任务书学院名称：数学与计算机学院专业：信息与计算科学专业年级：2007一、设计题目用回溯法求解一般哈密尔顿回路问题二、主要内容给出内存分类法的多种应用，给出这些应用对应的算法并编程实现。三、具体要求(1)给出各种分类法的求解算法;(2)编程实现各种分类法的算法;(3)对所写的每个算法给出时空复杂性分析。四、主要技术路线提示1、回溯法的主要思想是每次只构造解的一个分量，然后按照下面的方法来评估这个部分构造解。如果一个部分构造解可以进一步构造而不会违反问题的约束，我们就接受

2、对解的下一个分量所做的第一个合法选择。如果无法对下一个分量进行合法选择，就不必对剩下的任何分量再做任何选择了。在这种情况下，该算法进行回溯，把部分构造解的最后一个分量替换为他的下一个选择。2、设计回溯法的步骤(1)对所做的选择构造一棵所谓的状态空间数。(2)如果一个部分构造解仍然有可能导致一个完整解，我们说这个部分解在树中的相应结点是有希望的；否则，我们说他是没希望的。(3)一个回溯法的状态空间树是按照深度优先的方式来构造的。(4)最后，如果该算法找到了问题的一个完整解，它要么就停止了，要么继续查找其他

3、可能的解。3、课程设计哈密顿路径问题在上世纪七十年代初，终于被证明是“NP完备”的。据说具有这样性质的问题，难于找到一个有效的算法。实际上对于某些顶点数不到100的网络，利用现有最好的算法和计算机也需要比较荒唐的时间（比如几百年）才能确定其是否存在一条这样的路径。　　从图中的任意一点出发，路途中经过图中每一个结点当且仅当一次，则成为哈密顿回路。　　要满足两个条件：　　1.封闭的环　　2.是一个连通图，且图中任意两点可达　　经过图（有向图或无向图）中所有顶点一次且仅一次的通路称为哈密顿通路。　　经过图中所

4、有顶点一次且仅一次的回路称为哈密顿回路。　　具有哈密顿回路的图称为哈密顿图，具有哈密顿通路但不具有哈密顿回路的图称为半哈密顿图。　　平凡图是哈密顿图。4、针对算法实现，要求掌握算法的思想和原理，通过编程语言（VC、VB、Java等均可）实现算法。5、具体算法和方案可参考任务书后相关参考文献。五、进度安排1、第一周:分析题目的需求，设计抽象数据类型、构思算法、通过类的设计实现抽象数据类型并编写上机程序2、第二周完成程序开发，进行测试并分析结果，最后撰写课程设计报告六、完成后应上交的材料上交的成果的内容必须

5、由以下四个部分组成，缺一不可。1．上交源程序：学生按照课程设计的具体要求所开发的所有源程序（应该放到一个文件夹中）。2．上交程序的说明文件：（保存在.txt中），在说明文档中应该写明上交程序所在的目录，上交程序的主程序文件名，如果需要安装，要有程序的安装使用说明。3．课程设计报告电子文档：（保存在word文档中，文件名要求按照“学号姓名算法分析课设报告.doc”起名，如文件名为“200300109张三算法分析课设报告.doc”），按照课程设计的具体要求建立的功能模块，每个模块要求按照如下几个内容认真完成

6、：其中包括：（1）需求分析：在该部分中叙述每个模块的功能要求等。（2）概要设计在此说明每个部分的算法设计说明（可以是描述算法的流程图），每个程序中使用的存储结构设计说明（如果指定存储结构请写出该存储结构的定义。（3）详细设计各个算法实现的源程序，对每个题目要有相应的源程序（可以是一组源程序，每个功能模块采用不同的函数实现）。课程设计源程序要按照写程序的规则来编写。要结构清晰，重点函数的重点变量，重点功能部分要加上清晰的程序注释。（4）调试分析包括测试数据，测试输出的结果，时间复杂度分析，和每个模块设计和

7、调试时存在问题的思考（问题是哪些？问题如何解决？），算法的改进设想。（5）课设总结总结可以包括：课程设计过程的收获、遇到问题、遇到问题解决问题过程的思考、程序调试能力的思考、对算法设计与分析这门课程的思考、在课程设计过程中对《算法设计与分析》课程的认识等内容。4．课程设计报告打印稿。七、推荐参考资料教材：《算法设计与分析》宋文等编重庆大学出版社，2001。参考书：[1]《算法设计与分析》周培德电子工业出版社，2000。[2]《算法设计与分析》王晓东电子工业出版社，2004指导教师签名日期年月日系主任审核

8、日期年月日