数据结构专业课程设计方案报告模板计科.doc

数 据 结 构

课程设计汇报

设计题目: $$$$$$$问题

专 业： 计算机科学和技术
班 级： 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具体设计 9
2.4调试分析 12
2.5测试结果 14
3.设计结果展示 17
3.1用户手册 17
3.2程序运行部分截图 18
4.总结和心得体会 19
附 录 21

1.设计内容
1.1问题描述 （给出你所选择题目标要求描述）
某售货员要到若干城市去销售商品，已知各城市之间旅程（或旅费）。她要选定一条从驻地出发，经过每个城市一遍，最终回到驻地路线，使总旅程（或旅费）最小。
本问题关键词是：不反复遍历，旅程最短，即程序应在给定地图上给出一条旅程最短线路，使经过而且只经过要去每个城市一次，最终回到驻地。

1.2设计要求
（1）输入数据放到文件里，输入要测试文件名，能输出最短旅程及其路线。
（2）能用图形演示旅行商最好推销路线。

1.3开发环境
本程序开发环境为 Visual Studio

1.4研究思绪
对于“旅行商路线选择”这一问题，我们思绪以下：
运行程序——调用用户所给标准地图（程序自带中国交通地图和山东省关键城市及周围省会地图）——选择要去城市——经过坐标算出两城市之间距离存入内存——将城市连成一条回路——经过算法将回路优化——优化一定程度后停止——界面显示最优路线和旅行次序
我们程序关键算法是遗传算法，其基础描述以下：
遗传算法是模拟自然选择和生物进化过程，以优胜劣汰方法求解问题。算法需要选择一个适宜编码方法表示解，并选择一个评价函数来计算每个解适应值，适应值高解能够更轻易地被选中并进行交配，从而产生新子代。选择和交配过程一直循环，同时以一定概率进行变异，直到求得满意解或其它终止条件。算法运行过程含有很强指向性，适合众多复杂问题求解。
遗传算法过程能够抽象为4大部分：初始化、选择算子、交配算子和变异算子。初始化确定具体问题在遗传算法中编码、群体大小、多种概率大小等参数；选择算子确定怎样在群体中选择新种群；交配算子使选出来种群进行交配以模拟进化；变异算子使新个体能够保持多样性。
旅行商问题要求了每个城市只能出现一次，所以编码有其特殊性，通常采取整数编码方法，经过数字序列来表示城市遍历次序。采取整数编码方法简单遗传算法（SGA）交配策略通常是以单个整数为单位进行，可称为基于点交配；为TSP设计交配策略通常全部会以边为单位进行，可称为基于边交配。

1、简单遗传算法步骤图
随机生成初始种群
计算适应值并保留最优解
交配
变异
优化（可省略）
计算适应值并保留最优解
选择新子代
是否满足终止条件
结束
否
是

2、适应度函数
适应度函数必需能够配合选择方法有效区分子代优劣，我们采取方法是f=1/s ，其中s 是路径总长度。
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）在信息采样周期内，城市规模和城市之间距离等参数固定。

2.设计步骤
2.1需求分析
市场营销需要商家派遣人员到各个城市去调查市场情况和推销企业产品，为了节省开销和节省路途花费时间，就产生了旅行商到各个城市次序和最短路线选择问题。
基于以上问题，旅行商们需要是一款能够直观反应所需抵达城市次序和最短路线可视化应用程序，以供自己参考决议，选择最好行程。
所以，我们程序为了处理以上问题，采取了C++语言编程，其关键功效是：用可视化界面给用户提够所需抵达城市最短路线。用户只需用鼠标和热键点击选择所需抵达城市，然后经过程序运算，就可看到行程路线。
2.2概要设计
针对关键功效，我们首先要设计可视化界面，然后在控件上添加事件过程，再编写代码。
1、 程序中使用关键变量
x//点横坐标
y//点纵坐标
CitySites:Point *//城市序列
RoomSize /./空间大小
Comput //是否正在计算
KillMsg//是否关闭计算
DistanceM//距离矩阵
DMSize//矩阵大小
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()//是否正在计算
GetBestMark()//获取目前最高分
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，这是变异函数得来原因，实现了有父代到子代变异
顺次变异
按块变异
随机数%2
%………………%……5556发达花费较大 地方就是老大房间乐山大佛份开始对焦方法地方全部是分开计算得分手段废旧塑料地方就是打开见风使舵发送到飞水电开发家里看书肌肤上风建设力度封建时代快捷方法简单方@@@@@@@@@@%2
=1
=0

顺次交换：将i到j之间点依次和m到n之间点进行交换，交换函数以下：
tmp = gdest.index[m];
gdest.index[m] = gdest.index[n];
gdest.index[n] = tmp；

……
……
…………………………
…………
……
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,0)
(2,0)
(3,0)
(4,0)
(2,1)
(3,1)
(3,2)
(4,1)
(5,0)
(5,1)
(5,2)
(5,3)
(5,4)
(4,2)
(4,3)

3）// 四边形优化，此函数关键实现了图每次优化，为一个调整函数。
d
0
d
d
d
1
2
3

经过移动线，结构平行四边形，然后经过钝角证实，利用原理两边之和等于第三边上中线两倍，则该三角形为直角三角形，假如d0 + d2 > d1 + d3，则形成角比为锐角；假如是对钝角，则说明该四边形不用优化，假如不是则将该四边形进行优化，因为要组成一个闭合最短回路则要是全部这些组成整个环路这些四边形全部是钝角。

2.4调试分析
1、此程序因为设计到问题比较繁琐，开始是我们计划使用中国邮路算法进行求解，不过因为那个算法对于数量较大时效率太低，我们选择了变异算法，当然程序复杂度也大大增加。又因为我们程序使用MFC来实现，而且我们以前也全部没有接触过MFC，只是对C++语法有所了解，不过经过我们小组努力，边学边用，并借助网络，最终将我们程序跑通，当然我们程序还有很多问题，不过因为时间而且我们学到东西有限，程序也就能够运行到现在情况。
2、程序调试过程中我们也碰到了好多好多问题，有问题出现了以后我们从网上几乎查遍了全部比较有影响力论坛，也问了不少这方面好友。当然大部分问题我们能够经过这种方法处理，有些不能够得四处理问题我们也采取了其它方法处理了一部分问题。因为时间限制还没有处理问题，我们也一定会伴随我们知识增加去逐步完善这个问题。
3、再就是在这次课程设计过程中，学会了利用专业调试工具进行分析，这也能很快帮我们处理问题。还有就是调试并不仅仅是一个最终测试问题，而是伴伴随程序开发整个过程，边写边调，每写完一个过程就该调试一下，不然最终到全部程序结束在进行调试，调试过程将变异常复杂。
4、我们程序调试过程中也发觉了一定问题，比如说线粗细问题，不过MFC提供函数并不能满足需要，不能实现线粗细调整，因为现在时间已经不许可，这个我们只能放到以后进行更改。再就是程序路径显示，但城市数目过多时，因为路径只能显示在一行中，后面显示不出来。现在只能最多完整显示28个城市标号。这个我们写程序队员也了解到这个问题，不过这个实现在c++中确实让我们很为难，她并不像Java中变量处理那么简单。不过这个肯定能够处理，这个我们也会选择一中更完整方法去实现这个功效，我们将在以后程序中加上滚动条，这么不仅能够实现换行，还能够存放更多层。现在处理方案能够实现就是写入文件当中。经过我们测试我们测试自己程序，发觉了太多问题，用起来是那么粗糙，跟那些真正好程序差距还太远，不过经过这次课程设计，使我们了解了MFC开发过程和运行调用过程，这也使我们更多去了解MFC，并深入开发部分有一定价值程序。
5、对于我们程序由输入点坐标带来距离计算问题，可能会给程序效率带来一定影响，因为我们这个程序是在每次运行时候调用距离矩阵函数计算距离矩阵，这在数据量和使用量较大情况下，会给服务器带来很大负担。所以我们程序还能够做一下改善，在真正实际应用过程中不可能是每次全部是随机生成点，而是在数据库中调用预先存入点，这么我们就能够依据预先存入点，经过调用矩阵函数将距离矩阵求出存入数据库，再次调用时候能够直接调用数据库里距离矩阵，从而提升程序运行效率。

2.5测试结果

（1）在“地图”菜单中打开“随机生成”，输入随机数 n=100
（2）单击“确定”并产生随机点，并生成一个初始环路。
(3)单击“计算”菜单中“开机计算”，开始遗传迭代，并产生初始最优解。
（4）经过3394代，4次灾变数，基础达成了最优解，并保留。

（5）下面是n=66最优解。
（6）假如没有产生随机数就开始运行，程序会报错。以下：

3.设计结果展示
3.1用户手册
1、运行环境：WindowsXp/Windows/Windows/等。
2、实施文件：Traveller.exe
3、用户界面：可视化面向用户界面，用鼠标和键盘热键操作，轻易了解，简单易上手。
4、操作过程：
A、打开名称为“Traveller.exe”可实施文件（用鼠标左键双击图标或用右键单击图标并在下拉菜单中选择“打开”）；
B、然后依据自己需要能够按住鼠标添加自己需要点，也能够使用地图选项卡中自动生成生成点，这里能够依据自己要求设置生成点个数。
C、点击菜单栏计算里面开始计算，程序开始运行，当程序运行到自己满意程度，能够点击计算里面停止计算，此时在主窗口下方给出最优路线。
D、程序还能够依据自己需要添加背景图片。
5、其它功效实现：
A、鼠标单击能够选中点
B、按住Shift键单击鼠标，假如是点中某个点，则选中该点，继续按住鼠标拖放能够移动点。假如是没有击中任何点，则新建一个点。
C、按住Shift键，然后按住键盘上D键，能够实现对选中点删除。
D、能够使用此程序菜单栏地图中随机生成功效随机生成点，并能够限定生成点数量。
3.2程序运行部分截图
关键程序截图：
起始图：

终止图：

4.总结和心得体会

1、关键说明设计完成后总结和思索，完成任务情况，收获，意见和提议等。

2、假如是小组汇报，每个组员需要分别进行具体总结和心得体会，且需要先具体说明本人所做具体工作及任务完成情况。（小组中有几人，这个部分写几份！！！）
附 录
一、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;
}
}
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));
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关键代码以下：
// 四边形优化
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]]);
d1 = d3;
}
count++;
if(count > 5)
{
break;
}
}
while(change);
this->Mark(gene);
}……