数据结构课程设计报告模板--计科 (1)数据结构课程设计报告设计题目: $$$$$$$问题专业：计算机科学与技术班级：2班学生姓名：张文杰指导教师：201*年*月*日目录1.设计内容 (1)1.1问题描述 (1)1.2设计要求 (1)1.3开发环境 (1)1.4研究思路 (1)2.设计步骤 (5)2.1需求分析 (5)2.2概要设计 (5)2.3详细设计 (10)2.4调试分析 (13)2.5测试结果 (15)3.设计成果展示 (19)3.1用户手册 (19)3.2程序运行部分截图 (20)4.总结与心得体会 (21)附录 (22)1.设计内容1.1问题描述（给出你所选择的题目的要求描述）某售货员要到若干城市去销售商品，已知各城市之间的路程（或旅费）。
他要选定一条从驻地出发，经过每个城市一遍，最后回到驻地的路线，使总的路程（或旅费）最小。
本问题的关键词是：不重复遍历，路程最短，即程序应在给定的地图上给出一条路程最短的线路，使经过并且只经过要去的每个城市一次，最后回到驻地。
1.2设计要求（1）输入数据放到文件里，输入要测试的文件名，能输出最短路程及其路线。
（2）能用图形演示旅行商的最佳推销路线。
1.3开发环境本程序开发环境为 Visual Studio 20031.4研究思路对于“旅行商路线选择”这一问题，我们的思路如下：运行程序——调用用户所给标准地图（程序自带中国交通地图与山东省主要城市及周边省会地图）——选择要去的城市——通过坐标算出两城1市之间的距离存入内存——将城市连成一条回路——通过算法将回路优化——优化一定程度后停止——界面显示最优路线与旅行顺序我们程序的主要算法是遗传算法，其基本描述如下：遗传算法是模拟自然选择和生物进化的过程，以优胜劣汰的方式求解问题。
算法需要选择一种合适的编码方式表示解，并选择一种评价函数来计算每个解的适应值，适应值高的解可以更容易地被选中并进行交配，从而产生新的子代。
选择和交配的过程一直循环，同时以一定的概率进行变异，直到求得满意解或其它终止条件。
算法运行的过程具有很强的指向性，适合众多复杂问题的求解。
遗传算法的过程可以抽象为4大部分：初始化、选择算子、交配算子和变异算子。
初始化确定具体问题在遗传算法中的编码、群体大小、各种概率大小等参数；选择算子确定如何在群体中选择新的种群；交配算子使选出来的种群进行交配以模拟进化；变异算子使新的个体能够保持多样性。
旅行商问题规定了每个城市只能出现一次，因此编码有其特殊性，一般采用整数的编码方式，通过数字序列来表示城市的遍历次序。
采用整数编码方式的简单遗传算法（SGA）的交配策略通常是以单个整数为单位进行，可称为基于点的交配；为TSP设计的交配策略通常都会以边为单位进行，可称为基于边的交配。
1、简单遗传算法的流程如图22、适应度函数适应度函数必须能够配合选择方式有效区分子代的优劣，我们采用的方式是f=1/s ，其中s 是路径的总长度。
3、选择操作3实验采用了轮盘赌的选择方式，它是一种经典的 GA 选择方式，概率大个体在轮盘中占有更大的面积，更容易被选中。
4、变异操作变异操作是让遗传算法跳出局部最优的重要手段。
一般采用的变异操作是随机产生两个变异位，把这两个位的城市调换位置。
在一次变异中，选中的个体进行进行n/20（n为城市数目）次交换。
例：对序列 1 2 3 4 5 6 7 8执行 2 次交换，变异位分别 2 与 5，3 与 6，那么，一次交换后：1 5 3 4 2 6 7 8两次交换后：1 5 6 4 2 3 7 8。
5、优化搜索遗传算法一般采用的是2-opt 二段优化，这是一种简单的优化方案。
一次 2-opt表述如下：选择位置 a，b，尝试倒置ab间的所有路径，如果路径比原来短，则接受倒置，否则路径保持不变。
例如：1 2 3 4 5 6 7 8。
倒置 2，5 间路径，则变成 1 5 4 3 2 6 7 8。
在我们采用遗传算法的优化中，倒置操作一共进行n/10次尝试。
同时因为倒置较长的序列通常不会得到路径提升，所以控制倒置位置a，b 之间的差小于等于n /5。
由于我们的问题实际属于动态旅行商问题，我们提前做了两个假定：（1）旅行期间，城市间的交通都很发达，不存在因交通而耽误时间现象。
（2）在信息采样周期内，城市的规模与城市之间的距离等参数固定。
42.设计步骤2.1需求分析市场营销需要商家派遣人员到各个城市去调查市场状况和推销公司产品，为了节省开销和节约路途花费时间，就产生了旅行商到各个城市的顺序和最短路线选择问题。
基于以上问题，旅行商们需要的是一款能够直观反映所需到达城市的顺序以及最短路线的可视化应用程序，以供自己参考决策，选择最佳行程。
因此，我们的程序为了解决以上问题，采用了C++语言编程，其主要功能是：用可视化界面给用户提够所需到达城市的最短路线。
用户只需用鼠标和热键点击选择所需到达城市，然后通过程序运算，就可看到行程路线。
2.2概要设计针对主要功能，我们首先要设计可视化界面，然后在控件上添加事件过程，再编写代码。
1、程序中使用的主要变量x//点的横坐标y//点的纵坐标CitySites:Point *//城市序列RoomSize /./空间大小Comput //是否正在计算KillMsg//是否关闭计算DistanceM//距离矩阵DMSize//矩阵大小5BestIndex//最有序列CurrBestIndex//当前最有序列BestMark//最高分AVGMark//平均分GenNum//代数BestGen//最优代JumpCountDown//突变剩余次数JumpCount//突变次数TimeUsed//使用时间ProPath//当前路径2、使用的主要函数GetCityNum()//获取城市数量GetCitySite(int index)//获取城市地图中的某点Variant()//变异函数ThreadPro(pParam:LPVOID)//辅助线程ComputeDistanceMatrix()//计算距离矩阵DestroyDistanceMatrix()//销毁举例矩阵Mark(gene:GENE &)//打分函数QuadrangleOptimise(gene:GENE &)//四边形优化GetProPath()//获取当前路径GetStateDescription()// 获取当前状态GetStateSimpleDescription ()// 获取当前的简短状态StartCompute()//开始计算StopCommpute()//停止计算IsComputing()//是否正在计算6GetBestMark()//获取当前最高分GetAVGMark()//获取当前平均分WriteFile(filename:CString)//写入文件GetRoute()//获取当前最有路径ReadFile(filename:CString)//读取文件Clear()//清空Draw(pDC:CDC *,rect CRect,highlight:int,highlight2:int)//画图AddCity(x:double,y:double)//添加城市DeleteCity(index:int)//删除城市HitText(x:double,y:double,dx:double,dy:double)//点击测OnPaint();实现界面的初始化OnLButtonDown();//对鼠标做出的反应，实现选中点OnLButtonUp(UINT nFlags, CPoint point);//释放鼠标捕捉OnMouseMove(UINT nFlags, CPoint point);//对鼠标移动的反应OnKeyDown();//实现对键盘的反应，这里只处理用Shift+D删除点下面的函数实现下拉菜单地图里面的子菜单的反应：OnOpen();//实现对菜单栏“打开地图”的反应OnSave();//实现对菜单栏“保存地图”的反应OnRandom();//实现对菜单栏“随机生成”的反应OnDelete();//实现对菜单栏“删除城市”的反应OnClear();//实现对菜单栏“清空地图”的反应OnExit();//实现对菜单栏“退出”的反应下面函数实现计算功能：OnStartcomput();//实现对菜单栏“开始计算” 的反应OnStopcomput();//实现对菜单栏“停止运算”的反应下面的函数实现背景菜单的功能：OnSetbk();//实现对菜单栏“设置背景”的反应OnShowback();//实现对菜单栏“显示背景”的反应OnHelp();//实现对菜单栏“帮助的反应”OnTimer(UINT nIDEvent);//计时器，每隔一段时间做出的反应除了这三个类以外，还有像一些产生对话框需要的类，例如：RandCreateDlg等2、主程序运行界面3、程序结束界面2.3详细设计1、通过我们初步的分析，研究过旅行商的算法（包括蚁群算法，变异算法，神经网络算法等），决定使用变异算法，并进入详细设计阶段，详细设计阶段分为界面设计和代码设计，开始我们打算利用VB实现程序的，但是由于程序中大量的使用到了指针，使用VB不能满足程序的需要，我们选择了C++，虽然我们几个并不是很懂，但是由于我们中有几个已经接触过，所以我们也就拿了几本书，边学边做。
2、首先，我们的程序中的类有：1）CityMap类，因为这个类这是我们程序中最重要的一个类，里面包含了我们程序使用的绝大多数函数。
2）Point类，因为距离在平面图上的表示并不容易，我们选择了利用点坐标定义点，然后通过点坐标计算距离矩阵。
这就设计到了我们程序中最基本的一个类，Point类。
其中属性有x，y坐标，行为有求距离，以便于距离矩阵的求出。
3)TravellerDlg类，这个类是程序主界面的主要控制程序，对主界面的程序做出相应的反应，包括鼠标，包括，键盘，包括菜单的单击属性。
主要是用MFC实现，通过MFC来实现界面的布局。
主要方法有：3、主要函数解释1）变异函数：Variant，这是变异函数得来的原因，实现了有父代到子代的变异顺次交换：将i到j之间的点依次与m到n之间的点进行交换，交换函数如下：tmp = gdest.index[m];gdest.index[m] = gdest.index[n];gdest.index[n] = tmp；按块交换：将第i 块和第m 块交换，将第j 块和第m 块交换，每一块中含有的元素不定，每次都是随机生成。
用下面函数实现函数如下：memcpy(ptemp, gdest.index, n * sizeof(int));其中ptemp 为暂存区为目标区，gdest.index 表示原目标，n 表示要复制的长度。