课程设计---城市遍历问题

1、合肥学院计算机科学与技术系课程设计报告20092010学年笫二学期课程Java语言课程设计课程设计名称城市遍历问题求解专业班级07级网络工程（1）班姓名宗丽指导教师张贯虹、许强2010年9月一、需求分析城市遍历问题求解要求用图形展现对城市遍历问题求解的结果。其中要求设计一个文件保存地图信息，地图中标明各个城市之间是否有路及 它们的距离，并手丄输入起始城市，红线标出从起始城市开始遍历所有城市的最短 路径。遍历问题最主要的部分是对求解最短遍历的算法问题，这里我们运用了模拟 退火算法。模拟退火算法新解的产生和接受可分为如下四个步骤：第一步是由一个 产生函数从当前解产生一个位于解空间的新解；为便于后续

2、的计算和接受，减少算 法耗时，通常选择山当前新解经过简单地变换即可产生新解的方法，如对构成新解 的全部或部分元素进行置换、互换等，注意到产生新解的变换方法决定了当前新解 的邻域结构，因而对冷却进度表的选取有一定的影响。第二步是计算与新解所对应 的LI标函数差。因为LI标函数差仅山变换部分产生，所以LI标函数差的讣算最好按 增量讣算。事实表明，对大多数应用而言，这是计算口标函数差的最快方法。笫三 步是判断新解是否被接受，判断的依据是一个接受准则，最常用的接受准则是 Metropolis准则：若Atz 0则接受S作为新的当前解S,否则以概率exp (- t /T)接受S作为新的当前解S。第四步是当

3、新解被确定接受时，用新解代替 当前解，这只需将当前解中对应于产生新解时的变换部分予以实现，同时修正LI标 函数值即可。此时，当前解实现了一次迭代。可在此基础上开始下一轮试验。而当 新解被判定为舍弃时，则在原当前解的基础上继续下一轮试验。对于用图形展现城市及最短路径可以使用Graohics中的一些方法来实现。二、设计(一) 设计思想该题U对于用户需要达到操作简便和结果清晰明了，对于程序员要求采用的 算法尽量适用于城市数量较大时仍能做出正确快捷的计算。用户界面尽量贴近生活中使用的地图，有城市名称及其所在地会有点标明， 手工输入起始城市后查询，会有红线显示最短遍历的路径，并且是山城市到城市一 条一条

4、显示，使遍历的过程更加清晰明了。采用模拟退火算法的实现求解最短遍历，大致思想是重复“产生新解一计算 H标函数差一接受或舍弃”的迭代来进行实现。使用到的方法有Graohics中的 drawLineO, drawstring()等。以及为了达到行使顺序的效果这里需要使用线程中 的sleep()方法。(二) 功能设计1、地图的显示通过对界面上的下拉列表中地图的选择可对不同地图进行城市遍历的结果査 询。每张地图需要获得该城市里的所有位置名称以及坐标。由于本程序通过DAO层 过的城市名称后将所有城市放入了 ArrayList容器中，坐标用二维数组存 储，因此显示时需使用迭代器Iterator及Graph

5、ics中的drawString ()方 法。2、最佳遍历路径的图形化展示该功能主要是结果的图形化过程，即将最佳路径重起始位置开始遍历，用红 线标出路径，本程序附加了数字来标注遍历顺序，并将两城市之间的路程长度也标 注了出来。实现这些功能Graphics中的drawString (), drawLine ()等方法是不可必少 的。(三) 数据库设计本程序未使用数据库存储方式。(四) 详细设讣1、界面部分界面的设计是贴近生活中使用的地图，有图例和路径显示。对于查询最短路 径，需要手工输入起始城市，点击查询按钮查询。界面左边设置一个JComboBox组 件便于用户选择城市，具体位置实现通过setBo

6、unds(a, b, c, d)来实现。后面是一 个JLabel,内容是“起始城市：”。然后是一个JTextField组件，用于用户手工 输入起始位置。最右边是一个JButton 按钮，用于触发查询功能。在第二行最左边是一个JLabel,用于显示此次查询用时多少秒，初始状态是 用时:0. 000000秒。时间的计算通过使用System类中的nanoTime ()方法获得，该时间以毫微妙为单位。接着还是一个JLabel,用于给用户一个良好的提 示，比如当用户输入起始位置不合法时提示“您输入的城市不存在，请重新输 入！”当用户输入合法并点击查询JButton按钮时提示“正在寻找最佳路径，请稍 等”

7、。当正确查询并且将信息图形化后提示“查询结束，欢迎使用！”。下面是一条直线用于分开组件区域和图形化区域，主要是为了美化操作界 面。下面的一个大型矩形区域用于信息的显示。左下角的小型矩形区域是图例信息 的显示区域。当然还有一个JLabel用于显示遍历后的路程总长度，该JLabel只要 在正确查询后才会出现。具体界面如下图所示：图12、对用户操作的处理(1) 判断输入位置是否合法首先将输入内容通过getText ()方法获得并作为textCityName ()的参数，再 通过shoeCity()方法获得该城市所有位置的集合List，该list通过迭代器遍历 与输入内容进行比较，这里使用equals

8、()方法进行比较。(2) 触发事件的处理肖JComboBox触发事件时，设置变量draw,通过draw的值再调用repain () 方法将该城市所有位置图形化显示。当触发查询按钮后，根据输入的合法性设置变 量line的相应值，再调用repaint ()方法。当然，在paint ()方法里会根据变量 draw和变量line的不同值显示不同的信息。包括只显示该城市所有位置信息、遍 历该城市后的最佳行使路径，当然还会调用其他方法，比如：城市信息获得方法 showCity(),退火算法获得最佳路径方法newLoopO.最佳路径图形化方法 setLine ()、显示最佳路径总路程方法showWayLen

9、gth ()等。(3) 查询时间的计算采用System类中的nanoTime ()方法，返回最准确的可用系统计时器的当前 值，返回值是long类型，以毫微秒为单位。此方法只能用于测量已过的时间，与 系统或钟表时间的其他任何时间概念无关。返回值表示从某一固定但任意的时间算 起的毫微秒数(或许从以后算起，所以该值可能为负)。此方法提供毫微秒的精度，但不是必要的毫微秒的准确度。它对于值的更改频率没有作出保证。3、算法的实现(1) 退火算法原理模拟退火算法来源于固体退火原理，将固体加温至充分高，再让其徐徐冷 却，加温时，固体内部粒子随温升变为无序状，内能增大，而徐徐冷却时粒子渐趋 有序，在每个温度都达

10、到平衡态，最后在常温时达到基态，内能减为最小。根据 Metropolis准则，粒子在温度T时趋于平衡的概率为e- AE/(kT),其中E为温度 T时的内能，AE为其改变量，k为Boltzmann常数。用固体退火模拟组合优化问 题，将内能E模拟为LI标函数值f,温度T演化成控制参数t,即得到解组合优化 问题的模拟退火算法：山初始解i和控制参数初值t开始，对当前解重复“产生新 解一计算口标函数差一接受或舍弃”的迭代，并逐步衰减t值，算法终止时的当前 解即为所得近似最优解，这是基于蒙特卡罗迭代求解法的一种启发式随机搜索过 程。退火过程山冷却进度表(Cooling Schedule)控制，包括控制参数

11、的初值t及其 衰减因子At、每个t值时的迭代次数L和停止条件S。(2) 退火的基本思想设有n个城市，用数码1,n代表。城市i和城市j之间的距离为d(i, j) i, j二1,n。模拟退火算法模型可描述如下：解空间S是遍访每个城市恰好一次 的所有回路，是1，n的所有循环排列的集合，S中的成员记为(wl, w2 , wn),并记wn+l= wlo初始解可选为(1, , n)目标函数,此时的LI标函数即为访问所有城市的路径总长度或称为代价函数：我们要求此代价函数 的最小值。新解是随机产生1和n之间的两相异数k和m,若k (wl, w2 ,，wk , wk+1，wm，wn)变为：(wl, w2，wm

12、, wmT，wk+1 , wk， wn)。如果是 km,则将(wl, w2，wk , wk+1 , , wm，wn)变为：(wm, wmT ,，wl , wm+1，wkl , wn , wnl , , wk) o上述变换方法可简单说 成是“逆转中间或者逆转两端”。判断新解是否被接受，当新解被确定接受时，用 新解代替当前解，这只需将当前解中对应于产生新解时的变换部分予以实现，同时 修正目标函数值即可。此时，当前解实现了一次迭代。可在此基础上开始下一轮试 验。而当新解被判定为舍弃时，则在原当前解的基础上继续下一轮试验。(4)退火 算法的模型解空间。解空间S是遍访每个城市恰好一次的所有回路，是1,，

13、n的 所有循环排列的集合，S中的成员记为(wl,w2 , wn),并记wn+l= wlo初始解可选为(1，n)oU标函数。此时的U标函数即为访问所有城市的路径总长度或称为代价函 数，我们要求此代价函数的最小值。新解的产生随机产生1和n之间的两相异数k和m.wmT，wk+1 , wk，wn） o如果是 km,则将（wl, w2，wk , wk+1，wm，wn）变为， （wm, wmT，wl , wm+1，wkl , wn , wn-1，wk） o 上述变换 方法可简单说成是“逆转中间或者逆转两端”。（3）退火算法的参数控制问题模拟退火算法的应用很广泛，可以求解NP完全问题，但其参数难以控制，其

14、主要问题有以下三点：R温度T的初始值设置问题。温度T的初始值设置是影响模 拟退火算法全局搜索性能的重要因素之一、初始温度高，则搜索到全局最优解的可 能性大，但因此要花费大量的讣算时间；反之，则可节约讣算时间，但全局搜索性 能可能受到影响。实际应用过程中，初始温度一般需要依据实验结果进行若干次调 整。b）退火速度问题。模拟退火算法的全局搜索性能也与退火速度密切相关。一般 来说，同一温度下的“充分”搜索（退火）是相当必要的，但这需要计算时间。实际 应用中，要针对具体问题的性质和特征设置合理的退火平衡条件。C）温度管理问 题。温度管理问题也是模拟退火算法难以处理的问题之一。实际应用中，山于必 须考虑计算复杂度的切实可行性等问题，常采用如下所示的降温方式：T（t+1） = kXT（t）式中k为正的略小于1.00的常数，t为降温的次数。三、调试及测试（一）调试过程中遇到的主要问题及解决方法在设计和调试的过程主要遇到了 3个问题。首先是界面的展现和算出最短路 径之后怎样画出最短路径，使用Graohics中的一些方法和一些数组基本解决，但 是在第一次运行程序时需要扩大窗口来刷新界面才能使界面全部展现，该问题经讨 论