合肥学院
计算机科学与技术系
课程设计报告
2014～2015学年第一学期
课
程
Java语言程序设计 城市遍历问题求解 13软件工程（2班）
谭明老师、张老师
课程设计名称 专姓指
导
教业
班
级 名 师
2010年9月
一、需求分析
(一)、客户需求
1、 客户可以选择某个城市以及该城市中的起始位置。 2、 起始位置由客户手工输入。 3、 用图形界面将城市信息显示出来。
4、 将查询(或遍历)结果再次用图形效果显示出来。其中包括
遍历的顺序、城市之间的路程长度以及行使的总路程长度。 (二)、程序需求
1、 城市遍历是一个NP完全问题，即当城市数量很大时， 用
普通算法的计算量非常大，因此必须采用一种好的算法。本程序采用模拟退火算法。
2、 用文件保存地图的相关信息。
3、 设计过程中要考虑到程序的可移植性、可扩张性及安全性等
性能要求。
二、设计
(一)、设计思想
该城市遍历问题类似于著名的货郎担问题(Traveling Salesman Problem，简称“TSP”)，也类似于中国邮路问题、旅行商问题。是计算机算法理论历史上的经典问题之一。
首先设计良好的界面布局是至关重要的。综合客户需求和程序需求后，本人决定设计一个矩形界面，包括可选城市列表框(JComboBox)，一个JLabel，一个JTextField以及一个JButton(Find)。
其次是城市信息的图形化显示。考虑到程序的可扩展性、可移植性等性能要求，本人采用MVC编程思想。即DAO层负责对数据库(本程序采用文件存储)的数据读写操作，OP层负责功能的实现，UI层实现为用户提供界面。虽然本程序只用一个DAO，但考虑到如果采用数据库存储方式可能对应不同的数据库或者多个数据库进行操作，因此本程序仍然使用了设计模式里的工厂模式(factory)。图形化显示这就必须使用Applet应用程序以及抽象类Graphics。
然后是退火算法的实现。实现了退火算法后要将最佳遍历序列重起始城市位置开始用红线标出，这就必须使用Graphics类中的一些方法。比如drawLine(),drawString()等。当然，为了达到行使顺序的效果这里需要使用线程中的sleep()方法。 (二)、功能设计
1、 显示城市信息的功能。
这需要获得该城市里的所有位置名称以及坐标。由于本程序通过DAO层过的城市名称后将所有城市放入了ArrayList
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)、退火算法原理
模拟退火算法来源于固体退火原理，将固体加温至充分高，再让其徐徐冷却，加温时，固体内部粒子随温升变为无序状，内能增大，而徐徐冷却时粒子渐趋有序，在每个温度都达到平衡态，