旅行模拟查询系统

设计任务

1 整体描述

旅行模拟查询系统支持 12 个省份之间的旅行模拟查询功能，所有省份如下：湖北，广东，福建，四川，青海，西藏，河南，江苏，山西，黑龙江，北京，河北。城市之间有三种交通工具（飞机、火车、汽车），以及近 100 个不同时间的班次提供给用户进行选择。

2 制定旅行计划

用户可以在任意时刻向系统提出旅行要求（包括起点、终点）。用户可以指定旅行过程中采用的策略（不限时风险最小、限时风险最小、最短时间到达），以便满足用户的不同需求，系统将根据旅客要求为旅客设计路线。

3 旅行模拟

系统可以模拟推进旅客的旅行过程，以图形化界面和文字的形式展示旅客当前位置。在旅行过程中，用户随时可以查询当前时刻旅客所处状态（所在城市，乘坐的交通工具）。

功能需求

1 功能概述

本软件旨在根据旅客的要求设计出行路线并输出，同时系统能模拟旅客所在的地点和状态，为旅客提供能完美的出行计划。

城市之间有三种交通工具（汽车、火车和飞机）相连，某旅客于某一时刻向系统提出旅行要求，系统根据该旅客的要求为其设计一条旅行线路并输出；系统能查询当前时刻旅客所处的地点和状态（停留城市/所在交通工具）。

2 任务需求

2.1 软件数据要求

省份总数不少于 10 个。故选定 12 个省份进行软件设计，省份如下：

湖北、广东、福建、四川、青海、西藏

河南、江苏、山西、黑龙江、北京、河北

各个城市的风险程度不一样，分为低风险、中风险和高风险三种

我将 12 个城市设置成 3 个低风险，3 个中风险，3 个高风险

低风险：福建 西藏 山西

中风险：广东 青海 江苏

高风险：湖北 四川 黑龙江

城市之间有三种交通工具：汽车、火车、飞机

建立汽车、火车和飞机的时刻表（航班表），时刻表中信息包括班次、始发站、终点站、旅行方式、到达时间、出发时间。我们选定 12 个省份之间近 100 次航班表信息存储到本地。

2.2 用户查询要求

用户输入出发城市、目的地城市和旅行策略。

可选择的旅行策略包括：

——不限时最少风险策略：无时间限制，使得乘客的风险最小；

——限时最少风险策略：在规定的时间内乘客的风险最小。

——最短时间到达策略：不管风险值，只要让行程的时间最短。

添加乘客后，用户可以通过按钮输入乘客的 id 来查询乘客目前的状态，并可以用动画演示乘客的旅行过程。

2.3 模拟演示推进要求

旅行模拟查询系统以时间为轴向前推移，每 10 秒左右向前推进 1 个小时；

旅行过程中不考虑城市内换乘交通工具所需时间；

系统时间精确到小时。

2.4 图形化展示旅行过程

用图形界面表示用户的旅行过程，并在地图上动态反映当前行程，以及所使用的交通工具；

2.5 乘客更改路线

乘客可以点击更改路线按钮，实现更改目的地的功能。

总体方案设计

1 开发环境

本系统的开发环境可分为硬件环境与软件环境，分别如下所示：

·硬件环境：

本项目全程开发使用个人电脑，其硬件配置具体如下所示：

计算机类型：商务笔记本电脑

型号： 联想 80XL

处理器： Intel® Core™ i7-7500U CPU @ 2.70GHz(2904 MHz)

内存大小： 12.00 GB

·软件环境：

操作系统：Windows 10 专业版

开发语言：C++

集成开发环境：Qt creator（Qt 5.14.2）

2 系统整体结构及模块划分

系统的模块划分主要为以下部分：以窗口添加乘客模块，计算乘客路径模块，动画演示乘客旅行过程模块，城市模块，查询乘客状态模块，以动画展示某个乘客状态模块，以文件添加乘客模块，时刻表模块，程序主窗口模块，乘客更改路线模块。

上述的九个模块为旅行模拟查询系统所具有的功能模块。这十个模块是系统基本模块，也是满足用户旅行需求、为用户提供良好交互的必要支撑。部分模块由子模块构成，本文仅给出系统的总体说明，进一步细分的模块结构及具体实现未作介绍，详情可查看“各模块设计说明“。

数据结构说明和数据字典

1 数据结构说明

本部分将列举旅行模拟查询系统中使用到的所有基本数据结构，部分数据结构如计数符号本文不作详细说明，详情可参考程序源代码。

本部分除了给出数据结构的介绍以外，还针对各数据结构给出了示例。示例中部分为程序代码中摘出的实际代码，另一部分为了方便说明而书写的伪代码。

1.1 一些宏定义

数据结构：int，float；

存储内容：一些常量的定义。

【示例】

# define maxPassenger 10000  //乘客最大数量
# define maxTimetable 1000   //一天交通工具的最大班次
# define numberOfCity 12		//城市的数量
# define lowRiskCity 0.2     //低风险城市的风险值
# define middleRiskCity 0.5  //中风险城市的风险值
# define highRiskCity 0.9    //高风险城市的风险值
# define planeRisk 9         //乘坐飞机的风险值
# define trainRisk 5         //乘坐火车的风险值
# define busRisk 2           //乘坐汽车的风险值

1.2 乘客信息

·数据结构：结构体，数组；

·存储内容：乘客的基本信息，包括出发时间，起点，终点，旅行的路径以及交通工具，风险值等。

【示例】

struct Passenger		//定义乘客结构体					
{
    QString Number;		//乘客编号					
    QString startPoint;       //乘客的起点
    QString finishPoint;	//乘客的终点
    int startTimeDay;		//乘客的开始要求出发的日期
    int startTimeHour;		//乘客的开始要求出发的时间
    QString travelNum[numberOfCity];	//乘客乘坐的交通工具编号
int strategyType;	//乘客选择策略类型   -1表示最少风险策略  -2表示最短时间到达策略  正数表示限时最少风险策略的时间    
QString Route[numberOfCity]; //乘客从起点到终点要走的路线
    int typeTravel[numberOfCity]; //乘客的旅行方式（0飞机1火车2汽车）
    int cityNumber;		//乘客要走的城市数目
    float minRisk;		//乘客的最小风险值
    int spendTime;             //乘客整条线路花费的时间
    int visitedPlace;          //乘客已经到的城市的数量（用于输出）
    int flag;        //乘客的搭乘状态（0表示等待 1表示搭上交通工具）
};
struct Passenger passenger[maxPassenger];	//乘客信息的结构体数组

1.3 城市数组以及邻接表

·数据结构：数组、结构体，以邻接表的方式来存储城市，并将风险值设成权值；

·存储内容：城市的名字，风险值，可以直达的相邻的城市以及直达的时间和使用交通工具。

【示例】

struct City			//定义城市结构体
{
    QString name;		//城市的名称
    float riskVal;		//城市的风险值
    struct ArcNode* first_ptr;	//第一个表结点的地址,指向第一条依附该顶点的弧的指针
};
struct City city[numberOfCity];	//节点数组
struct ArcNode			//节点
{
    int adjvex;			//数组对应的位置
    struct ArcNode* nextarc;	//指向下一条弧的指针
    float info[24][3];		//权值即风险值(24表示24小时不同的权值，3表示用三种交通工具不同的权值:0飞机1火车2汽车） 例如info[6][0]就表示乘客在6点坐飞机从A城市到B城市的风险值
    int spendTime [24][3];	//乘坐三种交通工具所花费的时间（24表示24小时不同的时间，3表示用三种交通工具不同的权值:0飞机1火车2汽车） 例如spendTime[6][0]就表示乘客在6点坐飞机从A城市到B城市的时间
    QString travelNum[3][24];	//交通工具的编号（班次号） 例如travelNum[0][6]就表示乘客在6点坐飞机从A城市到B城市的班次号
};

1.4 时刻表

·数据结构：结构体，数组；

·存储内容：所有班次的详细安排，所存储的为某一班次的出发城市、目的城市、交通工具、出发时间、抵达时间以及班次号。

【示例】

struct Timetable			//定义时刻表结构体
{
    QString travelNum;			//交通工具的编号（班次号）
    QString travelType;             //交通工具的方式（飞机，火车，汽车）
    QString startPoint;             //交通工具的起点
    QString finishPoint;		//交通工具的终点
    int startTime;  			//交通工具的起始时间
    int finishTime;			//交通工具的终止时间
};
struct Timetable timetable[maxTimetable];	//时刻表信息的结构体数组

1.5 其他的变量

QString id;		//用于查询乘客状态的乘客编号
int DAY = 0;		//日期
int HOUR = 0;		//小时
int SECOND = 0;  //秒（用于动画）
AddTravel * addtravel;      //添加乘客的子窗口
Inquire * inquire;          //查询乘客状态的子窗口
Position * position;        //显示乘客状态的子窗口
cartoon * cartoon_1;        //显示动画的子窗口
change_route * changeRoute; //更改乘客路径的子窗口
int passengerNumber;						//乘客的数量
QString passengerRoute[numberOfCity];	//乘客的路径（DFS用）
int numPlace;								//记录乘客路径上途径的地点数（DFS用）
int spendTime;				//乘客从出发地到目的地的时间（DFS用）
float minimumRisk;			//乘客从出发地到目的地的最低风险值（DFS用）
int visitFlag[numberOfCity];//乘客的旅行城市标记，避免成环0不在1在（DFS用）
QString tempTravelNum[numberOfCity];//交通工具的编号（DFS用）

2 数据字典

此部分主要对本系统中所使用到的关键函数的名称、作用以及数据结构等进行介绍，而中间计算过程所使用的临时变量以及一些非关键变量等本部分不作详细说明。

2.1 关键函数

函数名	返回值类型	作用
AddTravel::getinput(int day,int hour)	void	对话框点击确定添加乘客函数
AddTravel::no_getinput()	void	对话框点击取消不添加乘客函数
find_city(QString cityName)	int	寻找城市所对应的数组序号
find_typeTravel(QString typeTravel)	int	用数字表示交通方式:0 飞机 1 火车 2 汽车
find_cityArr(int startSeq, int finishSeq)	int	在邻接表中寻找，若之前有连线返回 1，否则返回 0
DFS_travel(int startSeq, int finishSeq, int Seq)	void	DFS 深搜对限时最小风险策略进行计算
Dijkstra_risk(int Seq)	void	利用 Dijkstra 算法对最小风险策略进行计算
Dijkstra_time(int Seq)	void	利用 Dijkstra 算法对最短时间到达策略进行计算
arrange_route()	void	对每一个乘客安排路径
count_risk(int Seq)	void	计算风险值并找到最小风险值的路径，存到旅客的结构体数组中
transform_ternary(int num)	int	转换成三进制
set_visit_flag()	void	重置 visitFlag
cartoon::paintEvent\(QPaintEvent *)	void	动画的实现
input_city()	void	通过文件输入城市的名称
updata_info(QString travelNum, int startSeq, int finishSeq, int travelSeq, int startTime, int finishTime)	void	更新权值（风险值）找到比邻接表中更小的风险值则代替，找到比邻接表中更短的时间则代替
set_zero(struct ArcNode* p)	void	初始化 info 和 spendTime
Inquire::search()	void	对话框点击确定根据 id 查询乘客状态函数
Inquire::no_search()	void	对话框点击取消
change_route::change_ok()	void	对话框点击确定更改乘客目的地函数
change_route::change_cancel()	void	对话框点击取消
MainWindow::outputExe()	void	窗口输出乘客的旅行路线以及交通工具
MainWindow::outputFile(int hour,int day,int type)	void	日志文件的输出
newWight::paintEvent\(QPaintEvent *)	void	查询动画的实现
get_X(QString city)	int	返回各地的 x 坐标
get_Y(QString city)	int	返回各地的 y 坐标
input_passenger()	int	通过文件输入乘客的信息
Position::search(int day, int hour)	void	同步时间函数
input_timetable()	void	文件输入时刻表
transform(QString tran_a)	int	通过编号找到时刻表

各模块设计说明

1 以对话框形式添加乘客模块

1.1 对话框的 UI 界面设计

1.2 通过对话框添加乘客函数

void AddTravel::getinput(int day,int hour)

函数效果：对话框点击确定添加乘客函数

实现方法：通过 UI 界面输入的数据，将相应的乘客信息（出发时间，起点，终点，乘客 ID，策略）添加到全局的乘客数组中，根据乘客所选的策略调用 DFS_travel 函数或者 Dijkstra_risk 函数或者 Dijkstra_time 函数，计算出乘客的相应路径并存储在乘客数组中，最后初始化 UI 界面。

void AddTravel::no_getinput()

函数效果：对话框点击取消不添加乘客函数

实现方法：初始化 UI 界面即可。

2 计算乘客路径模块

2.1 利用 DFS 深搜找到城市 A 到 B 的所有路径进行筛选

void DFS_travel(int startSeq, int finishSeq, int Seq)

函数效果：DFS 深搜找到所有城市 A 到 B 的路线

实现方法：

void DFS_travel(int startSeq, int finishSeq, int Seq) //DFS 深搜

{

先令p为该城市邻接表的第一个指针

对起始城市进行标记，防止成环

IF 起点和终点符合旅客的条件则计算风险值并且 numPlace <= 4（numPlace 是从起点出发到达终点所要经过的城市数目，比如 广东-> 黑龙江的实际路线是 广东-> 福建-> 黑龙江则其 numPlace=2，numPlace <= 4 是为了优化程序，超过 4 个则默认不是最优）

Then 就计算该条路径的风险值以及时间花费，与数组中所存的路径相比较，如果优于原先路径则代替（调用 count_risk（）函数）

while (p 不是空指针时)

{

int j = p->adjvex;

if (visitFlag[j] == 0)

{

DFS_travel(j, finishSeq, Seq); //递归

}

p = p->nextarc;

}

将标志重置，表示该城市不在路径之内

}

该算法的时间空间复杂度分析：该算法的实现就相当于枚举出所有从城市 A 到城市 B 的路径，对其进行筛选。该算法的时间复杂度与城市数量和城市路线有关，假设城市数量为 n，在最差情况下，每个城市都和其他城市有直达的交通工具，该算法设定一个起点后，就相当于对其他的 n-1 个城市进行全排列，遍历的时间复杂度为 O（(n-1)!），而且对每个满足条件的路径还要进行计算筛选，尽管做了 numPlace <= 4 才能进入 count_risk（）函数的优化，将筛选算法的时间复杂度降低到常数（O（3 的 4 次方）），但是在实际运用当中，该算法运行起来还是比较吃力。

2.2 Dijkstra 算法求路径

2.2.1 void Dijkstra_risk(int Seq)

函数效果：用于不限时最小风险值策略的计算

函数实现：

以乘客的起点 v 为源点

1)初始化辅助数据结构：(i=1…n) O(n)

1.1) flag[i]=0；

1.2) 通过邻接表，对 dist[i]赋值；

1.3) 若可以通过邻接表找到，则 dist[i]=v，否则 dist[i]=-1

2)确定源点自身的最短距离: flag[v]=1, dist[v]=0 O(1)

3)循环确定其余 n-1 个顶点到 v 的最短距离： O(n2)

3.1)找出 D 中未被确定最短距离的顶点中路径最短的顶点，

 设该顶点序号为k，且dist[k]=min；

3.2)若 min 为-1，退出本算法；

3.3)赋值 flag[k]=1；

3.4)调整尚未被确定最短距离的顶点的估算距离：(j=1…n)

 若flag[j]=0 且 dist[j]>dist[k]+ p->info

 则dist[j]=dist[k]+ p->info，prev[j]=k

4)根据乘客的信息，找到相应的起点到终点的最短路径，并赋值给乘客的结构体数组中

2.2.2 void Dijkstra_time(int Seq)

函数效果：用于最短时间到达策略的计算

函数实现：与上述 Dijkstra_risk 基本相同，将判断条件替换成时间即可。

该算法的时间空间复杂度分析：假设城市的数量为 n，则该算法的时间复杂度是 O(n2)，空间复杂度也是 O(n2)，相比于弗洛伊德算法，迪杰特斯拉算法对于求两点的最短路径有着更好的时间复杂度，而这两个算法的空间复杂度相同都是 O(n2)。弗洛伊德算法的时间复杂度是 O(n3)，该算法求出任意两点之间的最短路径，但是对于我所设计的旅行系统来说，只要求出特点两点之间的最短路径即可，所以我选择了迪杰特斯拉算法来求最短路径。在实际情况的运用中，迪杰特斯拉算法也可以高效准确的求出旅行路线。

2.3 用数字表示交通方式

int find_typeTravel(QString typeTravel);

函数效果：用数字表示交通方式:0 飞机 1 火车 2 汽车，方便程序遍历

函数实现：判断 if typeTravel 是飞机则返回 0，同理火车返回 1，汽车返回 2

2.4 重置访问城市标记

void set_visit_flag();

函数效果：重置 visitFlag[]数组都为 0

函数实现：通过一个 while 循环重置 visitFlag[]数组

2.5 将 10 进制转换成 3 进制

int transform_ternary(int num);

函数效果：将 10 进制转换成 3 进制（用于旅行方式的遍历）

函数实现：

int transform_ternary(int num) //转换成三进制的形式

{

int i = 1, ternary = 0;

while (i 小于等于 num)

i = i * 3;

i = i / 3;

while (i 不等于 0)

{

ternary = ternary * 10 + num / i;

num = num - (num / i) * i;

i = i / 3;

}

return ternary;

}

2.6 为每一个文件输入的乘客安排路径

void arrange_route()；

函数功能：该程序既可以支持对话框输入，也可以支持文件输入，该函数用于对文件输入的乘客安排路径

函数实现：利用 while 循环对每一个乘客调用相应函数进行计算。

2.7 计算风险值并找到最小风险值的路径

void count_risk(int Seq);

函数效果：计算风险值并找到最小风险值的路径，存到旅客的结构体数组中

函数实现：

void count_risk(int Seq)

{

将乘客的旅行路径存在 tempCity 数组中

while (type < 3) //第一次的出行方式进行遍历

{

while (i < 24)			//第一次的出行时间进行遍历

{

 对剩下的城市的旅行方式进行遍历，方法是利用三进制的加法，

例如从 000 加到 222，对 4 个城市之间的三种交通方式进行遍历，找到对应的交通工具则按照最早的班次出发，并计算出相应的风险值和花费的时间

每次遍历完，判断是否小于存储的风险值，若小于则代替

  i++;

}

type++;

}

}

3 城市模块

3.1 城市输入

void input_city();

函数效果：用文件输入城市的名字以及高、中、低风险

函数实现：读取文件，将城市名称以及相应的风险值存在城市结构体数组当中。

3.2 初始化风险值以及旅行时间

void set_zero(struct ArcNode* p);

函数效果：初始化结构体数组中的 info 和 spendTime

函数实现：利用 while 循环初始化

4 以文件添加乘客模块

4.1 以文件方式添加乘客

int input_passenger();

函数效果：以文件方式添加乘客

函数实现：通过文件输入，将乘客信息（出发时间，起点，终点，乘客 ID，策略）添加到全局的乘客数组中。

5 时刻表模块

5.1 以文件方式添加时刻表

void input_timetable();

函数效果：以文件方式添加时刻表并创建相应的邻接表

函数实现：

void input_timetable() //输入各个城市之间的交通工具,并用邻接表存储城市图

{

打开文件

while(!file.atEnd())

{

将时刻表存储于timetable数组中

建立邻接表

调用updata_info（）函数更新权值（风险值）

}

关闭文件

}

5.2 在邻接表中寻找对应城市

int find_cityArr(int startSeq, int finishSeq);

函数效果：在邻接表中寻找，若之前有连线返回 1，否则返回 0

函数实现：

int find_cityArr(int startSeq, int finishSeq)

{

if (city[startSeq].first_ptr == NULL)

return 0;

else

{

遍历city[startSeq]的邻接表，若有则返回1 ，没有返回0 

}

}

5.3 寻找城市所对应的数组序号

int find_city(QString cityName);

函数效果：寻找城市所对应的数组序号

函数实现：利用 while 循环遍历 city 数组，若 city[].name == cityName,则返回该数组的下标。

5.4 更新权值

void updata_info(QString travelNum, int startSeq, int finishSeq, int travelSeq, int startTime, int finishTime);

函数效果：输入一个班次即更新邻接表所对应的权值（风险值），邻接表中的 info[24][3]表示城市 A 到 B 24 小时不同交通工具的风险值，若无交通到达则设为-1

函数实现：

void updata_info(QString travelNum, int startSeq, int finishSeq, int travelSeq, int startTime, int finishTime)

{

找到出发点和终点的邻接表

根据时间表对其中的风险值以及花费时间进行计算

若找到比邻接表中更小的风险值则代替

若找到比邻接表中更短的时间则代替

}

5.5 根据编号找到班次

int transform(QString tran_a 函数功能：根据编号找到班次

函数实现：利用 while 循环对 timetable 数组进行遍历，若班号相等则返回相应的数组下标。

6 程序主窗口模块

6.1 主窗口的 UI 设计

6.2 主模块的按钮绑定

//按退出程序按钮退出程序
    connect(ui->pushButton_3,&QPushButton::clicked,[=](){
        this->close();
    });
    //将按钮1与添加乘客绑定
    connect(ui->pushButton,&QPushButton::clicked,[=]()mutable{
        timer->stop();
        if( addtravel->exec() == AddTravel::Accepted )//点击确定
        {
            addtravel->getinput(day,hour);
            outputExe();
        }
        else
        {
            addtravel->no_getinput();
        }
        timer->start(100);
    });
    //将按钮2与查询乘客状态绑定
    connect(ui->pushButton_2,&QPushButton::clicked,[=]()mutable{
        QString output;
        timer->stop();
        if( inquire->exec() == Inquire::Accepted )
        {
            position->show();
        }
        else
        {
            inquire->no_search();
            timer->start(100);
        }
    });
    
    //将按钮4与显示动画绑定
    connect(ui->pushButton_4,&QPushButton::clicked,[=]()mutable{
        cartoon_1->show();
});
//将按钮5与更改路线绑定
    connect(ui->pushButton_5,&QPushButton::clicked,[=]()mutable{
        timer->stop();
        if( changeRoute->exec() == change_route::Accepted )
        {
            changeRoute->change_ok();
            timer->start(100);
        }
        else
        {
            changeRoute->change_cancel();
            timer->start(100);
        }
    });
}

6.3 主窗口的输出函数

void outputExe();                           //添加乘客输出函数
void outputFile(int hour,int day, int type);//日志文件的输出函数

6.4 主窗口的构造函数

MainWindow::MainWindow(QWidget *parent)
    , ui(new Ui::MainWindow)
{
    ui->setupUi(this);
    int i = 0, j = 0;
    input_city();							//通过文件输入城市信息并用数组存储
    passengerNumber = input_passenger();	//输入乘客信息
    input_timetable();						//输入时刻表信息，并完成城市的邻接表
arrange_route();						//对文件输入的乘客进行计算
}

7 查询乘客状态模块

7.1 查询乘客的 UI 界面

7.2 查询窗口

void Inquire::search()

函数效果：对话框点击确定根据 id 查询乘客状态函数

实现方法：通过 UI 界面输入的数据，将 id 传入查询，最后初始化 UI 界面。

void Inquire::no_search()

函数效果：对话框点击取消

实现方法：初始化 UI 界面即可。

8 以动画展示某个乘客状态模块

8.1 以动画展示某个乘客状态模块的 UI 界面

8.2 时钟更新

void Position::search(int day, int hour)

函数功能：实现动画窗口与主窗口的时间一致

函数实现：

void Position::search(int day, int hour)
{
    QString a, b;
    a = QString::number(day);
    b = QString::number(hour);
    ui->time->setText(b);
    ui->day->setText(a);
    update();
}

8.3 动画实现

void newWight::paintEvent(QPaintEvent *)

函数功能：实现以动画效果查询乘客

函数实现：

void newWight::paintEvent(QPaintEvent *)//动画实现
{
	//先画地图作为背景
    QPixmap pixmap_map(":/new/prefix1/image/map1111.png");
    QPainter llpainter(&pixmap)；
   //找到要查询的乘客
//找到城市A,B的X,Y坐标
    llpainter.drawLine(x_1, y_1, x_2, y_2);//画线
    //交通工具
    QPixmap pixmap_plane(":/new/prefix1/image/plane.gif");
    QPixmap pixmap_train(":/new/prefix1/image/train.gif");
    QPixmap pixmap_bus(":/new/prefix1/image/bus.gif");
    QPixmap pixmap_position(":/new/prefix1/image/position.png");
    //画出交通工具移动的动画
        painter.drawPixmap(travel_x - 10, travel_y - 10, pixmap);
}

8.4 各地的坐标

int get_X(QString city)

int get_Y(QString city)

函数功能：传入城市的名字返回该城市在地图上的 X 坐标和 Y 坐标

9 动画演示所有乘客旅行过程模块

9.1 动画演示函数

void cartoon::paintEvent(QPaintEvent )

函数实现：对每一个未到达的乘客都通过动画演示

void cartoon::paintEvent(QPaintEvent *)     //动画的实现
{
    QPixmap pixmap_map(":/new/prefix1/image/map1111.png");
    QPixmap pixmap = pixmap_map.scaled(791, 721);   //背景地图
    while( j < passengerNumber )                    //对每个乘客都画 
{
//得到城市A,B的X,Y坐标
        x_1 = get_X(passenger[j].Route[passenger[j].visitedPlace]);
        y_1 = get_Y(passenger[j].Route[passenger[j].visitedPlace]);
        x_2 = get_X(passenger[j].Route[passenger[j].visitedPlace + 1]);
        y_2 = get_Y(passenger[j].Route[passenger[j].visitedPlace + 1]);
        llpainter.drawLine(x_1, y_1, x_2, y_2);
        QPainter painter(this);
        j++;
    }
    llpainter.end();
    while( j < passengerNumber )                //添加交通工具
    {
        QPixmap pixmap_plane(":/new/prefix1/image/plane.gif");
        QPixmap pixmap_train(":/new/prefix1/image/train.gif");
        QPixmap pixmap_bus(":/new/prefix1/image/bus.gif");
        QPixmap pixmap_position(":/new/prefix1/image/position.png");
        painter.drawPixmap(travel_x - 10, travel_y - 10, pixmap_type);
//画出交通工具的移动
        j++;
    }
}

10 乘客更改路线模块

10.1 乘客更改路线模块的 UI 界面

10.2 更改乘客路线函数

void change_route::change_ok()

函数效果：对话框点击确定更改乘客路线函数

实现方法：通过 UI 界面输入的数据，根据相应的乘客信息（更改路线的终点，乘客 ID，策略）改变全局的乘客数组，根据乘客所选的策略调用 DFS_travel 函数或者 Dijkstra_risk 函数或者 Dijkstra_time 函数，计算出乘客的相应路径并重新存储在乘客数组中，最后初始化 UI 界面。

void change_route::change_cancel()

函数效果：对话框点击取消更改乘客路线函数

实现方法：初始化 UI 界面即可。

范例执行结果

1 范例执行结果

1.1 不限时最少风险策略策略范例

添加乘客如下

策略类型	旅行需求	计算结果
不限时最少风险	·出发城市：黑龙江·目的城市：广东	出发时间：0 日 5 时抵达时间：1 日 9 时行程耗时：28 小时

表 1

·范例执行结果图：

对应时间表中：

班次 08 51 5A，对应正确。

1.2 限时最少风险策略范例

添加乘客如下

策略类型	旅行需求	计算结果
限时最少风险策略	·出发城市：福建·目的城市：北京·限时：30 小时	出发时间：0 日 9 时抵达时间：1 日 12 时行程耗时：27 小时

范例执行结果图：

对应时间表中：

班次 1A 1D ，对应正确。

1.3 最短时间到达策略范例

添加乘客如下：

策略类型	旅行需求	计算结果
最短时间到达策略	·出发城市：黑龙江·目的城市：广东	出发时间：0 日 6 时抵达时间：0 日 21 时行程耗时：15 小时

范例执行结果图：

对应时间表中：

班次 09 2D 44 ，对应正确。该乘客的起点终点与策略 1 相同，但是输出结果不一样，一个是追求最小风险值，一个是追求时间，符合算法的预期。

2 测试情况说明

2.1 用户需求提交

首先输入旅客的要求，包括旅客 ID、出发地、目的地、旅行策略、然后点击按钮“OK”，此时系统将会规划好的旅行方案，并将用户的旅行计划输出到主窗口。经过对于不同旅客的测试工作，各种旅行方案均可以正常运行，无任何异常情况。
对于输入中出现的各种不合法情况，系统会及时地给出提示信息，并将状态还原到上一合法输入状态。经过测试，各种不合法的输入系统都会向用户发出提示信息，告知用户问题所在并提示修改。

2.2 旅行路线规划与展示

系统会伸展窗口，在左侧的旅行方案文本框中输出相应的旅行方案。我们针对每一种不同的用户策略需求进行了大量测试。测试结果显示，系统所给出的旅行方案与最优方案的结果差别甚微，满足预期，验证了方案输出和路径规划算法均通过测试，进一步说明算法是比较可靠的。

2.3 用户当前状态查询测试

在行程开始后，点击窗口右边的“乘客查询”按钮，弹出查询对话框，输入要查询乘客的ID后，会弹出另外一个对话框，该对话框分为两部分，对话框左侧用地图的方式形象地展示了用户当前所处的城市。对话框的右侧显示的是用户为完成的行程安排（关键事件），这部分内容会随着用户的位置推进不断刷新。经过大量测试，此部分显示的用户状态与行程安排一切正常，符合预期。

2.4 以动画的方式演示全部乘客的旅行状态

先预先添加两个不同的乘客，使得他们在时间上有交集，按下右边的“动画演示”按钮，程序会自动弹出对话框，以动画的方式演示这两名乘客的旅行状态图。经过测试和检查，动画演示的与实际情况一致。

2.5 乘客更改路径的功能

先预先添加一个的乘客，该乘客的信息如下

主窗口的输出如下：

点击主窗口右侧的更改路线按钮，并输入信息如下：

点击确认后主窗口输出如下，表示该乘客更改路线成功！查看动画和输出后，符合预期。

3 小结

根据以上的范例执行结果以及测试情况说明可以看出，本系统良好地实现了以下功能：

1.以时间为轴将用户旅行过程向前推进的功能；

2.旅客以 3 种不同策略旅行的功能；

3.程序在地图上动态反映出旅客旅行过程的功能；

4.实时查询旅客状态的功能；

5.多乘客共同添加的功能。

6.乘客更改路径的功能。

用户使用说明

1 引言

1.1 编写目的

为了帮助用户了解该旅行模拟查询系统的功能，使用该系统进行旅行路线的规划，模拟推演旅行的路径过程，特编写本用户使用说明书。

1.2 项目背景

今年疫情袭击了全球。在中国疫情爆发的时间正好在春节前夕，很多劳动者已经回到了家乡，随着疫情得到有效的控制，各地有序推进复工复产，人们需要回到工作岗位上。但是在回去途中仍然有一定的风险，我开发的旅行模拟查询系统可以精确计算不同路径的风险值，为乘客安排一个相对来说风险值最小最安全的旅行路径。

我希望通过开发旅行模拟查询系统，对人们在疫情条件下回岗工作时将会面临的一些问题进行整合、对可能影响问题的部分因素进行提取分析；针对该需求进行计算与求解，进而向用户推荐可靠的旅行方案，并使用图形界面模拟大致的旅行过程，最终达到为用户解决困难规划问题的目的。

1.3 软件功能

本软件系统可在用户选取好城市以及策略后，为旅客用户提供一条恰当的旅行路线以及具体行程安排。

除计算并生成旅行安排外，本软件还具有旅行模拟功能。该功能能够实时模拟用户当前旅行进度，为用户提供文字以及图形化模拟过程。

2 使用说明

2.1 运行环境配置需求

本软件可运行在 PC 及其兼容机上，运行的计算机需搭载 Windows98 以上操作系统，由于本软件所需计算机的性能并不高，当今市场上较为主流的计算机都能够支持本系统的运行，故对计算机的 CPU、内存等配置不作严格要求。

2.2 系统功能使用介绍

① 本软件可通过用户输入或下拉选择框的方式对自己的需求进行输入操作，而软件系统输出的旅行方案则由文本框中的文字以及图片体现；

② 本软件的系统时间推进为每 10 秒钟代表 1 个小时，系统时间精确到小时；

③ 本软件可采取的策略为“不限时风险最少”、“限时风险最少”以及“最短时间到达”；

④ 本软件通过文本形式以及图形化界面向用户提供旅行全过程模拟功能，用户可实时查看当前旅行状态，包括所在班次、城市等。

3 运行示例

① 添加乘客功能运行示例

（1）首先在主页面旁点下“添加乘客”按钮，弹出的窗口如图所示：

（2）填写对应的旅客 ID,起点，终点，旅行策略。填写好后，点击“OK”按钮，

（3）最终得出的旅行方案将会输出并显示在主页面的方框中。

（4）错误情况

对于输入中出现的各种不合法情况，系统会及时地给出提示信息，并将状态还原到上一合法输入状态。经过测试，各种不合法的输入系统都会向用户发出提示信息，告知用户问题所在并提示修改。

② 查看当前用户状态功能运行示例

（1）在成功提交方案后，点击“乘客查询”按钮。

（2）系统将自动弹出如下窗口，要求输入要查询乘客的 ID

输入乘客 ID 001 并点击 OK

（3）系统将会自动弹出改乘客目前的状态，并用动画实时更新，在右框有该乘客状态的文字描述

③ 动画演示功能运行示例

（1） 预先添加两个乘客

乘客 1：从四川出发到湖北，采用限时最小风险策略，限时为 14 小时

乘客 2：从黑龙江出发到广东，采用不限时最小风险策略

主页面框中提示乘客添加成功，并给出了两个乘客的最佳路径

（2）点击“动画演示”按钮，弹出窗口，实时用动画演示旅客的状态

④ 乘客更改路线示例

先预先添加一个的乘客，该乘客的信息如下：

主窗口的输出如下：

点击主窗口右侧的更改路线按钮，并输入信息如下：

点击确认后主窗口输出如下，表示该乘客更改路线成功！

⑤ 退出程序功能运行示例

点击“退出程序”按钮即可退出程序

评价和改进意见

1 系统评价

1.1 软件交互性良好

① 系统界面精简细致，用户操作简单且易于上手；

② 旅行计划以及模拟展示界面美观，系统不但会给出详细文字说明，并且用户在旅行过程全程可使用地图显示功能实时查询当前状态，包括所在位置/班次，给用户良好的使用体验；

1.2 功能完善

用户可以自由选择出发地、目的地，并自行选定旅行策略来获得旅行方案，还可以中途更改旅行的目的地。对于大部分用户需求，系统均能够自动计算并给出合理的旅行方案；

系统能够图形化模拟旅行过程。用户可在客户端通过查看地图的方式，直观地了解自己当前的旅行状态，包括所处位置、所在班次或是所在城市。

程序可以输出文本文档（后缀为.txt）格式的用户日志，记录了乘客的添加以及不同时间的旅行状态。

1.3 算法的复杂度

DFS 深搜算法评价：该算法的实现就相当于枚举出所有从城市 A 到城市 B 的路径，对其进行筛选。该算法的时间复杂度与城市数量和城市路线有关，假设城市数量为 n，在最差情况下，每个城市都和其他城市有直达的交通工具，该算法设定一个起点后，就相当于对其他的 n-1 个城市进行全排列，遍历的时间复杂度为 O（(n-1)!），而且对每个满足条件的路径还要进行计算筛选，尽管做了 numPlace <= 4 才能进入 count_risk（）函数的优化，将筛选算法的时间复杂度降低到常数（O（3 的 4 次方）），但是在实际运用当中，该算法运行起来还是比较吃力。

Dijkstra 算法评价：假设城市的数量为 n，则该算法的时间复杂度是 O(n2)，空间复杂度也是 O(n2)，相比于弗洛伊德算法，迪杰特斯拉算法对于求两点的最短路径有着更好的时间复杂度，而这两个算法的空间复杂度相同都是 O(n2)。弗洛伊德算法的时间复杂度是 O(n3)，该算法求出任意两点之间的最短路径，但是对于我所设计的旅行系统来说，只要求出特点两点之间的最短路径即可，所以我选择了迪杰特斯拉算法来求最短路径。在实际情况的运用中，迪杰特斯拉算法也可以高效准确的求出旅行路线。

1.4 系统整体性能较高

对于用户需求，我设计的软件将直接面对 NP 问题，对任何旅行需求直接进行暴力求得最优解并不现实，意义不大，因此我在对于最小风险策略和最短时间到达策略的乘客使用了迪杰特斯拉算法，将时间复杂度和空间复杂度控制在 O(n2)

。对于限时最小风险策略的乘客，由于迪杰特斯拉算法求得路径的时间可能会超过乘客所提的要求时间，因此我使用了 DFS 算法，在此基础上，我还加了一个判断条件，即当遍历的路径所经过的城市个数大于等于 5 个时，就不做风险计算，默认该路径不是旅客的最优路径。这样既优化了程序的性能，又对最后的结果没有影响。在层层递进、不断优化的过程中，最终我设计的主要算法的效率是非常高的。

经过大量测试，系统主要算法在各类需求上的运行情况均非常好，其结果也和提前暴力求解得到的结果比较接近。对于系统的负载能力，测试结果表明，旅行过程的地图模拟功能上，即使乘客数量较多，但软件依然没有表现出丝毫卡顿的现象，根据测试运行时的实际情况，本系统的负载能力应当是比较高的。

2 改进意见

2.1 模块划分不够合理

在设计初期，模块的功能划分应该进一步明确，使各个模块之间的功能相互独立，减少彼此之间的关联性，既便于软件的编写，也便于后期的维护工作。由于缺乏开发经验，在以前也没有系统性地学习过面向对象开发程序的相关课程，因此在编写时更多是采用了面向过程的思想，对于面向对象程序设计思想很少采用，这便导致各个模块之间不够独立，因此在软件的编写过程中使用了较多的全局变量进行参数的传递，虽然对于本次课程设计没有过大影响，但这样的做法不利于大型系统的开发与维护。

2.2 算法效率仍需优化

即使我对系统的主要算法进行了大量的改进与优化，但当城市的数量过多，班次过多的情况下，对于主要策略的算法在计算上还是略有延迟，不能够做到很短时间内便求得结果。

这不利于系统的扩展，比如策略增加、可选途经城市数量增加等，因此应当寻找效率更高的算法，或者可把算法修改为一些启发式算法，比如可以把目光转向模拟退火算法(SA)、遗传算法(GA)、蚁群算法(ACO)、人工神经网络(ANN)等。

♻️ 资源

大小： 13.4MB
➡️ 资源下载：https://download.csdn.net/download/s1t16/87415786