数据结构课程设计汇本案报告

数据结构课程设计汇本案报告

ID:39782614

大小:302.50 KB

页数:16页

时间:2019-07-11

数据结构课程设计汇本案报告_第1页
数据结构课程设计汇本案报告_第2页
数据结构课程设计汇本案报告_第3页
数据结构课程设计汇本案报告_第4页
数据结构课程设计汇本案报告_第5页
资源描述:

《数据结构课程设计汇本案报告》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库

1、数据结构课程设计设计说明书TSP问题起止日期:2016年6月27日至2016年7月1日学生姓名班级学号成绩指导教师(签字)2016年7月1日目录第1章需求分析11.1简介11.2系统的开发背景11.3研究现状1第2章概要设计22.1系统开发环境和技术介绍22.2系统需求分析22.2.1总体功能分析22.2.2核心功能分析3第3章详细设计43.1系统开发流程43.2系统模块设计43.3系统结构63.2系统流程图6第4章调试分析74.1程序逻辑调试74.2系统界面调试8第5章测试结果95.1测试环境95.2输入输出测试项目95.3测试结果10结论11参考文献11附录12第1章需求分析1.1简介旅

2、行商问题,即TSP问题(TravellingSalesmanProblem)又译为旅行推销员问题、货郎担问题,是数学领域中著名问题之一。假设有一个旅行商人要拜访n个城市,他必须选择所要走的路径,路径的限制是每个城市只能拜访一次,而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。1.2系统的开发背景TSP的历史很久,最早的描述是1759年欧拉研究的骑士周游问题,即对于国际象棋棋盘中的64个方格,走访64个方格一次且仅一次,并且最终返回到起始点。TSP由美国RAND公司于1948年引入,该公司的声誉以及线形规划这一新方法的出现使得TSP成为一个知名且流行的问题

3、。1.3研究现状TSP问题是一个组合优化问题。该问题可以被证明具有NP计算复杂性。因此,任何能使该问题的求解得以简化的方法,都将受到高度的评价和关注。旅行推销员问题是图论中最著名的问题之一,即“已给一个n个点的完全图,每条边都有一个长度,求总长度最短的经过每个顶点正好一次的封闭回路”。Edmonds,Cook和Karp等人发现,这批难题有一个值得注意的性质,对其中一个问题存在有效算法时,每个问题都会有有效算法。迄今为止,这类问题中没有一个找到有效算法。倾向于接受NP完全问题(NP-Complete或NPC)和NP难题(NP-Hard或NPH)不存在有效算法这一猜想,认为这类问题的大型实例不能

4、用精确算法求解,必须寻求这类问题的有效的近似算法。第2章概要设计2.1系统开发环境和技术介绍MicrosoftVisualC++6.0不仅是一个C++编译器,而且是一个基于Windows操作系统的可视化集成开发环境(IDE)。VisualC++6.0由许多组件组成,包括编辑器、调试器以及程序向导AppWizard、类向导ClassWizard等开发工具。这些组件通过一个名为DeveloperStudio的组件集成为和谐的开发环境。2.2系统需求分析2.2.1总体功能分析TSP问题最容易想到的也肯定能得到最佳解的算法是穷举法,即考虑所有可能的旅行路线,从中选择最佳的一条。但是用穷举法求解TSP

5、问题的时间复杂度为Ο(n!),当n大到一定程度后是不可解的。于TSP问题,一个旅行家要穿过多个城市,已知城市个数,以及城市间距,每个城市经历且只经历一次,求出最短路径解和最短路径长度。本实验只要求近似解,可以采用贪心法求解:任意选择某个城市作为出发点,然后前往最近的未访问的城市,直到所有的城市都被访问并且仅被访问一次,最后返回到出发点。输入城市数目N为正整数,城市间距离按邻接矩阵方式排列输入,最小值为0,共有N*N个数值;输出最优解和最优值。2.2.2核心功能分析以下是核心功能代码分析:贪心算法排序:为了解决问题,需要寻找一个构成解的候选对象集合,它可以优化目标函数,贪婪算法一步一步的进行。

6、起初,算法选出的候选对象的集合为空。接下来的每一步中,根据选择函数,算法从剩余候选对象中选出最有希望构成解的对象。如果集合中加上该对象后不可行,那么该对象就被丢弃并不再考虑;否则就加到集合里。每一次都扩充集合,并检查该集合是否构成解。如果贪婪算法正确工作,那么找到的第一个解通常是最优的。代码如下图所示:第3章详细设计3.1系统开发流程1、上网查找与题目相关的资料,并重点阅读课本上的相关知识。2、对问题进行抽象,得到描述问题的算法,编写出程序。3、设计完整的程序进行演示。4、对设计进行总结分析。3.2系统模块设计功能模块:主函数:int main() 主要由以下函数构成: intDistanc

7、eMin(int*p):搜索得到与当前距离最近的城市,返回当前距离最短节点对应下标voidCreatArry():动态创建标记数组voidCreateMatrix():动态创建矩阵voidTSP():贪心算法排序3.3系统流程图第4章调试分析4.1程序逻辑调试由于以下程序中定义CreateMatrix时忘记加括号导致程序错误。4.2系统界面调试请输入城市数:输入城市间距离的邻接矩阵:输入一个邻接矩阵02030

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。