合肥学院。
计算机科学与技术系。
2014～2015学年第一学期。
2010年9月。
1、需求分析。
一)、客户需求
1、 客户可以选择某个城市以及该城市中的起始位置。
2、 起始位置由客户手工输入。
3、 用图形界面将城市信息显示出来。
4、 将查询(或遍历)结果再次用图形效果显示出来。其中包括遍历的顺序、城市之间的路程长度以及行使的总路程长度。
二)、程序需求。
1、 城市遍历是一个np完全问题，即当城市数量很大时， 用普通算法的计算量非常大，因此必须采用一种好的算法。本程序采用模拟退火算法。
2、 用文件保存地图的相关信息。
3、 设计过程中要考虑到程序的可移植性、可扩张性及安全性等性能要求。
2、设计。一)、设计思想。
该城市遍历问题类似于著名的货郎担问题(tr**eling salesman problem，简称“tsp”)，也类似于中国邮路问题、旅行商问题。是计算机算法理论历史上的经典问题之一。
首先设计良好的界面布局是至关重要的。综合客户需求和程序需求后，本人决定设计一个矩形界面，包括可选城市列表框(jcombobox)，一个jlabel，一个jtextfield以及一个jbutton(find)。
其次是城市信息的图形化显示。考虑到程序的可扩展性、可移植性等性能要求，本人采用mvc编程思想。即dao层负责对数据库(本程序采用文件存储)的数据读写操作，op层负责功能的实现，ui层实现为用户提供界面。
虽然本程序只用一个dao，但考虑到如果采用数据库存储方式可能对应不同的数据库或者多个数据库进行操作，因此本程序仍然使用了设计模式里的工厂模式(factory)。图形化显示这就必须使用applet应用程序以及抽象类graphics。
然后是退火算法的实现。实现了退火算法后要将最佳遍历序列重起始城市位置开始用红线标出，这就必须使用graphics类中的一些方法。比如drawline(),drawstring()等。
当然，为了达到行使顺序的效果这里需要使用线程中的sleep()方法。
二)、功能设计。
1、 显示城市信息的功能。
这需要获得该城市里的所有位置名称以及坐标。由于本程序通过dao层过的城市名称后将所有城市放入了arraylist容器中，坐标用二维数组存储，因此显示时需使用迭代器iterator及graphics中的drawstring()方法。为了视觉上的美观，颜色设计方法setcolor()也是必不可少的。
2、 根据用户手工输入的起始位置开始遍历，寻找最佳路径。
这一功能的实现也是解决实现本程序的核心。对于用户输入的起始位置首先应该判断输入是否合法，即该城市(或该地图)是否存在此起始位置。合法输入之后应该触发查询按钮jbutton了。
之后的事件通过事件监听方法actionperformed()实现。
接下来是退火算法的实现寻找最佳路径。这里的最佳路径指的是遍历城市所有位置所行使的路程长度最短。具体实现在下面的详细设计中说明。
3、 将最佳遍历路径用图形化实现。
该功能主要是结果的图形化过程，即将最佳路径重起始位置开始遍历，用红线标出路径，本程序附加了(?)来标注遍历顺序，并将两城市之间的路程长度也标注了出来。
实现这些功能graphics中的drawstring()，drawline()等方法是不可比少的。
三)、数据库设计。
本程序未使用数据库存储方式，使用了文件存储。文件存储各个城市里的地方名称，包括合肥市(合肥学院，安徽大学，火车东站等)，蚌埠市(蚌埠学院，蚌埠医学院，安徽财经大学等)等。
四)、详细设计。
1、 界面设计。
左边设置一个jcombobox组件便于用户选择城市，具体位置实现通过setbounds(a,b,c,d)来实现。后面是一个jlabel，内容是“起始城市：”。
然后是一个jtextfield组件，用于用户手工输入起始位置。最右边是一个jbutton 按钮，用于触发查询功能。
在第二行最左边是一个jlabel，用于显示此次查询用时多少秒，初始状态是“用时：0.000000秒”。
时间的计算通过使用system类中的nanotime()方法获得，该时间以毫微妙为单位。接着还是一个jlabel，用于给用户一个良好的提示，比如当用户输入起始位置不合法时提示“您输入的城市不存在，请重新输入！”当用户输入合法并点击查询jbutton按钮时提示“正在寻找最佳路径，请稍等。
当正确查询并且将信息图形化后提示“查询结束，欢迎使用！”。
下面是一条直线用于分开组件区域和图形化区域，主要是为了美化操作界面。下面的一个大型矩形区域用于信息的显示。左下角的小型矩形区域是图例信息的显示区域，内容包括：
1)、(行驶顺序。(2)、-直达路线。当然还有一个jlabel用于显示遍历后的路程总长度，该jlabel只要在正确查询后才会出现。具体界面如下图所示。
2、 功能设计。
1)、判断输入位置是否合法。
首先将输入内容通过gettext()方法获得并作为textcityname()的参数，再通过shoecity()方法获得该城市所有位置的集合，该list通过迭代器遍历与输入内容进行比较，这里使用equals()方法进行比较。
2)、触发事件的处理。
当jcombobox触发事件时，设置变量draw，通过draw的值再调用repain()方法将该城市所有位置图形化显示。当触发查询按钮后，根据输入的合法性设置变量line的相应值，再调用repaint()方法。当然，在paint()方法里会根据变量draw和变量line的不同值显示不同的信息。
包括只显示该城市所有位置信息、遍历该城市后的最佳行使路径，当然还会调用其他方法，比如：城市信息获得方法showcity()，退火算法获得最佳路径方法newloop()、最佳路径图形化方法setline()、显示最佳路径总路程方法showwaylength()等。
3)、查询时间的计算。
采用system类中的nanotime()方法，返回最准确的可用系统计时器的当前值，返回值是long类型，以毫微秒为单位。此方法只能用于测量已过的时间，与系统或钟表时间的其他任何时间概念无关。返回值表示从某一固定但任意的时间算起的毫微秒数（或许从以后算起，所以该值可能为负）。
此方法提供毫微秒的精度，但不是必要的毫微秒的准确度。它对于值的更改频率没有作出保证。
3、 退火算法的实现。
1)、退火算法原理。
模拟退火算法**于固体退火原理，将固体加温至充分高，再让其徐徐冷却，加温时，固体内部粒子随温升变为无序状，内能增大，而徐徐冷却时粒子渐趋有序，在每个温度都达到平衡态，最后在常温时达到基态，内能减为最小。根据metropolis准则，粒子在温度t时趋于平衡的概率为e-δe/(kt)，其中e为温度t时的内能，δe为其改变量，k为boltzmann常数。用固体退火模拟组合优化问题，将内能e模拟为目标函数值f，温度t演化成控制参数t，即得到解组合优化问题的模拟退火算法：
由初始解i和控制参数初值t开始，对当前解重复“产生新解→计算目标函数差→接受或舍弃”的迭代，并逐步衰减t值，算法终止时的当前解即为所得近似最优解，这是基于蒙特卡罗迭代求解法的一种启发式随机搜索过程。退火过程由冷却进度表(cooling schedule)控制，包括控制参数的初值t及其衰减因子δt、每个t值时的迭代次数l和停止条件s。
2)、退火的基本思想。
2).1 初始化：初始温度t(充分大)，初始解状态s(是算法迭代的起点)，每个t值的迭代次数l。
2).2 对k=1，……l做第(3)至第6步。
2).3 产生新解s′。
2).4 计算增量δt′=c(s′)-c(s)，其中c(s)为评价函数。
2).5 若δt′<0则接受s′作为新的当前解，否则以概率exp(- t′/t)接受s′作为新的当前解。
2).6 如果满足终止条件则输出当前解作为最优解，结束程序。 终止条件通常取为连续若干个新解都没有被接受时终止算法。
2).7 t逐渐减少，且t->0，然后转第2步。
3)退火算法新解的产生和接受。
3).1 由一个产生函数从当前解产生一个位于解空间的新解；为便于后续的计算和接受，减少算法耗时，通常选择由当前新解经过简单地变换即可产生新解的方法，如对构成新解的全部或部分元素进行置换、互换等，注意到产生新解的变换方法决定了当前新解的邻域结构，因而对冷却进度表的选取有一定的影响。
3).2 是计算与新解所对应的目标函数差。因为目标函数差仅由变换部分产生，所以目标函数差的计算最好按增量计算。事实表明，对大多数应用而言，这是计算目标函数差的最快方法。
3).3 是判断新解是否被接受，判断的依据是一个接受准则，最常用的接受准则是metropo1is准则： 若δt′<0则接受s′作为新的当前解s，否则以概率exp(-δt′/t)接受s′作为新的当前解s。
3).4 是当新解被确定接受时，用新解代替当前解，这只需将当前解中对应于产生新解时的变换部分予以实现，同时修正目标函数值即可。此时，当前解实现了一次迭代。
可在此基础上开始下一轮试验。而当新解被判定为舍弃时，则在原当前解的基础上继续下一轮试验。
4)退火算法的模型
解空间。解空间s是遍访每个城市恰好一次的所有回路，是的所有循环排列的集合，s中的成员记为(w1,w2 ,…wn)，并记wn+1= w1。初始解可选为(1，……n)。
目标函数。此时的目标函数即为访问所有城市的路径总长度或称为代价函数，我们要求此代价函数的最小值。
新解的产生随机产生1和n之间的两相异数k和m。
若k 如果是k>m，则将(w1, w2 ,…wk , wk+1 ,…wm ,…wn)变为， (wm, wm-1 ,…w1 , wm+1 ,…wk-1 ,wn , wn-1 ,…wk)。上述变换方法可简单说成是“逆转中间或者逆转两端”。
5) 退火算法的参数控制问题。
模拟退火算法的应用很广泛，可以求解np完全问题，但其参数难以控制，其主要问题有以下三点：
5).1 温度t的初始值设置问题。温度t的初始值设置是影响模拟退火算法全局搜索性能的重要因素之。
一、初始温度高，则搜索到全局最优解的可能性大，但因此要花费大量的计算时间；反之，则可节约计算时间，但全局搜索性能可能受到影响。实际应用过程中，初始温度一般需要依据实验结果进行若干次调整。
5).2 退火速度问题。模拟退火算法的全局搜索性能也与退火速度密切相关。
一般来说，同一温度下的“充分”搜索(退火)是相当必要的，但这需要计算时间。实际应用中，要针对具体问题的性质和特征设置合理的退火平衡条件。
5).3 温度管理问题。 温度管理问题也是模拟退火算法难以处理的问题之一。
实际应用中，由于必须考虑计算复杂度的切实可行性等问题，常采用如下所示的降温方式：t(t+1)＝k×t(t) 式中k为正的略小于1.00的常数，t为降温的次数 。
3、调试与测试。
一、测试过程中遇到的主要问题及解决方法。
1、如何获得大量的城市信息(名称、坐标等)？
答：通过buffeedreader将信息存入list中，在通过迭代器iterator依次读出这些信息。
2、如何图形化信息？
课程设计报告格式 课程设计
洛阳理工学院。课程设计说明书。课程名称。设计课题。专业。班级。学号。姓名。完成日期2014年12月26日。问题描述 小四宋体，行间距单倍行距，每段缩进两个字符。叙述一下设计的内容要求。基本要求 小四宋体，行间距单倍行距，每段缩进两个字符。叙述一下设计的基本要求。测试数据 小四宋体，行间距单倍行距，每...
课程设计总结,课程设计报告
课程设计总结，课程设计报告。3.尝试应用项目管理软件进行项目进程的规划管理 绘制甘特图，不作硬性要求 二 选题说明。人事管理是企业信息管理的重要部分，面对大量的人事工资信息，财务部门采用人力处理将浪费大量的时间 人力和物力，且数据的准确性低。因此，开发一个界面友好，易于操作的人事工资管理软件进行自动...
课程设计 课程设计报告格式
学校名。课程设计报告。课程名称 c语言程序设计 系别 专业班级 学号。姓名。课程题目 企业人事管理系统 完成日期 指导老师 年月日。附件。课程设计的内容。企业人事管理系统 本项目的目标是开发一个功能实用，操作简便，简单明了的人事管理系统。能够录入人事的基本资料，在操作上能够完成诸如添加 修改 删除 ...