1、二、设计（一）设计思想该题目对于用户需要达到操作简便和结果清晰明了，对于程序员要求采用的算法尽量适用于城市数量较大时仍能做出正确快捷的计算。用户界面尽量贴近生活中使用的地图，有城市名称及其所在地会有点标明，手工输入起始城市后查询，会有红线显示最短遍历的路径，并且是由城市到城市一条一条显示，使遍历的过程更加清晰明了。采用模拟退火算法的实现求解最短遍历，大致思想是重复“产生新解计算目标函数差接受或舍弃”的迭代来进行实现。使用到的方法有Graohics中的drawLine（）,drawString（）等。以及为了达到行使顺序的效果这里需要使用线程中的sleep（）方法。（二）功能设计1、地图的显示通
2、过对界面上的下拉列表中地图的选择可对不同地图进行城市遍历的结果查询。每张地图需要获得该城市里的所有位置名称以及坐标。由于本程序通过DAO层过的城市名称后将所有城市放入了ArrayList容器中，坐标用二维数组存储，因此显示时需使用迭代器Iterator及Graphics中的drawString（）方法。2、最佳遍历路径的图形化展示该功能主要是结果的图形化过程，即将最佳路径重起始位置开始遍历，用红线标出路径，本程序附加了数字来标注遍历顺序，并将两城市之间的路程长度也标注了出来。实现这些功能Graphics中的drawString（），drawLine（）等方法是不可必少的。（三）数据库设计本程序
3、未使用数据库存储方式。（四）详细设计1、界面部分界面的设计是贴近生活中使用的地图，有图例和路径显示。对于查询最短路径，需要手工输入起始城市，点击查询按钮查询。界面左边设置一个JComboBox组件便于用户选择城市，具体位置实现通过setBounds（a,b,c,d）来实现。后面是一个JLabel，内容是“起始城市：”。然后是一个JTextField组件，用于用户手工输入起始位置。最右边是一个JButton 按钮，用于触发查询功能。在第二行最左边是一个JLabel，用于显示此次查询用时多少秒，初始状态是“用时：0.000000秒”。时间的计算通过使用System类中的nanoTime（）方法获得
4、，该时间以毫微妙为单位。接着还是一个JLabel，用于给用户一个良好的提示，比如当用户输入起始位置不合法时提示“您输入的城市不存在，请重新输入！”当用户输入合法并点击查询JButton按钮时提示“正在寻找最佳路径，请稍等.”。当正确查询并且将信息图形化后提示“查询结束，欢迎使用！下面是一条直线用于分开组件区域和图形化区域，主要是为了美化操作界面。下面的一个大型矩形区域用于信息的显示。左下角的小型矩形区域是图例信息的显示区域。当然还有一个JLabel用于显示遍历后的路程总长度，该JLabel只要在正确查询后才会出现。具体界面如下图所示:图12、对用户操作的处理（1）判断输入位置是否合法首先将输入
5、内容通过getText（）方法获得并作为textCityName（）的参数，再通过shoeCity（）方法获得该城市所有位置的集合，该list通过迭代器遍历与输入内容进行比较，这里使用equals（）方法进行比较。（2）触发事件的处理当JComboBox触发事件时，设置变量draw，通过draw的值再调用repain（）方法将该城市所有位置图形化显示。当触发查询按钮后，根据输入的合法性设置变量line的相应值，再调用repaint（）方法。当然，在paint（）方法里会根据变量draw和变量line的不同值显示不同的信息。包括只显示该城市所有位置信息、遍历该城市后的最佳行使路径，当然还会调用其
6、他方法，比如：城市信息获得方法showCity（），退火算法获得最佳路径方法newLoop（）、最佳路径图形化方法setLine（）、显示最佳路径总路程方法showWayLength（）等。（3）查询时间的计算采用System类中的nanoTime（）方法，返回最准确的可用系统计时器的当前值，返回值是long类型，以毫微秒为单位。此方法只能用于测量已过的时间，与系统或钟表时间的其他任何时间概念无关。返回值表示从某一固定但任意的时间算起的毫微秒数（或许从以后算起，所以该值可能 为负）。此方法提供毫微秒的精度，但不是必要的毫微秒的准确度。它对于值的更改频率没有作出保证。3、算法的实现（1）退火算法
7、原理模拟退火算法来源于固体退火原理，将固体加温至充分高，再让其徐徐冷却，加温时，固体内部粒子随温升变为无序状，内能增大，而徐徐冷却时粒子渐趋有序，在每个温度都达到平衡态，最后在常温时达到基态，内能减为最小。根据Metropolis准则，粒子在温度T时趋于平衡的概率为e-E/（kT），其中E为温度T时的内能，E为其改变量，k为Boltzmann常数。用固体退火模拟组合优化问题，将内能E模拟为目标函数值f，温度T演化成控制参数t，即得到解组合优化问题的模拟退火算法：由初始解i和控制参数初值t开始，对当前解重复“产生新解计算目标函数差接受或舍弃”的迭代，并逐步衰减t值，算法终止时的当前解即为所得近似
8、最优解，这是基于蒙特卡罗迭代求解法的一种启发式随机搜索过程。退火过程由冷却进度表（Cooling Schedule）控制，包括控制参数的初值t及其衰减因子t、每个t值时的迭代次数L和停止条件S。（2）退火的基本思想设有n个城市，用数码1,n代表。城市i和城市j之间的距离为d（i，j） i, j=1,n。模拟退火算法模型可描述如下：解空间S是遍访每个城市恰好一次的所有回路，是1，n的所有循环排列的集合，S中的成员记为（w1,w2 ,，wn），并记wn+1= w1。初始解可选为（1，n）目标函数，此时的目标函数即为访问所有城市的路径总长度或称为代价函数：我们要求此代价函数的最小值。新解是随机产生1
9、和n之间的两相异数k和m，若k （w1, w2 ,，wk , wk+1 ,，wm ,，wn）变为：（w1, w2 ,，wm , wm-1 ,，wk+1 , wk ,，wn）。如果是km，则将 （w1, w2 ,，wk , wk+1 ,，wm ,，wn）变为：（wm, wm-1 ,，w1 , wm+1 ,，wk-1 ,wn , wn-1 ,，wk）。上述变换方法可简单说成是“逆转中间或者逆转两端”。判断新解是否被接受,当新解被确定接受时，用新解代替当前解，这只需将当前解中对应于产生新解时的变换部分予以实现，同时修正目标函数值即可。（4）退火算法的模型解空间。初始解可选为（1，n）。目标函数。此时
10、的目标函数即为访问所有城市的路径总长度或称为代价函数，我们要求此代价函数的最小值。新解的产生随机产生1和n之间的两相异数k和m。若k m（w1, w2 ,，wk , wk+1 ,，wm ,，wn）变为（w1, w2 ,，wm , wm-1 ,，wk+1 , wk ,，wn）。m，则将（w1, w2 ,，wk , wk+1 ,，wm ,，wn）变为， （wm, wm-1 ,，w1 , wm+1 ,，wk-1 ,wn , wn-1 ,，wk）。 （3） 退火算法的参数控制问题模拟退火算法的应用很广泛，可以求解NP完全问题，但其参数难以控制，其主要问题有以下三点：a）温度T的初始值设置问题。温度T的
11、初始值设置是影响模拟退火算法全局搜索性能的重要因素之一、初始温度高，则搜索到全局最优解的可能性大，但因此要花费大量的计算时间；反之，则可节约计算时间，但全局搜索性能可能受到影响。实际应用过程中，初始温度一般需要依据实验结果进行若干次调整。b）退火速度问题。模拟退火算法的全局搜索性能也与退火速度密切相关。一般来说，同一温度下的“充分”搜索（退火）是相当必要的，但这需要计算时间。实际应用中，要针对具体问题的性质和特征设置合理的退火平衡条件。C）温度管理问题。 温度管理问题也是模拟退火算法难以处理的问题之一。实际应用中，由于必须考虑计算复杂度的切实可行性等问题，常采用如下所示的降温方式：T（t+1）
12、kT（t） 式中k为正的略小于1.00的常数，t为降温的次数 。三、调试及测试（一）调试过程中遇到的主要问题及解决方法在设计和调试的过程主要遇到了3个问题。首先是界面的展现和算出最短路径之后怎样画出最短路径，使用Graohics中的一些方法和一些数组基本解决，但是在第一次运行程序时需要扩大窗口来刷新界面才能使界面全部展现，该问题经讨论还未解决。其次是算法的实现，在对退火算法资料的查询和阅读后，写出算法并通过数据验证也已解决，但是对于退火的温度管理本程序仅仅使用了简单的多次循环来结束退火。（二）对设计和编码的回顾讨论和分析此程序基本完成题目所要求的一些功能。采用了MVC编程思想和工厂模式，使得程
13、序的扩展性、移植性得到很好的保证。程序代码分布清晰，各类功能、函数功能一目了然，较符合java编程规范。本程序在初始化时组件无法显示，必须拖动界面才可以，这是本程序的不足或者技术方面的欠缺。在退火算法的条件控制中没能根据城市的数量来计算退火的条件，即何时结束退火算法的设置不是很科学。此外程序中城市较少，无法满足客户需求，程序有待于进一步完善（三）程序运行的时空效率分析此程序时间效率较低，根据查询用时结果可知。造成这一现象主要是因为退火算法的条件控制没有达到较好，也是本程序最大不足之处之一。另外一个原因是由于本程序采用文件存储，因此在数据读取方面速度会比较慢，这也会影响程序的时间效率。城市坐标用
14、二维数组来进行存储，城市间可视为无向图，因此可采用特殊矩阵中的对称三角方式来存储，即变成一维数组。但在具体的程序编写时发现，当数据较大时或者维数较多时，同样的数据采用一维数组和二维数组存储时，二维数组的访问速度较快，而且二位数组读取较方便。虽然在空间性能上有些不足，但提高了访问速度。（四）测试数据集输入不合法时：图2输入合法时：图3图4四、经验和体会拿到Java程序语言课程设计的题目后，首先是读题对题目进行需求分析，考虑一些编程中可能遇到的问题。其次开始界面设计、类的设计、类功能的连接等等实现。在遇到问题解决问题的过程中不断完善功能。至此在经过对程序的反复修改和同伴讨论之后完成的程序仍然存在一
15、些的不足，还有待我们发现以及改进。例如对退火条件的设置不是很科学等。这次Java课程设计不仅考查了对Java语言基本理论知识的学习程度还考核了我们综合运用以及学习新知识的能力，并且在编写过程中还考验了我们与人合作的能力。完成一个课题需要对JAVA语言的GUI设计、文件的熟练掌握以及灵活运用各种类库，并且需要有对问题的理解、解决这个过程的能力。认识到对于编写一个较为复杂的软件系统而言，不能一拿到课题就开始编写程序，程序的需求分析和设计分析是必须的。这对于我们将来的就业有很大的帮助。我们在以后的学习过程中更要加大对这方面的学习力度，为将来的就业打下牢固的基础。附录：主要源程序/主界面类，包括一些功
16、能的实现public class ui extends JFrame implements ActionListener private userOP usOP = new userOP（）; private annealingMeans annealing = new annealingMeans（）; private List list, newList; private static int draw = 0, line = 0; private String cityName = new String（）;private static long startTime = 0,endTim
17、e = 0; String anHui = 合肥市, 蚌埠市安庆市芜湖市阜阳市淮北市 ;String timeStr = 查询用时：0.000000 秒; JComboBox box = new JComboBox（anHui）; JLabel startCity = new JLabel（起始城市:）; JLabel time = new JLabel（timeStr）; JLabel Info = new JLabel（ - 欢 迎 使 用 - JTextField start = new JTextField（）; JButton find = new JButton（查询 public
18、 ui（） this.setLayout（null）; this.setTitle（城 市 遍 历 box.setBounds（90, 12, 70, 30）; this.add（box）; box.addActionListener（this）;/ 为下拉列表注册监听器 / 加入起始城市标签 startCity.setBounds（190, 15, 230, 30）; this.add（startCity）; /加入起始城市输入组件JTextField start.setBounds（260, 15, 100, 24）; this.add（start）; start.addActionLis
19、tener（this）;/ 为文本框注册监听器 / 显示查询用时 time.setBounds（20, 20, 160, 60）; this.add（time）; / 加入查询用时标签 Info.setBounds（240, 20, 300, 60）; this.add（Info）; /加入查询按钮 find.setBounds（520, 15, 80, 30）; this.add（find）; find.addActionListener（this）;/ 为查询按钮注册监听器 this.setBounds（200, 200, 700, 530）;/ 窗口大小、位置 this.setVisib
20、le（true）; public void paint（Graphics g） String startCityName = start.getText（）.trim（）; / 绘制图例内容 g.setColor（new Color（83, 205, 74）; g.drawString（?）, 22, 435）; g.setColor（Color.black）; 行驶顺序, 45, 435）; g.setColor（Color.red）;, 22, 450）;直达路线, 48, 450）; / 设置直线（连接两个城市的）颜色 if （draw = 1） cityName = / 获得合肥市所有
21、地方名称信息 list = usOP.showCity（cityName）; / 计算和设置查询所用时间 public void showTime（long a） float f = a / 1000; float b = new Float（f / 1000000）.floatValue（）; time.setText（ + String.valueOf（b） + 秒 / 用于显示行使的总路程 SuppressWarnings（static-access） public void showWayLength（Graphics g） Info.setText（查询结束，欢迎使用！ g.setC
22、olor（Color.white）;总路程: + annealing.wayLength + 米, 20, 470）; /userOP类，主要是操作功能的一些方法public class userOP private pathInfo paInfo = new pathInfo（）; public static int lineOK = 0; / 判断输入的城市是否有效 public boolean testCityName（String cityName, String name） List list = this.showCity（cityName）; Iterator li = list
23、.iterator（）; while （li.hasNext（） String strName = li.next（）; if （name.trim（）.equals（strName） return true; return false; / 返回城市列表 public List showCity（String name） return （List） factory.getFac（）.getUserDAO（）.read（name） / 显示城市name的名称 public void show（Graphics g, List list, String name） int i = 0, x =
24、0, y = 0, a = null; a = this.getZB（name）; String city = li.next（）; x = ai0; y = ai1; g.setColor（Color.blue）; g.fillArc（x, y, 10, 10, 0, 360）; g.setColor（Color.black）; g.drawString（city, x, y）; i+; if （i = a.length） break; / 画出序列list的路线 public void setLine（Graphics g, String city, List S, List newLis
25、t, String startCity） int zb = null,i=0, x = 0, y = 0, w = 0, h = 0, stop = 0; int startCityIndex = 0,newListSize=newList.size（）; /获得该城市的路径长度 int way=this.getCityWay（city）; / 获得原始序列坐标 zb = this.getZB（city）; / 判断起始位置在最佳序列中位置 int indexOfNewList = newList.indexOf（startCity）; / 起始位置在原始序列中的坐标 startCityInd
26、ex = S.indexOf（startCity）; i = startCityIndex; while （true） x = zbi0; y = zbi1; startCityIndex=i; if （indexOfNewList = （newListSize- 1） indexOfNewList = 0; else indexOfNewList+; String str = newList.get（indexOfNewList）; i = S.indexOf（str）; w = zbi0; h = zbi1; g.setColor（Color.red）; try Thread.sleep（1000）; catch （InterruptedException e） e.printStackTrace（）; g.drawLine（x, y, w, h）; stop+;g.drawString（
