地铁路线规划
一.简述：
本次地铁出行线路规划个人项目，选择使用的编程语言是java语言，编程工具是eclipse，且为了降低难度与简化要求，现阶段我们可以假定程序的输入一定是正确的。同时，为了让地铁程序能与地铁线路图解耦，我们需要将地铁线路与程序分离开，将其保存成一个可读入的文件，data.txt文件。把所有线路的信息按照一定格式输入。在地铁程序上实现了三个项目需求，txt文件的导入，用户希望查询指定地铁线经过的站点的实现，两个站点间最短路径的算法实现，最后对程序进行了多次测试，都成功。
二.PSP表：
三.项目说明：
1.txt文件的输入格式：
站点 下一个站点 距离
刘园 西横堤 1 西横堤 果酒厂 1 果酒厂 本溪路 1 本溪路 勤俭道 1 。。。。。。
2.包，类的功能
Model包：用来存放自定义的四个实体类，距离类，缓存类，节点类，路径类。
Manager包：用来存放两个方法，txt文件的导入，需求的几号线输出，两个站点最短路径的输出。
Test包：用来测试几个需求的包。
3.最短路径算法
public class ComputeShort {
private Data data; // 存储数据的类
private EasyCache cache = new EasyCache(); // 缓存数据，防止数据量过大导致内存溢出
private Path getShortDis(Node a, Node b, Set<Node> visited) {
// Set里的值是和放入顺序无关的固定顺序,这里恰好可以做cache的key
String key = a.toString() + b.toString() + visited;
Path rs = (Path) cache.get(key);
if (rs != null) {
//System.out.println("read from cache : " + key);
return rs;
}
// cache里没有则计算
rs = new Path();
// 访问过了则返回
if (visited.contains(a)) {
cache.put(key, rs);
return rs;
} else {
visited.add(a);
rs.getPath().add(a);
}
// 如果是相连的直接返回结果
if (a.isConnected(b)) {
rs.getPath().add(b);
rs.setDis(data.getDis().get(a, b));
cache.put(key, rs);
return rs;
} else {
// 否则递归调用
Iterator<Node> nodes = a.getConnected();
int tempRs = -1;
LinkedList<Node> path_temp = null;
while (nodes.hasNext()) {
Node temp = nodes.next();
Integer dis = -1;
Set<Node> visted_child = new HashSet<Node>();
visted_child.addAll(visited);
Path child = getShortDis(temp, b, visted_child);
if (child.getDis() == -1)
continue;
dis = data.getDis().get(a, temp) + child.getDis();
if (tempRs == -1 || dis < tempRs) {
tempRs = dis;
path_temp = child.getPath();
}
}
if (path_temp != null)
rs.getPath().addAll(path_temp);
if (tempRs != -1)
rs.setDis(tempRs);
cache.put(key, rs);
return rs;
}
}
public Data getData() {
return data;
}
public void setData(Data data) {
this.data = data;
}
public Path getShort(String a, String b) {
Node nodeA = data.getNodes().get(a);
Node nodeB = data.getNodes().get(b);
Path p = getShortDis(nodeA, nodeB, new HashSet<Node>());
return p;
}
public String[] getOneLine(int linename) {
String[][] line=data.getLine();
String[] oneLine=new String[line[linename-1].length];
for(int i = 0;i<line[linename-1].length;i++) {
oneLine[i]=line[linename-1][i];
}
return oneLine;
}
}
这个算法是通过网上资源学习的，觉得他写得很不错，虽然要实现本次项目最短路径算法还要进行修改，但是这个算法还能计算距离，我觉得这样不仅能完成需求，还可以在此基础上增加新的内容，也就是在进行最短路径计算时还可以加上每两个站点间的距离权值，这也是为什么txt文件中设计了距离的属性。
4.测试
路线输出功能：
最短路径功能：
四.体会：
学会建立项目、编写markdown文件、使用Git 推送代码。
构思地铁线路问题，将其抽象为基于图的运算。设计主要功能模块。
学习了最短路径的算法，收益颇多。
就这一项目，就发现了自己还有还有很多不会的java编写方法，还要继续学习。