数据结构课程设计报告模板--计科 (1)
数 据 结 构
课程设计报告
设计题目: $$$$$$$问题
专 业： 计算机科学与技术 班 级： 2班 学生姓名：张文杰
指导教师：
201*年*月*日
目 录
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
1.1问题描述 .................................................................................................... 1
附 录 ................................................................................................ 22
$$$$$$$问题 1.设计内容
1.1问题描述 （给出你所选择的题目的要求描述）
某售货员要到若干城市去销售商品，已知各城市之间的路程（或旅费）。他要选定一条从驻地出发，经过每个城市一遍，最后回到驻地的路线，使总的路程（或旅费）最小。
本问题的关键词是：不重复遍历，路程最短，即程序应在给定的地图上给出一条路程最短的线路，使经过并且只经过要去的每个城市一次，最后回到驻地。
1.2设计要求
（1）输入数据放到文件里，输入要测试的文件名，能输出最短路程及其路线。
（2）能用图形演示旅行商的最佳推销路线。
1.3开发环境
本程序开发环境为 Visual Studio 2003
1.4研究思路
对于“旅行商路线选择”这一问题，我们的思路如下：
运行程序——调用用户所给标准地图（程序自带中国交通地图与山东省主要城市及周边省会地图）——选择要去的城市——通过坐标算出两城
1
$$$$$$$问题 市之间的距离存入内存——将城市连成一条回路——通过算法将回路优化——优化一定程度后停止——界面显示最优路线与旅行顺序
我们程序的主要算法是遗传算法，其基本描述如下：
遗传算法是模拟自然选择和生物进化的过程，以优胜劣汰的方式求解问题。算法需要选择一种合适的编码方式表示解，并选择一种评价函数来计算每个解的适应值，适应值高的解可以更容易地被选中并进行交配，从而产生新的子代。选择和交配的过程一直循环，同时以一定的概率进行变异，直到求得满意解或其它终止条件。算法运行的过程具有很强的指向性，适合众多复杂问题的求解。
遗传算法的过程可以抽象为4大部分：初始化、选择算子、交配算子和变异算子。初始化确定具体问题在遗传算法中的编码、群体大小、各种概率大小等参数；选择算子确定如何在群体中选择新的种群；交配算子使选出来的种群进行交配以模拟进化；变异算子使新的个体能够保持多样性。
旅行商问题规定了每个城市只能出现一次，因此编码有其特殊性，一般采用整数的编码方式，通过数字序列来表示城市的遍历次序。采用整数编码方式的简单遗传算法（SGA）的交配策略通常是以单个整数为单位进行，可称为基于点的交配；为TSP设计的交配策略通常都会以边为单位进行，可称为基于边的交配。
1、简单遗传算法的流程如图
2
$$$$$$$问题 随机生成初始种群 计算适应值并保存最优解 交配 变异 优化（可省略） 计算适应值并保存最优解 否 选择新子代 是否满足终止条件 是 结束
2、适应度函数
适应度函数必须能够配合选择方式有效区分子代的优劣，我们采用
的方式是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）在信息采样周期内，城市的规模与城市之间的距离等参数固定。
4
$$$$$$$问题 2.设计步骤
2.1需求分析
市场营销需要商家派遣人员到各个城市去调查市场状况和推销公司产品，为了节省开销和节约路途花费时间，就产生了旅行商到各个城市的顺序和最短路线选择问题。
基于以上问题，旅行商们需要的是一款能够直观反映所需到达城市的顺序以及最短路线的可视化应用程序，以供自己参考决策，选择最佳行程。
因此，我们的程序为了解决以上问题，采用了C++语言编程，其主要功能是：用可视化界面给用户提够所需到达城市的最短路线。用户只需用鼠标和热键点击选择所需到达城市，然后通过程序运算，就可看到行程路线。
2.2概要设计
针对主要功能，我们首先要设计可视化界面，然后在控件上添加事件过程，再编写代码。
1、 程序中使用的主要变量
x//点的横坐标 y//点的纵坐标
CitySites:Point *//城市序列 RoomSize /./空间大小 Comput //是否正在计算 KillMsg//是否关闭计算 DistanceM//距离矩阵 DMSize//矩阵大小
5
$$$$$$$问题 BestIndex//最有序列
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()//是否正在计算
6
$$$$$$$问题 GetBestMark()//获取当前最高分 GetAVGMark()//获取当前平均分 WriteFile(filename:CString)//写入文件 GetRoute()//获取当前最有路径 ReadFile(filename:CString)//读取文件 Clear()//清空 Draw(pDC:CDC
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删除点
下面的函数实现下拉菜单地图里面的子菜单的反应：
*,rect
7
$$$$$$$问题
OnOpen();//实现对菜单栏“打开地图”的反应 OnSave();//实现对菜单栏“保存地图”的反应 OnRandom();//实现对菜单栏“随机生成”的反应 OnDelete();//实现对菜单栏“删除城市”的反应 OnClear();//实现对菜单栏“清空地图”的反应 OnExit();//实现对菜单栏“退出”的反应 下面函数实现计算功能：
OnStartcomput();//实现对菜单栏“开始计算” 的反应
8
$$$$$$$问题
OnStopcomput();//实现对菜单栏“停止运算”的反应 下面的函数实现背景菜单的功能：
OnSetbk();//实现对菜单栏“设置背景”的反应 OnShowback();//实现对菜单栏“显示背景”的反应 OnHelp();//实现对菜单栏“帮助的反应”
OnTimer(UINT nIDEvent);//计时器，每隔一段时间做出的反应
除了这三个类以外，还有像一些产生对话框需要的类，例如：RandCreateDlg等
2、 主程序运行界面
9
$$$$$$$问题
3、 程序结束界面
2.3详细设计
1、通过我们初步的分析，研究过旅行商的算法（包括蚁群算法，变异算法，神经网络算法等），决定使用变异算法，并进入详细设计阶段，详细设计阶段分为界面设计和代码设计，开始我们打算利用VB实现程序的，
10
$$$$$$$问题 但是由于程序中大量的使用到了指针，使用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；
11
$$$$$$$问题
…i …j …………m …n … 按块交换：将第i块和第m块交换，将第j块和第m块交换，每一块中含有的元素不定，每次都是随机生成。用下面函数实现函数如下：
memcpy(ptemp, gdest.index, n * sizeof(int));其中ptemp为暂存区为目标区，gdest.index表示原目标，n表示要复制的长度。详细代码见附录。
…i j …………m n … 2）距离矩阵的计算函数，ComputeDistanceMatrix()，根据点坐标，求得距离矩阵，便于计算使用。由于距离问题的特殊性，其距离矩阵为一个对称矩阵，且对角线上的都为0。所以生成的矩阵格式如下：
(1,(2,(3,(4,(5,(2,(3,(4,(5,(3,(4,(5,12
(4,(5,(5,
$$$$$$$问题 3）// 四边形优化，此函数主要实现了图的每次优化，为一个调整函数。
d 0
d 1 d 2
d 3
通过移动线，构造平行四边形，然后通过钝角的证明，利用原理两边之和等于第三边上的中线的两倍，则该三角形为直角三角形，如果d0 + d2 > d1 + d3，则形成的角比为锐角；如果是对钝角，则说明该四边形不用优化，如果不是则将该四边形进行优化，因为要构成一个闭合的最短回路则要是所有的这些构成整个环路的的这些四边形都是钝角。
2.4调试分析
1、此程序由于设计到的问题比较繁琐，开始是我们打算使用中国邮路的算法进行求解，但是由于那个算法对于数量较大时效率太低，我们选择了变异算法，当然程序的复杂度也大大的增加。又由于我们的程序使用MFC来实现，而且我们以前也都没有接触过MFC，只是对C++的语法有所了解，但是经过我们小组的努力，边学边用，并借助网络，最终将我们的程序跑通，当然我们的程序还有很多的问题，但是由于时间而且我们的学到的东西有限，程序也就能够运行到现在的情况。
13
$$$$$$$问题 2、程序的调试过程中我们也遇到了好多好多的问题，有的问题出现了以后我们从网上几乎查遍了所有的比较有影响力的论坛，也问了不少的这方面的朋友。当然大部分的问题我们能够通过这种方式解决，有些不能够得到解决的问题我们也采取了其他的方式解决了一部分问题。由于时间的限制还没有解决的问题，我们也一定会随着我们知识的增长去逐渐的完善这个问题。
3、再就是在这次的课程设计过程中，学会了利用专业的调试工具进行分析，这也能很快的帮我们解决问题。还有就是调试并不仅仅是一个最后测试的问题，而是伴随着程序开发的整个过程，边写边调，每写完一个过程就该调试一下，否则最后到所有的程序结束在进行调试，调试过程将变的异常复杂。
4、我们程序调试过程中也发现了一定的问题，比如说线的粗细问题，但是MFC提供的函数并不能满足需要，不能实现线粗细的调整，由于现在时间已经不允许，这个我们只能放到以后进行更改。再就是程序路径的显示，但城市数目过多时，由于路径只能显示在一行中，后面的显示不出来。现在只能最多完整的显示28个城市的标号。这个我们的写程序的队员也了解到这个问题，但是这个的实现在c++中确实让我们很为难，他并不像Java中的变量的处理那么简单。但是这个肯定能够解决，这个我们也会选择一中更完整的方式去实现这个功能，我们将在以后的程序中加上滚动条，这样不仅能够实现换行，还能够存放更多的层。现在的解决方案可以实现的就是写入文件当中。通过我们测试我们测试自己的程序，发现了太多的问题，用起来是那么的粗糙，跟那些真正的好程序差距还太远，但是通过这次的课程设计，使我们了解了MFC的开发过程以及运行的调用过程，这也使我们更多的去了解MFC，并进一步开发一些有一定价值的程序。 5、对于我们程序由输入点坐标带来的距离计算问题，可能会给程序的效率
14
$$$$$$$问题
带来一定的影响，由于我们这个程序是在每次运行的时候调用距离矩阵函数计算距离矩阵，这在数据量和使用量较大的情况下，会给服务器带来很大的负担。所以我们的程序还可以做一下的改进，在真正的实际应用过程中不可能是每次都是随机的生成点，而是在数据库中调用预先存入的点，这样我们就可以根据预先存入的点，通过调用矩阵函数将距离矩阵求出存入数据库，再次调用的时候可以直接调用数据库里的距离矩阵，从而提高程序的运行效率。
2.5测试结果
（1）在“地图”菜单中打开“随机生成”，输入随机数 n=100
（2）单击“确定”并产生随机点，并生成一个初始环路。
15
$$$$$$$问题
(3)单击“计算”菜单中的“开机计算”，开始遗传迭代，并产生初始最优解。
（4）经过3394代，4次灾变数，基本达到了最优解，并保存。
16
$$$$$$$问题
（5）下面是n=66的最优解。
17
$$$$$$$问题
（6）如果没有产生随机数就开始运行的，程序会报错。如下：
18
$$$$$$$问题 3.设计成果展示
3.1用户手册
1、运行环境：WindowsXp/Windows2003/Windows2000/等。
2、执行文件：Traveller.exe
3、用户界面：可视化面向用户的界面，用鼠标和键盘热键操作，容易理解，简单易上手。 4、操作过程：
A、打开名称为“Traveller.exe”的可执行文件（用鼠标左键双击图标或用右键单击图标并在下拉菜单中选择“打开”）；
B、然后根据自己的需要可以按住鼠标添加自己需要的点，也可以使用地图选项卡中的自动生成生成点，这里可以根据自己的要求设置生成点的个数。
C、点击菜单栏的计算里面的开始计算，程序开始运行，当程序运行到自己满意的程度，可以点击计算里面的停止计算，此时在主窗口的下方给出最优路线。
D、程序还可以根据自己的需要添加背景图片。 5、其他功能实现：
A、鼠标单击可以选中点
B、按住Shift键单击鼠标，如果是点中某个点，则选中该点，继续按住鼠标拖放可以移动点。如果是没有击中任何点，则新建一个点。 C、按住Shift键，然后按住键盘上的D键，可以实现对选中点的删除。
D、可以使用此程序的菜单栏地图中的随机生成功能随机的生成点，
19
$$$$$$$问题
并可以限定生成点的数量。
3.2程序运行部分截图
关键程序截图： 起始图：
终止图：
20
$$$$$$$问题 4.总结与心得体会
1、主要说明设计完成后的总结与思考，完成任务情况，收获，意见和建议等。
2、如果是小组报告，每个成员需要分别进行详细的总结和心得体会，且需要先详细说明本人所做的具体工作及任务完成情况。（小组中有几人，这个部分写几份！！！）
21
$$$$$$$问题 附 录
一、Variant的关键代码如下： // 变异函数
void CCityMap::Variant(GENE & gsource, GENE & gdest, int * ptemp, int size, int varate) {
static int i;
static int j, k, l, n, m; static int tmp;
memcpy(gdest.index, gsource.index, sizeof(int) * size); for(i = 0; i < varate; i++) {
switch(rand() % 2) {
case 0:
// 逆序变异，将两个数之间的数进行互换，一个顺序逆转 {
j = rand() % size; k = rand() % size; if(j == k) {
k = (k + 1) % size; }
if(j > k) {
k += size;
//for(l = j; l < j + k - l; l++) for(l = j; l < (j + k) / 2 + 1; l++) {
n = (j + k - l) % size; m = l % size;
tmp = gdest.index[m];
gdest.index[m] = gdest.index[n]; gdest.index[n] = tmp; } }
22
$$$$$$$问题 else {
for(l = j; l < (j + k) / 2 + 1; l++) {
tmp = gdest.index[l];
gdest.index[l] = gdest.index[j + k - l]; gdest.index[j + k - l] = tmp; } } }
break; case 1:
// 转移变异 {
j = rand() % size;
k = rand() % MAX_TRANS_NUM; if(k == 0) {
k = 1; }
l = rand() % (size - k) + 1;
n = (j + k) % size + l > size ? size - (j + k) % size : l;
memcpy(ptemp, gdest.index + (j + k) % size, n * sizeof(int));
if(n < l) {
memcpy(ptemp + n, gdest.index, (l - n) * sizeof(int)); }
n = j + k > size ? size - j : k;
memcpy(ptemp + l, gdest.index + j, n * sizeof(int)); if(n < k) {
memcpy(ptemp + l + n, gdest.index, (k - n) * sizeof(int));
}
m = k + l;
n = j + m > size ? size - j :m;
memcpy(gdest.index + j, ptemp, n * sizeof(int));
23
$$$$$$$问题 if(n < m) {
memcpy(gdest.index, ptemp + n, (m - n) * sizeof(int));
} }
break; default: break; } } }
二、ComputeDistanceMatrix的关键代码如下：
// 计算距离矩阵
void CCityMap::ComputeDistanceMatrix() {
int i, j;
this->DestroyDistanceMatrix(); // 创建存储空间
this->DMSize = this->CityNum;
this->DistanceM = new double * [DMSize]; DistanceM[0] = NULL;
for(i = 1; i < this->DMSize; i++) {
this->DistanceM[i] = new double[i]; }
// 计算距离
for(i = 1; i < DMSize; i++) {
for(j = 0; j < i; j++) {
DistanceM[i][j] = CitySites[i].Distance(this->CitySites[j]); } } }
三、QuadrangleOptimise的关键代码如下： // 四边形优化
24
$$$$$$$问题 void CCityMap::QuadrangleOptimise(GENE & gene) {
if(this->CityNum < 3) {
return; }
static int i, tmp; //change说明该四边形做出了优化 static bool change;
static double d0, d1, d2, d3; static int count; count = 0; do {
change = false; d0 = this->CitySites[gene.index[0]].Distance(this->CitySites[gene.index[CityNum - 1]]);
d1 = this->CitySites[gene.index[1]].Distance(this->CitySites[gene.index[CityNum - 1]]);
// 寻找钝角
for(i = 1; i < this->CityNum - 1; i++) {
d2 = this->CitySites[gene.index[i]].Distance(this->CitySites[gene.index[i + 1]]); d3 = this->CitySites[gene.index[i - 1]].Distance(this->CitySites[gene.index[i + 1]]); if(d0 + d2 > d1 + d3) {
// 交换公共点顺序 tmp = gene.index[i];
gene.index[i] = gene.index[i - 1]; gene.index[i - 1] = tmp; change = true; }
d0 = this->CitySites[gene.index[i]].Distance( this->CitySites[gene.index[i - 1]]);
25
$$$$$$$问题 d1 = d3; }
count++; if(count > 5) {
break; } }
while(change); this->Mark(gene); }……
26
因篇幅问题不能全部显示，请点此查看更多更全内容