数据结构课程设计报告模板--计科 (1)

《数据结构课程设计报告模板--计科 (1)》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、数据结构课程设计报告设计题目:$$$$$$$问题专业：计算机科学与技术班级：2班学生姓名：张文杰指导教师：201*年*月*日指导教师评语指导教师：年月日成绩评定学号姓名任务分工成绩目录1.设计内容11.1问题描述11.2设计要求11.3开发环境11.4研究思路12.设计步骤52.1需求分析52.2概要设计52.3详细设计92.4调试分析122.5测试结果143.设计成果展示173.1用户手册173.2程序运行部分截图184.总结与心得体会19附录21$$$$$$$问题1.设计内容1.1问题描述（给出你所选择的题目的要

2、求描述）某售货员要到若干城市去销售商品，已知各城市之间的路程（或旅费）。他要选定一条从驻地出发，经过每个城市一遍，最后回到驻地的路线，使总的路程（或旅费）最小。本问题的关键词是：不重复遍历，路程最短，即程序应在给定的地图上给出一条路程最短的线路，使经过并且只经过要去的每个城市一次，最后回到驻地。1.2设计要求（1）输入数据放到文件里，输入要测试的文件名，能输出最短路程及其路线。（2）能用图形演示旅行商的最佳推销路线。1.3开发环境本程序开发环境为VisualStudio20031.4研究思路对于“旅行商路线选择”这一

3、问题，我们的思路如下：运行程序——调用用户所给标准地图（程序自带中国交通地图与山东省主要城市及周边省会地图）——选择要去的城市——通过坐标算出两城市之间的距离存入内存——将城市连成一条回路——通过算法将回路优化4$$$$$$$问题——优化一定程度后停止——界面显示最优路线与旅行顺序我们程序的主要算法是遗传算法，其基本描述如下：遗传算法是模拟自然选择和生物进化的过程，以优胜劣汰的方式求解问题。算法需要选择一种合适的编码方式表示解，并选择一种评价函数来计算每个解的适应值，适应值高的解可以更容易地被选中并进行交配，从而产生

4、新的子代。选择和交配的过程一直循环，同时以一定的概率进行变异，直到求得满意解或其它终止条件。算法运行的过程具有很强的指向性，适合众多复杂问题的求解。遗传算法的过程可以抽象为4大部分：初始化、选择算子、交配算子和变异算子。初始化确定具体问题在遗传算法中的编码、群体大小、各种概率大小等参数；选择算子确定如何在群体中选择新的种群；交配算子使选出来的种群进行交配以模拟进化；变异算子使新的个体能够保持多样性。旅行商问题规定了每个城市只能出现一次，因此编码有其特殊性，一般采用整数的编码方式，通过数字序列来表示城市的遍历次序。采用

5、整数编码方式的简单遗传算法（SGA）的交配策略通常是以单个整数为单位进行，可称为基于点的交配；为TSP设计的交配策略通常都会以边为单位进行，可称为基于边的交配。1、简单遗传算法的流程如图4$$$$$$$问题随机生成初始种群计算适应值并保存最优解交配变异优化（可省略）计算适应值并保存最优解选择新子代是否满足终止条件结束否是2、适应度函数适应度函数必须能够配合选择方式有效区分子代的优劣，我们采用的方式是f=1/s，其中s是路径的总长度。3、选择操作实验采用了轮盘赌的选择方式，它是一种经典的GA选4$$$$$$$问题择方式

6、，概率大个体在轮盘中占有更大的面积，更容易被选中。4、变异操作变异操作是让遗传算法跳出局部最优的重要手段。一般采用的变异操作是随机产生两个变异位，把这两个位的城市调换位置。在一次变异中，选中的个体进行进行n/20（n为城市数目）次交换。例：对序列12345678执行2次交换，变异位分别2与5，3与6，那么，一次交换后：15342678两次交换后：15642378。5、优化搜索遗传算法一般采用的是2-opt二段优化，这是一种简单的优化方案。一次2-opt表述如下：选择位置a，b，尝试倒置ab间的所有路径，如果路径比原来

7、短，则接受倒置，否则路径保持不变。例如：12345678。倒置2，5间路径，则变成15432678。在我们采用遗传算法的优化中，倒置操作一共进行n/10次尝试。同时因为倒置较长的序列通常不会得到路径提升，所以控制倒置位置a，b之间的差小于等于n/5。由于我们的问题实际属于动态旅行商问题，我们提前做了两个假定：（1）旅行期间，城市间的交通都很发达，不存在因交通而耽误时间现象。（2）在信息采样周期内，城市的规模与城市之间的距离等参数固定。4$$$$$$$问题2.设计步骤2.1需求分析市场营销需要商家派遣人员到各个城市去调

8、查市场状况和推销公司产品，为了节省开销和节约路途花费时间，就产生了旅行商到各个城市的顺序和最短路线选择问题。基于以上问题，旅行商们需要的是一款能够直观反映所需到达城市的顺序以及最短路线的可视化应用程序，以供自己参考决策，选择最佳行程。因此，我们的程序为了解决以上问题，采用了C++语言编程，其主要功能是：用可视化界面给用户提够所需到达城市的最短路