问题描述

城市之间有各种交通工具（汽车、火车和飞机）相连，有些城市之间无法直达，需要途径中转城市。某旅客于某一时刻向系统提出旅行要求。考虑在当前 COVID-19 疫情环境下，各个城市的风险程度不一样，分为低风险、中风险和高风险三种。系统根据风险评估，为该旅客设计一条符合旅行策略的旅行线路并输出；系统能查询当前时刻旅客所处的地点和状态（停留城市/所在交通工具）

功能需求

城市总数不少于 10 个，为不同城市设置不同的单位时间风险值：低风险城市为 0.2；中风险城市为 0.5；高风险城市为 0.9。各种不同的风险城市分布要比较均匀，个数均不得小于 3 个。旅客在某城市停留风险计算公式为：旅客在某城市停留的风险=该城市单位时间风险值*停留时间。

建立汽车、火车和飞机的时刻表（航班表），假设各种交通工具均为起点到终点的直达，中途无经停。

不能太简单，城市之间不能总只是 1 班车次；

整个系统中航班数不得超过 10 个，火车不得超过 30 列次；汽车班次无限制；

旅客的要求包括：起点、终点和选择的低风险旅行策略。其中，低风险旅行策略包括：

最少风险策略：无时间限制，风险最少即可

限时最少风险策略：在规定的时间内风险最少

旅行模拟系统以时间为轴向前推移，每 10 秒左右向前推进 1 个小时(非查询状态的请求不计时，即：有鼠标和键盘输入时系统不计时)；

不考虑城市内换乘交通工具所需时间

系统时间精确到小时

建立日志文件，对旅客状态变化和键入等信息进行记录

用图形绘制地图，并在地图上实时反映出旅客的旅行过程。

为不同交通工具设置不同单位时间风险值，交通工具单位时间风险值分别为：汽车=2；火车=5；飞机=9。旅客乘坐某班次交通工具的风险 = 该交通工具单位时间风险值该班次起点城市的单位风险值乘坐时间。将乘坐交通工具的风险考虑进来，实现前述最少风险策略和限时风险最少策略。

功能分析：

城市风险值存储在 MySQL 数据库中，设置 10 个城市

设计城市之间的时刻表，并存储在 MySQL 数据库中

时间推进功能需要设置定时器，每隔一秒发出超时信号，时间向前进 6 分钟，并实时更新现在时间至图形化界面上

日志文件使用 qInstallMessageHandler 自定义消息处理函数将 qDebug 等消息输出到 log 文件中

根据所设计的时刻表绘图：

为交通工具设置风险值，当计算一个城市到另一个城市风险值时，需要将其加上

对策略的分析：

将城市看作为点，城市间的路径看作为边，边的权重为现在时间城市之间的最小风险值和城市之间所耗时间两个权重

最少风险策略：

不考虑时间权重，使用 Dijkstra 算法，寻找风险值最小的路径

限时最少风险策略：

考虑时间权重不能超过限制，通过 DFS 深度搜索算法，当时间超过时剪枝，当走到目标城市且风险值更小时，更新

软件开发环境：

Qt，MySQL

总体结构和模块划分

Widget 与 map，MySQL，way 模块单向交互

Map 模块：定义地图子窗口，实现绘制旅客路径

MySQL 模块：实现数据库连接，根据 SQL 语句查找数据并返回 QSqlQuery 类型

Way 模块：定义一个类，用于存放路径的时刻表，包含起止城市、起止时间、交通工具、耗时

Main：实现日志功能

程序文件目录及功能：

mysql.h ——定义数据库连接及查询的头文件

way.h ——定义一个类，用于存放路径的时刻表，包含起止城市、起止时间、交通工具、耗时

map.h ——定义地图子窗口，实现绘制旅客路径的头文件

widget.h ——定义主窗口，实现获取输入、根据不同策略寻找路径，并向地图子窗口传递绘制所需的信息的头文件

main.cpp ——自定义日志输出函数，实现窗口的显示

way.cpp ——实现 way 的初始化

mysql.cpp ——实现数据库连接，根据 SQL 语句查找数据并返回 QSqlQuery

map.cpp ——实现获取主窗口传递的数据，请根据此绘制不同交通工具的路径图

widget.cpp ——实现数据库初始化，时间自动推进，获取输入数据，根据策略找出路径，向子窗口传递绘图数据的功能

map.ui ——地图子窗口及控件

widget.ui ——主窗口及控件

数据库数据说明：

city 中存储各城市风险值

time_table 中存储时刻表

Way 模块：

Way 用于存放路径的时刻表，包含起止城市、起止时间、交通工具、耗时

MySQL 模块：

MySQL 初始化时，会连接到数据库，selectCity 可通过输入的 SQL 语句，在时刻表中查询符合要求的数据，并返回 QSqlQuery 类型

Map 模块：

数据结构

名称	标识符	类型	详细描述
交通工具的类型	type	int	用来描述需要绘图的交通工具的类型
开始城市	from	int	存储绘图时开始城市位置
终止城市	to	int	存储绘图时终止城市位置
现在位置	currentPosition	int [2]	存储绘图时现在位置
目的位置	destination	int [2]	存储绘图时目的位置
城市位置	city	int [10][2]	存储所有城市位置
x 方向单位移动距离	xMove	int	存储绘图时每次计时器超时 x 方向单位移动距离
y 方向单位移动距离	yMove	int	存储绘图时每次计时器超时 y 方向单位移动距离
地图模块计时器	mTimer	QTimer	地图模块计时器
飞机移动	plane_move	void	飞机移动函数
火车移动	train_move	void	火车移动函数
汽车移动	car_move	void	汽车移动函数
自定义析构函数	end	void	自定义析构函数
计时器超时	mTimer_timeout	slot	计时器超时
获取数据	getData	slot	从主窗口获取数据
显示旅客	showP	slot	显示旅客所在位置

总体功能：

当 getData 函数从主窗口获得交通工具、起始城市、终止城市时，根据交通工具的速度和城市之间的距离，计算出每次移动在 x，y 方向上所需移动的距离，计时器每 1s 超时一次，也就是程序中的 6 分钟。在开始时，旅客在起始城市显示，根据交通工具的类型选择移动函数，在此期间，旅客消失，交通工具显示，当到达目的城市时，交通工具消失，旅客显示。

Widget 模块：

输入：

名称	标识符	类型	介质	描述
策略	strategy	int	选择框	储存用户选择的策略
起始城市	fromCity	int	选择框	储存用户选择的出发城市
终止城市	toCity	int	选择框	储存用户选择的目的地
时间限制	timeLimite	int	文本输入框	储存用户输入发时间限制

输出：

名称	标识符	类型	介质	描述
路径输出	plan	Way	文本框	输出旅客路径
预计到达时间	arriveTime	int [3]	文本框	输出旅客预计到达时间
现在时间	now	int [3]	文本框	输出现在时间

数据结构：

名称	标识符	类型	详细描述
数据库	MySQL	MySQL	初始化存储时刻表的数据库
现在时间-天	day	int	现在时间-天
现在时间-小时	hour	int	现在时间-小时
现在时间-分钟	minute	int	现在时间-分钟
时间输出文本	txtContext	QString	以文本形式输出现在时间
策略	strategy	int	输入的策略
起始城市	from	int	输入的起始城市
终止城市	to	int	输入的终止城市
时间限制	timeLimite	int	输入的时间限制
是否按下按钮	pushBotton	bool	是否按下按钮
定时器	fTimer	QTimer	主窗口定时器
子窗口	mapWidget	Widget	子窗口
交通工具的类型	type	int	绘图传递的交通工具的类型
现在起始城市	currentFrom	int	现在起始城市
现在目的城市	currentTo	int	现在目的城市
每个城市的移动策略	plan	Way [10]	Dijkstra 算法所需的每个城市的移动策略
每个城市的到达时间	arriveTime	int [10][3]	Dijkstra 算法所需的每个城市的到达时间
是否成功找到路径	success	bool	是否成功找到路径
暂时存储路径	tempPlan	Way [10]	暂时存储路径，用来更新 plan
旅客路径	path	QStack	旅客路径
画图路径	mapPath	QStack	画图所需的路径
当前最小风险	minCost	double	DFS 算法当前最小风险
所耗时间	costTime	int [2]	单条路径所耗时间
风险值	cost	double	单条路径所需风险值
城市风险值	value	double [10]	存储每个城市的风险值
现在时间	currentTime	int [3]	现在时间
是否经过城市	throughCity	bool [10]	标识城市是否经过
城市距初始城市距离	distance	double [10]	城市距初始城市的风险值
制定路径	Makeplan	void	根据 plan 的内容，寻找路径，并存储在 path 中
寻找策略对应的路径	findWay	void	根据策略选择不同的算法，同时对数据进行初始化
Dijkstra 算法	Djkstra	void	Dijkstra 算法寻找路径
更新城市	updateCity	void	Dijkstra 算法更新城市
深度优先搜索算法	DFS	void	深度优先搜索算法
计算总消耗时间	calculateTotalCost	void	深度优先搜索算法计算总消耗的时间
计算风险值	calculateCost	void	计算单条路径风险值
时间更新	updateCurrentTime	void	定时器超时时，更新时间
定时器超时	fTimer_timeout	slot	定时器超时
按下提交按钮	on_submit_clicked	slot	按下提交按钮，传入数据
按下加速按钮	on_pushButton_clicked	slot	按下加速按钮，时间前进一小时
传递数据	sendData	signal	向子窗口传递数据
显示旅客	showPassenger	signal	子窗口显示旅客

功能：获取输入、根据不同策略寻找路径，并向地图子窗口传递绘制所需的信息，实现数据交换和主要功能

模块设计说明

MySQL 模块

select City 函数算法：

根据传入的 MySQL 语句，在数据库中进行查找，并返回 QSqlQuery 类型

功能:

向 Widget 主窗口传递数据

Map 模块：

plane_move,train_move,car_move 函数算法：

每种交通工具有不同的速度，根据传入的不同交通工具来调用不同函数进行路径绘制

Widget 模块：

updateCurrentTime 函数算法：

每当计时器超时，时间向前移动 6 分钟，并更新文本框数据

findWay 函数算法：

对所用到的数据进行初始化，并根据输入的策略选择不同函数，之后进行 Makeplan 制定路径

Dijkstra 函数算法：

对于起始城市，设置其到达时间，与起始城距离，当前城市，是否经过城市的初始值，当当前城市不是目的城市且没有经过时，寻找距当前城市风险值最小的城市，并更新其到达时间和与起始城市的距离，并标记此城市已经经过，重复以上过程，直到到达目的城市。

updateCity 函数算法：

在数据库中寻找从当前城市出发的时刻表，并一一计算其风险值，并更新 plan 每个城市的移动策略

DFS 函数算法：

在数据库中寻找从当前城市出发的时刻表，先计算其总消耗时间，若时间限制没有超过，则进行下一步，否则直接结束。在时间限制没有超过的条件下，若该城市没有访问过且不是目的城市时，计算风险值，更新到达时间、tempPlan 每个城市的移动策略，并标记该城市已经经过，进行进一步的递归；若在时间限制内且该城市是目的城市，计算风险值，更新到达时间表、tempPlan 每个城市的移动策略，如果风险值比目前最小风险值还要小，则更新 plan 为 tempPlan。

Makeplan 函数算法：

根据目的城市和每个城市的移动策略，反向递归城市的路径，并将其压至 path，mapPath 栈中

输出及绘图处理：

将目的城市的到达时间输出，并按照栈中的顺序出栈，输出策略到解决方案文本框；当当前时间与解决方案中每个城市的出发时间相同时，向 mapWidget 窗口传递交通工具类型、出发城市、到达城市。

使用说明

因为本实验使用 MySQL 及 Qt 实现，所包含的动态链接库比较多，所以没有附上 exe 可执行文件，需要使用源代码编译运行生成可正常使用的程序

数据库使用：

本实验所需的数据库信息在 mysql.cpp 中，默认数据库为 travel_plan，用户名为 root，默认密码为空。

运行程序之前需要在设置的数据库中导入数据，数据文件为时刻表及城市风险值信息。

修改时刻表时需同事修改 time_table 和 time_table_id，且应对照着所画地图添加时刻表，不然画图时会不经过地图上的线路。（为表示简单，起始时间应为整数）

图形化界面使用：

当前时间框从第 0 天 0：0 开始以 10s1 小时代速度推进

策略选择按钮选择策略

出发城市按钮选择出发城市

到达城市按钮选择到达城市

当选择显示最少风险策略时，时间限制输入有效，可输入以小时为单位的限制时间

提交按钮按下会提交输入的信息

加速一小时可在等待时使用，用于缩短等待时间，但是不能在乘客移动时使用

策略输出框在最少风险策略或限时最少风险可以寻找到路径时输出路径，当限时最少风险策略找不到路径时输出“can not find path!”。

到达时间输出框在可以寻找到路径时输出到达时间

范例执行结果及测试情况

根据交通图：

黄色为飞机路线，紫色为火车路径，绿色为汽车路径

数据库中的时刻表：

+-----+--------------+--------------+---------+--------+-----------------------+

| id | from | to | start | end | transpotation |

+-----+--------------+-------------+-----------+-------+-------------------------+

| 1 | 北京 | 上海 | 8 | 9 | 飞机 |

| 2 | 北京 | 广州 | 9 | 10 | 飞机 |

| 3 | 北京 | 南京 | 10 | 11 | 飞机 |

| 4 | 上海 | 北京 | 11 | 12 | 飞机 |

| 5 | 广州 | 北京 | 12 | 13 | 飞机 |

| 6 | 南京 | 北京 | 13 | 14 | 飞机 |

| 7 | 南京 | 上海 | 5 | 7 | 火车 |

| 8 | 上海 | 南京 | 7 | 9 | 火车 |

| 9 | 南京 | 广州 | 9 | 11 | 火车 |

| 10 | 广州 | 南京 | 11 | 13 | 火车 |

| 11 | 广州 | 上海 | 13 | 15 | 火车 |

| 12 | 上海 | 广州 | 15 | 17 | 火车 |

| 13 | 厦门 | 合肥 | 17 | 19 | 火车 |

| 14 | 合肥 | 厦门 | 19 | 21 | 火车 |

| 15 | 深圳 | 合肥 | 5 | 7 | 火车 |

| 16 | 合肥 | 深圳 | 7 | 9 | 火车 |

| 17 | 深圳 | 厦门 | 9 | 11 | 火车 |

| 18 | 厦门 | 深圳 | 11 | 13 | 火车 |

| 19 | 郑州 | 济南 | 13 | 15 | 火车 |

| 20 | 济南 | 郑州 | 15 | 17 | 火车 |

| 21 | 重庆 | 郑州 | 17 | 19 | 火车 |

| 22 | 郑州 | 重庆 | 19 | 21 | 火车 |

| 23 | 济南 | 重庆 | 8 | 10 | 火车 |

| 24 | 重庆 | 济南 | 15 | 17 | 火车 |

| 25 | 南京 | 厦门 | 8 | 11 | 汽车 |

| 26 | 南京 | 厦门 | 14 | 17 | 汽车 |

| 27 | 南京 | 厦门 | 18 | 21 | 汽车 |

| 28 | 南京 | 厦门 | 20 | 23 | 汽车 |

| 29 | 厦门 | 济南 | 8 | 11 | 汽车 |

| 30 | 厦门 | 济南 | 14 | 17 | 汽车 |

| 31 | 厦门 | 济南 | 18 | 21 | 汽车 |

| 32 | 厦门 | 济南 | 20 | 23 | 汽车 |

| 33 | 广州 | 深圳 | 8 | 11 | 汽车 |

| 34 | 广州 | 深圳 | 14 | 17 | 汽车 |

| 35 | 广州 | 深圳 | 18 | 21 | 汽车 |

| 36 | 广州 | 深圳 | 20 | 23 | 汽车 |

| 37 | 深圳 | 重庆 | 8 | 11 | 汽车 |

| 38 | 深圳 | 重庆 | 14 | 17 | 汽车 |

| 39 | 深圳 | 重庆 | 18 | 21 | 汽车 |

| 40 | 深圳 | 重庆 | 20 | 23 | 汽车 |

| 41 | 上海 | 合肥 | 8 | 11 | 汽车 |

| 42 | 上海 | 合肥 | 14 | 17 | 汽车 |

| 43 | 上海 | 合肥 | 18 | 21 | 汽车 |

| 44 | 上海 | 合肥 | 20 | 23 | 汽车 |

| 45 | 合肥 | 郑州 | 8 | 11 | 汽车 |

| 46 | 合肥 | 郑州 | 14 | 17 | 汽车 |

| 47 | 合肥 | 郑州 | 18 | 21 | 汽车 |

| 48 | 合肥 | 郑州 | 20 | 23 | 汽车 |

+----+-------------+-------------+-----------+-------+-------------------------+

最少风险策略

例：寻找上海至济南路径：

可发现输出为：

上海--> 合肥--> 郑州--> 重庆--> 济南

而不是看起来路程最短的：

上海--> 南京--> 厦门--> 济南

因为上海和南京均为 0.9 的高风险城市，而且此路径上时刻表较慢，所以选择上海--> 合肥--> 郑州--> 重庆--> 济南这一路径

例：寻找重庆至上海的路径：

可发现输出为：

重庆--> 郑州--> 合肥--> 上海

而不是

重庆--> 深圳--> 合肥--> 上海等其他路径

在数据库中查看

可发现重庆--> 郑州--> 合肥--> 上海这一路径风险值最低，且总用时更短

限时最少风险策略：

例：寻找北京至重庆的路径

可发现到达时间刚好不超出时间限制

路径为：

北京--> 广州--> 深圳--> 重庆

若缩小时间限制：

则会显示找不到路径