一、实验内容及实验要求
【问题描述】
设计一个校园导游程序,为来访的客人提供各种信息查询服务。
【基本要求】
- 设计你所在学校的校园平面图,所含景点不少于10个.以图中顶点表示校 内各景点,存放景点名称、代号、简介 等信息；以边表示路径，存放路径长度等相关信息。
- 为来访客人提供图中任意景点相关信息的查询。
- 为来访客人提供图中任意景点的问路查询，即查询任意两个景点之间的一条最短的简单路径。
【测试数据】
以江苏科技大学长山校区为例。
【实现提示】
一般情况下，校园的道路是双向通行的，可设校园平面图是一个无向网，顶点和边均含有相关信息.
二、问题分析
概述
- 本实验的编程语言采用Java，并用Swing实现了GUI。用户可以点击校内景点的图片来查询该景点的详细信息，程序支持查询任意两景点间的最短路径，并可以根据初始点的位置提供推荐游览路径。
- 数据结构采用了图的邻接矩阵存储，并且为了更加方便的实现Floyd算法，还提供了图的前趋结点数组。
- 最短路径的查询采用了Floyd算法
- 推荐游览路径即是从一个指定景点开始，不重复的游览完所有景点的路径，这一路径的计算采用了马踏棋盘算法，本质上采用了DFS图的深度优先遍历，另外还采用了贪心思想进行了优化。
最短路径——Floyd算法
Floyd算法可以给出网络中任意两个结点之间的最短路径，因此它是比Dijkstra更一般的算法。Floyd算法的思想是将n个结点的网络表示为n行n列的矩阵，而矩阵中的元素Di,j表示从结点i到结点j的距离，如果两点直接没有边相连，则相应的元素就是无穷∞。
具体过程描述如下：
a.从任意一条单边路径开始。所有两点之间的距离是边的权，如果两点之间没有边相连，则权为无穷大。
b.对于每一对结点 i 和 j，看看是否存在一个结点 k 使得从 i 到 k 再到 j 比己知的路径更短。如果是更新它，直到所有的结点都已经尝试过。
伪代码描述如下：
枚举顶点k ∈ [1,n]
以顶点k为中介点，枚举所有顶点对i和j（i ∈ [1,n],j ∈1[1,n]）
如果dis[i][k] + dis[k][j] <dis[i][j]成立
赋值dis[i][j] = dis[i][k] + dis[k][j]
注意Floyd算法为了能回溯得到最短路径的结果，需要声明一个前趋结点数组，用来保存所有点的前一个结点，每次找到更短的路径时，需要更新这一数组。
推荐游览路径——马踏棋盘算法
推荐游览路径是从一个指定景点开始，不重复的游览完所有景点的路径，即在图中寻找一条由指定结点开始的哈密尔顿路径。这一问题可以通过类似马踏棋盘问题的算法来解决，实质上是采用了图的深度优先遍历和贪心算法的优化。
该算法具体过程描述如下：
图的数据结构与前一个算法相同，采用的还是邻接矩阵。
先将当前位置结点设置为已访问，然后根据当前的结点位置，计算下一步还能走哪些位置，并把这些位置放入到一个集合ArrayList中，每走一步，step+1。
遍历ArrayList中存放的所有位置，看看哪个可以走通，如果走通就继续，走不通就回溯。
最后判断是否完成了任务：使用step和应该走的步数比较，如果没有达到数量，则表示没有完成任务，将整个结果置0。
注意这样的搜索结果会根据策略的不同而改变，不同的策略执行的时间快慢也不一样，在这里，我们可以通过贪心算法对它进行优化，具体过程如下
在马踏棋盘算法获取下一步可以走的位置集合ArrayList之前，我们需要对ArrayList集合中点的下一步的所有集合的数目进行非递减排序。
这样在ArrayList中第一个结点就是下一步应该走的结点，我们需要优先选择它，因为它的后续结点最少，代表着需要回溯的点也越少。
采用了贪心算法优化之后，程序执行的时间效率会大大提高。
三、逻辑设计
程序有三个包分别为：domain、service、 ui
domain包下提供了两个类：
- View类是景点的抽象，生成的对象代表学校里的景点，具有私有属性：景点的编号、名称以及景点的介绍。
- MGraph类是图的数据结构，采用邻接矩阵表示，顶点数组中存放每一个景点的对象，该类的构造方法初始化了图的结点和边。
Service包下提供了三个类：
- ShortestPathService类提供了求图中任意两个景点之间的最短路径的Floyd算法。
- TourPathService类提供了求推荐游览路径的马踏棋盘算法。
- ViewsService类用来展示各景点的详细信息。
ui包中是Swing的一些组件类，用于实现GUI，同时其中的MainInterface类也是程序的入口。
以下是程序的流程图：
四、物理设计
本实验的数据结构采用图的邻接矩阵各算法也依据邻接矩阵来实现。图中每个结点都是一个景点View类的对象。
下图是景点的带权无向图：
以下是图以及景点类的数据结构：
package com.domain;
import java.util.Arrays;
/*
类MGraph：用于表示学校景点的无向网
*/
public class MGraph {
//最大顶点数
public static final int MAX_SIZE = 20;
//最大权值，即∞
public static final int MAX_INT = 65535;
//顶点数组
private View[] vertex = new View[MAX_SIZE];
//图的邻接矩阵
private int[][] adj = new int[MAX_SIZE][MAX_SIZE];
//图的前趋结点数组
private int[][] pre = new int[MAX_SIZE][MAX_SIZE];
//图的顶点数和边数
private int vertexNum, edgeNum;
//初始化图结构
public MGraph() {
//设置结点数与边数
vertexNum = 12;
edgeNum = 17;
//初始化顶点数组
initialVertex(vertex);
//初始化邻接矩阵
initialAdj(adj);
//初始化前趋结点数组
initializePre(pre);
}
//初始化顶点数组
private void initialVertex(View[] vertex) {
vertex[0] = new View(1, "行政楼", "办公主楼，校领导办公的地方~");
vertex[1] = new View(2, "海韵湖", "海韵湖连通着长江，景色优美，是饭后散步的好地方，外围有红蓝塑胶跑道，学校时常举办环湖跑比赛");
vertex[2] = new View(3, "图书馆", "图书馆总共五层，室内环境优雅，藏书众多，更有窗边观湖雅座，是各大卷王的必争之地");
vertex[3] = new View(4, "东食堂", "东食堂有很多特色菜肴，食堂对面就是图书馆");
vertex[4] = new View(5, "东操场", "体育锻炼的好地方，时常举办足球比赛");
vertex[5] = new View(6, "南门", "校门庄严气派，毗邻长晖路，马路对面有烧烤和麻辣烫卖");
vertex[6] = new View(7, "文体中心", "一楼有乒乓球馆、健美操馆、健身房，二楼有室内篮球场和羽毛球场，是锻炼身体的好去处，旁边还有船苑剧场可以看电影");
vertex[7] = new View(8, "西操场", "平时举办运动会的地方");
vertex[8] = new View(9, "经世楼", "学校四座教学楼中的一座，其它几个分别为笃学楼、明德楼以及文理大楼，教师多媒体讲台、多功能显示屏、打印机、自动贩卖机等基础设施完善");
vertex[9] = new View(10, "文理大楼", "长山校区的地标建筑，共21层，到天台可以俯瞰整个校园景色，气势磅礴");
vertex[10] = new View(11, "西食堂", "西食堂有三层，第三层是民族食堂，可以品尝各地的特色菜肴");
vertex[11] = new View(12, "西宿舍区", "西片区学生住宿的地方，分为7个组团，从宿舍到教学楼要跑好多路QAQ");
}
//初始化邻接矩阵
private void initialAdj(int[][] adj){
//先初始化
for (int i = 0; i<vertexNum;i++){
for (int j = 0; j<vertexNum;j++){
adj[i][j] = MAX_INT;
}
adj[i][i] = 0;
}
adj[0][1]=300; //行政楼-海韵湖
adj[1][0]=300;
adj[0][9]=700; //行政楼-文理大楼
adj[9][0]=700;
adj[9][8]=100; //文理大楼-经世楼
adj[8][9]=100;
adj[2][9]=400; //文理大楼-图书馆
adj[9][2]=400;
adj[1][2]=600; //海韵湖-图书馆
adj[2][1]=600;
adj[7][8]=100; //西操场-经世楼
adj[8][7]=100;
adj[2][7]=550; //西操场-图书馆
adj[7][2]=550;
adj[7][10]=250; //西食堂-西操场
adj[10][7]=250;
adj[6][7]=100; //文体中心-西操场
adj[7][6]=100;
adj[2][3]=100; //图书馆-东食堂
adj[3][2]=100;
adj[6][10]=300; //西食堂-文体中心
adj[10][6]=300;
adj[3][6]=550; //文体中心-东食堂
adj[6][3]=550;
adj[10][11]=200; //西宿舍区-西食堂
adj[11][10]=200;
adj[5][6]=250; //文体中心-南门
adj[6][5]=250;
adj[3][4]=100; //东食堂-东操场
adj[4][3]=100;
adj[5][11]=700; //西宿舍区-南门
adj[11][5]=700;
adj[4][5]=250; //南门-东操场
adj[5][4]=250;
}
//初始化前趋结点数组
private void initializePre(int[][] pre){
for (int i = 0; i<vertexNum;i++){
Arrays.fill(pre[i],i);
}
}
public View[] getVertex() {
return vertex;
}
public void setVertex(View[] vertex) {
this.vertex = vertex;
}
public int[][] getAdj() {
return adj;
}
public void setAdj(int[][] adj) {
this.adj = adj;
}
public int getVertexNum() {
return vertexNum;
}
public void setVertexNum(int vertexNum) {
this.vertexNum = vertexNum;
}
public int getEdgeNum() {
return edgeNum;
}
public void setEdgeNum(int edgeNum) {
this.edgeNum = edgeNum;
}
public int[][] getPre() {
return pre;
}
public void setPre(int[][] pre) {
this.pre = pre;
}
}
package com.domain;
/*
类View：用于表示每一个景点
*/
public class View {
//景点的编号
private int id;
//景点的名称
private String name;
//景点的介绍
private String introduction;
public View(int id, String name, String introduction) {
this.id = id;
this.name = name;
this.introduction = introduction;
}
public int getId() {
return id;
}
public void setId(int id) {
this.id = id;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public String getIntroduction() {
return introduction;
}
public void setIntroduction(String introduction) {
this.introduction = introduction;
}
}
下面是最短路径Floyd算法的代码：
//Floyd算法
private void floyd() {
//变量保存距离
int len = 0;
//对中间结点遍历，k就是中间结点的下标
for (int k = 0; k < mGraph.getVertexNum(); k++) {
//从i结点开始出发
for (int i = 0; i < mGraph.getVertexNum(); i++) {
//到达j结点
for (int j = 0; j < mGraph.getVertexNum(); j++) {
//从i结点出发，经过中间结点k，到达j结点的距离
len = dis[i][k] + dis[k][j];
//如果比原来的距离小，更新距离和前趋结点
if (len < dis[i][j]) {
dis[i][j] = len;
pre[i][j] = pre[k][j];
}
}
}
}
}
下面是推荐游览路径马踏棋盘算法及其使用贪心算法优化的代码：
/*
DFS寻找哈密尔顿路径：马踏棋盘算法
result为图，id为当前点（从0开始），step为步数记录,初始步数为1
*/
private void traversalMap(int[] result, int id, int step){
//更新结果图
result[id] = step;
//标志该位置已经访问
visited[id] = true;
//获取当前位置可以走的下一个位置的集合
ArrayList<Integer> ps = next(id);
//利用贪心算法排序优化，优先选择下一步可选择位置最少的点
sort(ps);
//遍历ps,递归回溯
while (!ps.isEmpty()){
//取出下一个可以走的位置
Integer p = ps.remove(0);
//判断该点是否被访问过
if (!visited[p]){
//如果没有访问过,进行下一步
traversalMap(result,p,step+1);
}
}
//判读是否遍历了所有的点，使用step和应该走的步数比较，如果没有到达数量，将整个结果置0
//step<结点数 成立的情况有两种
//1.所有结点到目前为止仍然没有走完
//2.所有结点到目前为止已经走完，处于回溯过程（无路可走）
if (step<mGraph.getVertexNum() && !finished){
result[id] = 0;
visited[id] = false;
}else {
//如果完成了
finished = true;
}
}
//根据当前点的位置，计算还能走哪些位置，把这些点的id放入一个ArrayList中,id从0-11
private ArrayList<Integer> next(int id) {
ArrayList<Integer> ps = new ArrayList<>();
for (int j = 0; j<mGraph.getVertexNum(); j++) {
//如果这条路连通，就把点加入
if (dis[id][j]<MGraph.MAX_INT){
ps.add(j);
}
}
return ps;
}
//利用贪心算法对DFS优化
//根据当前这一步的下一步的选择位置，进行非递减排序，减少在DFS时的回溯次数
private void sort(ArrayList<Integer> ps){
ps.sort(new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return next(o1).size()-next(o2).size();
}
});
}
查询景点详细信息的代码最为简单，但用GUI实现景点的展示对我这个新手来说还是很繁琐的。文章来源：https://www.toymoban.com/news/detail-787466.html
//传入景点id，返回景点的介绍（字符串）
public String getViewInformation(int id){
return vertex[id-1].getIntroduction();
}
总结
对于本次实验来说还有许多可以改进的地方文章来源地址https://www.toymoban.com/news/detail-787466.html
- 图的结点是不可以修改的，其实一开始也考虑过通过文件读取图中结点以及边的权值信息，或者用户可以手动修改结点和边的信息。但因为想要用GUI展示，对于结点的修改肯定要动态的改变地图样貌，这样一来实现起来就非常困难，而且用户对结点修改的步骤也较为繁琐，所以索性就把结点和边定死了。
- 图不能动态的展示，每次查询最短路径只能通过文字信息展现，不能在地图上画出此次查询的最短路线。因为要实现这一功能需要加上窗口的坐标变换和计算，画出相应的行动轨迹，对我来说过于困难。
- 功能较少，只有查询景点、最短路径和推荐路径这三个功能。其实一方面可以根据路况信息、甚至是地形的坡度来动态的改变边的权值。另一方面可以增加每个景点的推荐程度这一信息来对景点进行排序，给用户优先级的推荐等。
- 推荐路径只能推荐从当前结点出发一个可行的哈密尔顿道路，并不能求出游览所有景点一次的最短道路。
到了这里，关于数据结构课程设计——项目2：校园导游咨询的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
