开放原子开发者工作坊

地铁出行路线

https://github.com/ChengFR/PersonalProgram_SubwayRoute

时间预期

PSP 2.1	Personal Software Process Stages	Time
Planning	计划
· Estimate	· 估计这个任务需要多少时间
Development	开发
· Analysis	· 需求分析 (包括学习新技术)	3h
· Design Spec	· 生成设计文档	1h
· Design Review	· 设计复审 (和同事审核设计文档)	0.5h
· Coding Standard	· 代码规范 (为目前的开发制定合适的规范)	1h
· Design	· 具体设计	1h
· Coding	· 具体编码	2h
· Code Review	· 代码复审	0.5h
· Test	· 测试（自我测试，修改代码，提交修改）	1h
Reporting	报告
· Test Report	· 测试报告
· Size Measurement	· 计算工作量
· Postmortem & Process Improvement Plan	· 事后总结, 并提出过程改进计划	1h
	合计	11h

实际用时

PSP 2.1	Personal Software Process Stages	Time
Planning	计划
· Estimate	· 估计这个任务需要多少时间
Development	开发
· Analysis	· 需求分析 (包括学习新技术)	4h
· Design Spec	· 生成设计文档	0.5h
· Design Review	· 设计复审 (和同事审核设计文档)	\
· Coding Standard	· 代码规范 (为目前的开发制定合适的规范)	2h
· Design	· 具体设计	2h
· Coding	· 具体编码	3h
· Code Review	· 代码复审	1h
· Test	· 测试（自我测试，修改代码，提交修改）	1h
Reporting	报告
· Test Report	· 测试报告
· Size Measurement	· 计算工作量
· Postmortem & Process Improvement Plan	· 事后总结, 并提出过程改进计划	1h
	合计	14.5h

程序性能

　　在程序设计阶段，对于程序的性能进行过考量。

　　在实现功能最少换乘寻路时，最初准备将地铁图按照一般图进行处理，运用Dijkstra算法，记录到达每一站的前一站(当前最短路径中)；定义换乘的代价为较大数，定义换乘行为为该站的前一站的前一站与其不在同一条地铁线上，在计算该节点的距离时，需要加上换乘代价。最后根据站点记录推出线路。

　　然而该算法要对大量节点进行搜索，由于Dijkstra运用贪心的策略，首先搜索的是终点站(从终点站倒推)所在线路上的所有站点，而大量情况往往是存在换乘的，因此效率低下。

　　考虑到地铁图存在一定的特殊性，只有在换乘站才能进行"换乘"，也就是说两个不在同一条地铁线上的站点之间的路线必然经过这两个站点所在线路上的换乘站。因此提取换乘站进行寻路，处理的节点比原图节点少得多，只是计算节点之间的距离会增加时间开销。(事实上计算距离的函数确实占用了最多的时间)

　　程序最终的性能分析图：

程序测试时进行初始化，调用了一次findTrailB函数以及一次findTrailC函数，分别为最短寻路和最少换乘寻路。

可以看到初始化过程中文件处理占用的时间最多。在findTrailC最少换乘寻路函数中，距离计算函数calcDis占用的时间最多。

函数实现为:

int subNet::calcDis(station* sta1, station* sta2, subLine* line) {
 if ((!inLine(sta1, line)) || (!inLine(sta2, line))) {
  cerr << "stations are not in a line." << endl;
  if (!inLine(sta1, line))
   cerr << sta1->_name << "not in line." << endl;
  if (!inLine(sta2, line))
   cerr << sta2->_name << "not in line." << endl;
  return -1;
 }
 int num1 = 0, num2 = 0;
 auto b = line->_stations.begin();
 auto e = line->_stations.end();
 int i = 0;
 for (; b != e; b++, i++) {
  if ((*b) == sta1)
   num1 = i;
  if ((*b) == sta2)
   num2 = i;
 }
 if (line->_isCir) {
  int length = line->_stations.size();
  int dis1 = (num1 - num2) % length;
  int dis2 = (num2 - num1) % length;
  return (dis1 > dis2) ? dis1 : dis2;
 }
 else {
  return (num1 > num2) ? num1 - num2 : num2 - num1;
 }
}

程序测试

路线输出测试测例：(随机选取)

1号线

大兴线

最短寻路测试：

公主坟 知春路 //存在多条路线，其中多次换乘路线相较于直达路线更近

知春路 公主坟 //反向测试

火器营 巴沟 //环线测试

最少换乘测试：

公主坟 知春路 //存在多条路线，其中直达线路并非最近

知春路 公主坟 //反向测试

火器营 巴沟 //环线测试

公主坟 国贸 //存在多条直达路线

沙河 巩华城 //由于最少换乘算法时基于换乘站寻路的，设置不经过换乘站路线看其是否能够正常寻路

 

没有列出错误的输入样例

这十个测试样例具有一定代表性，实际测试样例不止这些。

---

补充：进一步的测试发现1号线转4号线，例如“大望路”、“四惠”、“四惠东”、“高碑店”不满足定义的换乘表达，故特殊处理

个人收获

1.重新学习了C++的知识。由于一段时间没有使用C++，有些生疏。这次练习提升了C++的技能。

2.OOP的一次实践。利用面向对象思想编写的程序。然而程序规范性上还需要提升。

3.某种意义上提升了解决实际问题的能力。