校园导航系统数据结构

系统概述

1.开发环境：windows 10，Clion2022

2.开发语言：C++

设计内容：设计学校的平面图，至少包括10个以上的场所，每两个场所间可以有不同的路，且路长也可能不同，找出从任意场所到达另一场所最短路径，以及从任意场所到达所有场所的最短路径。

图1-1 学校平面图设计

（1）地点设置介绍：如图1-1所示，设计图共计16个场所，并进行了编号（从0开始）；

（2）顶点间的距离值：各顶点间距离值如图1-1所示,单位为米。

4.用户需求：

图1-2 菜单

图1-2展示了本程序初步设计的菜单，通过命令行实现用户交互，基本功能如下：

a)显示校园平面图：打印校园平面图；

b)两地点间最短路径：由用户输入起点、终点，并输出最短距离值与最短路径；

c)校园导航：由用户选择当前位置，输出“从当前位置开始，到达所有场所，最终返回当前位置”的最短距离、路径；

d)留下评论：读取用户输入评论，写入文件；

e)查看评论：从文件中读取评论并打印。

5.设计思想：

a)图的存储：将校园地图通过邻接矩阵进行存储；

b)两地点间最短路径：在初始化时，通过Dijkstra算法计算出任意两点间的最短距离、路径，用户使用该功能时只需查表并输出即可；

c)校园导航：本质是非完全图，允许重复访问的旅行商问题。通常的旅行商问题是NPC问题，并且要求完全图，非完全图的求解较难。本次系统设计通过将非完全图转化为完全图，然后使用状态压缩动态规划解决旅行商问题，达到本功能的近似求解。经过学习了解，此种方法不一定能得到最优解，但本人在网上尚未找到权威资料以解决本问题。

二、系统总体设计

2.1用户交互设计

图2-1 用户交互

图2-1为用户交互流程图，其设计了一个简单循环，循环中获取用户输入、解析并执行，执行操作后进行下一次循环（或退出程序）。

2.2图操作模块设计

图操作模块主要针对“两地点间最短路径”、“校园导航”两大功能进行设计。

由于程序功能相对简单，因此图操作模块直接用结构化设计思想进行实现，即使用全局变量、函数的形式实现即可。

三、详细设计思路及算法

3.1 两地点间最短路径（Dijkstra算法）

Dijkstra算法的核心流程如下：

对于图G，顶点为V（v0-vn），边为E，假设求点v0到所有顶点的最短距离（路径），

初始化：建立两个集合S，T。S表示已求得最短距离的点集合，T表示未求得最短距离的点集合，初始时S={v0}，T=V-S；

从T中取出距离起点v0最近的点，假设为vi，将其放入S；

以vi为桥梁，更新T中到达起点v0的距离；

重复2、3直到没有T为空或无可达点（距离为无穷）。

图3-1 例图（来源：网络）

以图3-1为例，假设起点为A，

初始时，S={A(0)}，T={B(2), C(∞), D(6)}；

从T中选出最近点B，加入S，则S={A(0), B(2)}，T={C(∞), D(6)}；

以B为桥梁，更新T中的距离，例如对于T中D，AD=6 < 4 =AB+BD，因此更新T={C(5), D(4)};

以此类推，运行至T为空或无可达点即可。

如此即可求得A点到各点的最短距离，而求路径时，只需额外使用一个数组pre，在更新T时记录结点前驱即可，例如上面更新D时，记录pre[D]=B，然后从pre倒推即可得到最短路径。

3.2 校园导航（TSP动态规划）

前面提到非完全图的TSP问题并未找到权威解法，因此本程序设计将非完全图转化为完全图，然后使用状态压缩动态规划求解TSP问题：

非完全图转化为完全图：转化方式为若两点之间无边，则使用Dijkstra算法求出最短路径作为替代边；

动态规划求解TSP问题。

TSP问题的定义是从某点出发，经过所有点仅一次，最终回到起点，暴力求解的复杂度为n!，使用动态规划可将复杂度变换为2n×n2。

图3-2 TSP动态规划定义（来源：网络）

图3-2展示了TSP动态规划递归公式。

动态规划核心在于理解递归公式，图3-2中的TSP(c1, C, ci)表示从c1出发，经过集合C中所有城市一次，最终到达ci的最短路径。那么TSP(c1, V, c1)即为待求解，其中假设c1为起点，V为所有城市集合。

图3-3 TSP例图（来源：网络）

图3-4 第二层递推计算（来源：网络）

而递归公式方面，举例说明，TSP例图如图3-3所示，假设起点为c1，则第二层的计算如图3-4所示，可以看到第二层计算依赖于第一层（即C集合长度为1）。

而状态压缩动态规划只是动态规划的一种实现方式，在本实验中，核心在于使用二进制位来表示集合C，由于校园场所设计为16个，因此使用16位即可表示集合C，第i位为0表示集合C不包含场所0，为1则表示集合C包含场所0.

四、主要函数详细设计

4.1 用户交互的详细设计

图4-1 用户交互代码实现

如图4-1所示，用户交互的核心是一个while循环，在循环中，

首先使用getline函数读取用户一行输入，并进行简单的输入检查；

根据用户输入执行操作：本程序设计为输入序号命令即可执行相应操作，例如输入2可执行“两地点间最短路径”操作。

在各操作执行中，便是程序核心逻辑实现。

3.2 图操作的详细设计

图4-2 代码结构

图4-2展示了代码结构，其中graph.h为图相关操作的实现。

在graph.h中，通过全局变量、函数的形式定义了校园场所数组、校园场所图邻接矩阵、两点间最短距离、两点间最短路径、Dijkstra函数、TSP函数等，其中提供了InitGraph函数，实现了图的初始化，而main.cpp中的主函数只需调用此函数即可完成初始化。

图4-3 InitGraph函数

图4-3中，InitGraph函数首先对邻接矩阵进行初始化，然后使用Dijkstra计算两点之间的最短距离、路径，并加以存储，之后通过查表可直接得到最短路径。

另外，在使用Dijkstra计算最短距离、路径时，还将graph补全为完全图，存储于cgraph中，用于TSP函数实现。

图4-4 Dijkstra函数

图4-4为Dijkstra函数代码实现，其核心逻辑与3.1小节叙述相符合。

可以看到，图4-4中，使用map而非数组来存储集合S、T，以更好地贴合Dijkstra算法，优点是便于理解。

图4-5 main函数两地点间最短路径处理

图4-5展示了main函数中，对于两地点间最短路径操作的处理，首先接收用户输入的起点、终点，然后查表得到最短距离、路径，能查表的原因便在于初始化时已使用Dijkstra计算得到任意两点间的最短距离、路径。

图4-6 TSP函数代码实现

图4-6中，TSP函数整体实现逻辑相对复杂了，因为用到了状态压缩动态规划。

核心在于搞清楚dp[s][t]的意义，其表示从start出发，经过了s中为1的场所，最终到达t的最短路径，后面的逻辑便是将s从状态000…000（16个0）枚举到状态111…111（16个1），依照递推公式求解dp[s][i]（i∈[0, 15]）。

注意到dp[s][i]，i从0到15中，部分i值是无效的，因为s中场所i必须为1（因为最终到达了i）；另外，当s中包含start时，只有dp[s][start]有效，因为要求场所只经过一次。

图4-7 TSP函数代码实现-续

如图4-7所示，当dp求解完成时，则已获取到了结果集、路径集，通过简单的倒推即可得到待求路径。需注意的是，由于求得路径是在补全后的完全图基础上得到的，因此当path中，场所i到场所i+1实际上并没有边直接相连，则在打印时需打印Dijkstra求得的最短路径（场所i到场所i+1）。

五、系统功能实现效果

系统功能实现效果截图

1.图5-1展示了程序基础界面，进入程序后，首先打印了菜单，然后类似于命令行交互，打印命令提示符“nav>”，等待用户输入。

图5-1 基础界面

2.图5-2展示了操作1，校园平面图

图5-2 校园平面图

3.图5-3演示了操作2，两地点间最短路径，通过图1-1进行检查，可知结果正确。

图5-3 两地点间最短路径

4.图5-4展示了操作3，校园导航功能，通过图1-1检查可知结果正确

图5-4 校园导航

5.图5-5展示了输入错误地点时出现错误提示功能

图5-5 错误提示

6.图5-6展示了操作4、5，评论功能，可以看到由于采用文件存储，先前写入过的评论也会被展示。

图5-6 评论

六、总结与展望

6.1 总结

以下是对代码的总结。

1.优点：整体逻辑清晰，代码结构良好；

2.不足：校园导航功能还可进一步完善；

3.遇到的困难：校园导航功能为TSP问题的变体，最优解有待讨论，实现较为复杂；

4.解决的问题：将校园导航功能转化为一般的TSP问题，并进行求解。

6.2不足与展望

1.不足：校园导航功能还可进一步完善；

2.展望：对场所的硬编码进行拓展，实现由用户定义图，并实现导航等功能。

代码展示：

#include "menu.h"
#include "graph.h"
#include <string>
#include <iostream>
#include <cstring>
#include <fstream>
inline void PerrorExit(const std::string &msg = "") {
  if (!msg.empty()) std::cout << msg << ": ";
  std::cout << strerror(errno) << std::endl;
}
bool GetPlace(std::string &line) {
  std::getline(std::cin, line);
  if (!place_map.count(line)) {
    std::cout << "地点不存在" << std::endl;
    return false;
  }
  return true;
}
int main() {
  InitGraph();
  menu();
  std::string line;
  while (true) {
    // 获取用户输入
    std::cout << "nav> ";
    if (!std::getline(std::cin, line)) break;
    // 输入为空
    if (line.empty()) continue;
    // 根据用户输入执行操作
    if (line == "0") {
      // 退出程序
      std::cout << "感谢使用" << std::endl;
      exit(0);
    } else if (line == "1") {
      // 显示校园平面图
      map();
    } else if (line == "2") {
      // 两地点间最短路径
      // 获取起点，终点
      std::cout << "请输入起点：";
      if (!GetPlace(line)) continue;
      int start = place_map[line];
      std::cout << "请输入终点：";
      if (!GetPlace(line)) continue;
      int end = place_map[line];
      // 最短距离
      std::cout << "最短距离：" << min_dis[start][end] << std::endl;
      // 最短路径
      std::cout << "最短路径：";
      std::cout << places[start] << " --> ";
      for (auto p: paths[start][end]) std::cout << places[p] << " --> ";
      std::cout << places[end] << std::endl;
    } else if (line == "3") {
      // 校园导航
      std::cout << "请输入当前位置：";
      if (!GetPlace(line)) continue;
      int start = place_map[line];
      TSP(start);
    } else if (line == "4") {
      // 留下您对生活区的评论
      std::cout << "请输入评论：";
      std::getline(std::cin, line);
      if (line.empty()) continue;
      std::ofstream os{"comment.txt", std::ios_base::app};
      os << line << std::endl;
    } else if (line == "5") {
      // 查看评论
      std::ifstream is{"comment.txt"};
      while (std::getline(is, line)) std::cout << line << std::endl;
    } else if (line == "menu") {
      // 查看菜单
      menu();
    } else {
      // error
      std::cout << "请输入正确指令" << std::endl;
    }
  }
  return 0;
}

#ifndef NAVIGATION_MENU_H
#define NAVIGATION_MENU_H

#include <iostream>

inline void menu() {
  std::cout<<"                        欢迎使用校园（生活区）导航系统" <<std::endl;
  std::cout<<"    *******************************************************************"<<std::endl;
  std::cout<<"    *                       1.显示校园平面图                          *"<<std::endl;
  std::cout<<"    *                       2.两地点间最短路径                        *"<<std::endl;
  std::cout<<"    *                       3.校园导航                                *"<<std::endl;
  std::cout<<"    *                       4.留下您对生活区的评论                    *"<<std::endl;
  std::cout<<"    *                       5.查看评论                                *"<<std::endl;
  std::cout<<"    *                       0.退出程序                                *"<<std::endl;
  std::cout<<"    *******************************************************************"<<std::endl;
  std::cout<<"    *                         输入序号以执行操作                      *"<<std::endl;
  std::cout<<"    *                          输入menu查看菜单                       *"<<std::endl;
  std::cout<<"    *******************************************************************"<<std::endl;
  std::cout<<"    *                                                                 *"<<std::endl;
}

// 查看地图
inline void map() {
  std::cout<<"    ——————————————————————————————————————————————————"<<std::endl;
  std::cout<<"    |               |垃圾回收站 |                           | 快递站 |   | 球场 |       |  湖  |        |"<<std::endl;
  std::cout<<"    |                ===========                             ========     ======        |      |        |"<<std::endl;
  std::cout<<"    |                                                                                    ======         |"<<std::endl;
  std::cout<<"    |                                                                                                   |"<<std::endl;
  std::cout<<"    |========           ========                         ========        =======        ======          |"<<std::endl;
  std::cout<<"    |C组团   |         | B组团  |       广场            | A组团  |      | 体育馆|      |      |         |"<<std::endl;
  std::cout<<"    |宿舍楼  |         | 宿舍楼 |                       | 宿舍楼 |      |       |      |  操  |         |"<<std::endl;
  std::cout<<"    |========           ========                         ========        =======       |  场  |         |"<<std::endl;
  std::cout<<"    |                                                                                  |      |         |"<<std::endl;
  std::cout<<"    |========    =================                       ========                       ======          |"<<std::endl;
  std::cout<<"    |D组团   |  | 医务室 |  师生  |                     |  二号  |                                      |"<<std::endl;
  std::cout<<"    |宿舍楼  |  |        |  活动  |                     |  食堂  |                                      |"<<std::endl;
  std::cout<<"    |========    =================                       ========                                       |"<<std::endl;
  std::cout<<"    |                                                                                                   |"<<std::endl;
  std::cout<<"    |                                                                                                   |"<<std::endl;
  std::cout<<"    |========                                                                                           |"<<std::endl;
  std::cout<<"    |停车场  |                                                                                          |"<<std::endl;
  std::cout<<"    |========                                       =========                                           |"<<std::endl;
  std::cout<<"    |                                              |  二号门  |                                         |"<<std::endl;
  std::cout<<"    ——————————————————————————————————————————————————"<<std::endl;
}

#endif //NAVIGATION_MENU_H

#ifndef NAVIGATION_GRAPH_H
#define NAVIGATION_GRAPH_H

#include <climits>
#include <unordered_map>
#include <string>
#include <map>
#include <stack>
#include <vector>
#include <algorithm>

constexpr int PN = 16;
constexpr int INF = INT_MAX;

const char *places[PN] = {
        "C组团宿舍楼",
        "D组团宿舍楼",
        "停车场",
        "垃圾回收站",
        "B组团宿舍楼",
        "医务室",
        "师生活动中心",
        "广场",
        "快递站",
        "A组团宿舍楼",
        "二号食堂",
        "二号门",
        "球场",
        "体育馆",
        "湖",
        "操场"
};

// 邻接矩阵
int graph[PN][PN] = {
        {INF, 60,  INF, 230, 100, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF},
        {INF, INF, 40,  INF, INF, 100, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF},
        {INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, 250, INF, INF, INF, INF},
        {INF, INF, INF, INF, INF, INF, INF, INF, 150, INF, INF, INF, INF, INF, INF, INF},
        {INF, INF, INF, INF, INF, INF, INF, 0,   INF, INF, INF, INF, INF, INF, INF, INF},
        {INF, INF, INF, INF, INF, INF, 0,   INF, INF, INF, 150, INF, INF, INF, INF, INF},
        {INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, 100, INF, INF, INF, INF, INF},
        {INF, INF, INF, INF, INF, INF, INF, INF, INF, 0,   INF, INF, INF, INF, INF, INF},
        {INF, INF, INF, INF, INF, INF, INF, INF, INF, 60,  INF, INF, 200, INF, INF, INF},
        {INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, 20,  INF, INF, 220, INF, INF},
        {INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, 20,  INF, INF, INF, INF},
        {INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, 620},
        {INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, 60,  150, INF},
        {INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, 100},
        {INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, 150},
        {INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF},
};

// 转换为完全图后的邻接矩阵
int cgraph[PN][PN] = {0};

// 名称到id的映射，图操作时使用id而非名称
std::unordered_map<std::string, int> place_map;

// 两点之间最短距离
int min_dis[PN][PN] = {0};

// 两点之间最短路径
std::vector<int> paths[PN][PN];

void Dijkstra(int start) {
  // 初始化
  std::map<int, int> S, T, Pre;
  for (int i = 0; i < PN; ++i) {
    T[i] = graph[start][i];
    if (graph[start][i] != INF) Pre[i] = start;
  }
  T.erase(start);

  for (int i = 1; i < PN; ++i) {
    // 从T中取出距离起点最近的点
    int min = INF, min_index = -1;
    for (const auto &pr: T) {
      auto k = pr.first;
      auto v = pr.second;
      if (v < min) {
        min = v;
        min_index = k;
      }
    }
    if (min_index < 0) break; // 无可达点

    // 将最近点移动至结果集
    S.insert({min_index, min});
    T.erase(min_index);

    // 使用新加入点，更新待处理集的距离
    for (const auto &pr: T) {
      auto k = pr.first;
      auto v = pr.second;
      if (graph[min_index][k] == INF) continue;
      int nd = S[min_index] + graph[min_index][k];
      if (nd < v || v == INF) {
        Pre[k] = min_index;
        T[k] = nd;
      }
    }
  }

  // 已经获取到结果集、路径集
  for (const auto &pr: S) {
    auto k = pr.first;
    auto v = pr.second;
    // v：从start到k的最短距离

    // 更新最短距离、完全图
    min_dis[start][k] = v;
    if (cgraph[start][k] == INF) cgraph[start][k] = v;

    // 填入路径
    std::vector<int> path;
    int cur = k;
    while (Pre[cur] != start) {
      path.push_back(Pre[cur]);
      cur = Pre[cur];
    }
    std::reverse(path.begin(), path.end());
    paths[start][k] = path;
  }
}

void TSP(int start) {
  // dp[s][[t]：从start出发，经过了s中为1的城市一次，当前在t的最短路径
  static int dp[1 << PN][PN] = {0};
  static int pre[1 << PN][PN];
  for (int s = 1; s < (1 << PN); ++s) {
    for (int t = 0; t < PN; ++t) {
      dp[s][t] = 0;
      pre[s][t] = -1;
    }
  }

  for (int s = 1; s < (1 << PN); ++s) {
    for (int i = 0; i < PN; ++i) {
      // i需要在状态s中
      // 例如s为 0...000101，经过了城市0、2，则需计算dp[s][0] dp[s][2]
      if ((s & (1 << i)) == 0) continue;

      // 若s中含有start，只计算dp[s][start]，其他为异常情况
      if ((s & (1 << start)) == 1 && i != start) continue;

      // 未到达当前城市前的状态
      // 例如s为0...010101，i为0，则pre_s为0...010100
      int pre_s = (s ^ (1 << i));

      // 边界条件，s中只有一个城市
      if (pre_s == 0) {
        dp[s][i] = cgraph[start][i];
        pre[s][i] = start;
        continue;
      }

      // 其他情况，在上述例子中，需考虑dp[pre_s][2]+d[2][0] dp[pre_s][4]+d[4][0]
      int min = INF, min_index = -1;
      for (int j = 0; j < PN; ++j) {
        if ((pre_s & (1 << j)) == 0) continue;
        if (dp[pre_s][j] + cgraph[j][i] < min) {
          min = dp[pre_s][j] + cgraph[j][i];
          min_index = j;
        }
      }
      dp[s][i] = min;
      pre[s][i] = min_index;
    }
  }

  // 获得结果集，路径集
  int result = dp[(1 << PN) - 1][start];

  std::vector<int> path;
  int s = (1 << PN) - 1;
  int t = start;
  while (s != 0) {
    int pre_t = pre[s][t];
    path.push_back(pre_t);
    s = (s ^ (1 << t));
    t = pre_t;
  }
  std::reverse(path.begin(), path.end());

  std::cout << "最短距离：" << result << std::endl;
  std::cout << "路径：";
  path.push_back(start);
  for (int i = 0; i < path.size() - 1; ++i) {
    std::cout << places[path[i]] << " --> ";
    auto next = path[i + 1];
    for (auto p: paths[path[i]][next]) std::cout << places[p] << " --> ";
  }
  std::cout << places[start] << std::endl;
}

// 初始化校园地图
void InitGraph() {
  for (int i = 0; i < PN; ++i) place_map[places[i]] = i;
  // 初始化邻接矩阵
  for (int i = 0; i < PN; ++i) {
    for (int j = 0; j < PN; ++j) {
      if (graph[i][j] != INF) graph[j][i] = graph[i][j];
    }
    graph[i][i] = 0;
  }

  // 用Dijkstra计算两点之间的最短距离、路径
  for (int i = 0; i < PN; ++i) {
    for (int j = 0; j < PN; ++j) {
      min_dis[i][j] = INF;
      cgraph[i][j] = INF;
      if (graph[i][j] != INF) cgraph[i][j] = graph[i][j];
    }
  }
  for (int i = 0; i < PN; ++i) Dijkstra(i);

  // 检查是否存在两点，它们之间不可达，是则报错
  for (int i = 0; i < PN; ++i) {
    for (int j = 0; j < PN; ++j) {
      if (cgraph[i][j] == INF) {
        std::cout << places[i] << " 到 " << places[j] << " 不可达" << std::endl;
        exit(1);
      }
    }
  }
}

#endif //NAVIGATION_GRAPH_H

文章出处登录后可见！

已经登录？立即刷新

校园导航系统 数据结构

二、系统总体设计

三、详细设计思路及算法

四、主要函数详细设计

相关推荐

校园导航系统数据结构