数据结构实验

这学期,我选中的这个实验是最短路问题,实际上最后的效果是很差的,因为我花在数据结构实验上的时间比较少,倒是数据库实验感觉做的不错,明天再发数据库实验的。到时再在这里添加链接。

20. 公交线路上优化路径的查询 

问题描述 

最短路径问题是图论中的一个经典问题,其中的Dijkstra算法一直被认为是图论中的好算法,但有的时候需要适当的调整Dijkstra算法才能完成多种不同的优化路径的查询。 

对于某城市的公交线路,乘坐公交的顾客希望在这样的线路上实现各种优化路径的查询。设该城市的公交线路的输入格式为: 

线路编号:起始站名(该站坐标);经过的站点1名(该站坐标);经过的站点2名(该站坐标);……;经过的站点n名(该站坐标);终点站名(该站坐标)。该线路的乘坐价钱。该线路平均经过多少时间来一辆。车速。 

例如:63:A(32,45);B(76,45);C(76,90);……;N(100,100)。1元。5分钟。1/每分钟。 

假定线路的乘坐价钱与乘坐站数无关,假定不考虑公交线路在路上的交通堵塞。 

对这样的公交线路,需要在其上进行的优化路径查询包括:任何两个站点之间最便宜的路径;任何两个站点之间最省时间的路径等等。 

 基本要求 

① 根据上述公交线路的输入格式,定义并建立合适的图模型。 

② 针对上述公交线路,能查询获得任何两个站点之间最便宜的路径,即输入站名S,T后,可以输出从S到T的最便宜的路径,输出格式为:线路x:站名S,…,站名M1;换乘线路x:站名M1,…,站名M2;…;换乘线路x:站名MK,…,站名T。共花费x元。 

③ 针对上述公交线路,能查询获得任何两个站点之间最省时间的路径(不考虑在中间站等下一辆线路的等待时间),即输入站名S,T后,可以输出从S到T的考虑在中间站等下一辆线路的等待时间的最省时间的路径,输出格式为:线路x:站名S,…,站名M1;换乘线路x:站名M1,…,站名M2;…;换乘线路x:站名MK,…,站名T。共花费x时间。 

④ 针对上述公交线路,能查询获得任何两个站点之间最省时间的路径(要考虑在中间站等下一辆线路的等待时间),即输入站名S,T后,可以输出从S到T的考虑在中间站等下一辆线路的等待时间的最省时间的路径,输出格式为:线路x:站名S,…,站名M1;换乘线路x:站名M1,…,站名M2;…;换乘线路x:站名MK,…,站名T。共花费x时间。 

(4) 实现提示 

需深入考虑,应根据不同的应用目标,即不同的优化查询来建立合适的图模型。 

 

github地址:

https://github.com/Findxiaoxun/Busmap

devlog

2014年03月19日 13时57分12秒 正式开始,前两个问题的算法已经有了头绪,今天就先把这两个实现。
还是先考虑下数据的读入和存储问题吧。以免后期大改动。
路线用vector,联通否直接用二维数组,每个点都标序号
class node应该包含的东西:
站点序列,站点经过的线路号,
class route :
线路经过的站点
线路车速,价格,
等待的时间。

文件的操作放到服务器上。同时文件的处理,对路线等的读入和初步处理在服务器上。
采用多线程来计算,同时,主意在屏幕提示状态
结果的保存格式?选择的点及用的路线。按顺序存储
2014年03月26日 10时32分08秒 虽然scanner巨慢无比,我还是先选用scanner看看吧http://zhidao.baidu.com/link?url=lQFBknkSa43YWkq8gxWtQfQbdg
DS5raKmZBnqQdgpYdI1XUkv_RrjY97Wf9fjr3taj80DKjJNjs1hkaHZ10wTK
新建一个client来处理吧,先,至于用不用服务器再说吧,用的话,还需要下载文件。这样也行。
进度条:http://blog.csdn.net/kakashi8841/article/details/6388797
http://bbs.csdn.net/topics/340076988
进度条先放一放,client加载数据用最后.thread 和runnable的区别http://blog.chinaunix.net/uid-20665441-id-310538.html
文件的工作放到
rmi传输文件:http://www.cnblogs.com/qytan36/archive/2010/03/28/1698885.html

只写本地的!!!
version 0.3
数据格式:
线路号 站点数 站1 x1 y1 站2 x2 y2 站3 x3 y3 站4 x4 y4 …  价格 周期 车速
搜集数据

2014年04月02日 10时35分05秒 把数据格式定下来,同时准备做主界面(开始有个页面的消失动画)

version 0.6
更新了主界面。准备今晚先写算法,然后准备更新的东西。
最省时间的那个算法:
首先先把数据读入进去。也不要处理。读入的是每条线路的经过的点,这条线路的价格。等等。然后再循环每条线路,更新经过的点的passRoute,还有就是点与点之间的是否通(后期可以通过两个点的共同的路线来确定路线。)
14:46 2014/4/23
version 0.7 完善界面,同时测试第一个算法功能
后期目标:接入语音功能,可以弹出结果的选择界面
Node:
index:节点序号passRoute[]:经过它的线路号len经过它的线路数量x,y:节点坐标
getPassRoute()获取通过的线路号
getIndex()获取节点号
addPassRoute()添加经过的线路,用户在初始添加线路的时候

Route:
speed:速度index线路号price价格time多长时间来一趟len经过的节点数passNode经过的节点号
addPassNode()添加经过的节点号
getPassNode()获取该线路的节点集合
getSpeed()获取速度
getPassNodelen()获取经过的节点数量

16:37 2014/4/27 抓紧时间完善啊!!!
9:15 2014/5/4 goal:完善测试第一个
version 0.8 文件读入结束,界面设计70%,准备开始测试第一个
find按钮按下,直接调用dijkstra的方法
最省时间的:先不考虑换成的车号
所有的点都从1开始!!nodelen有意义
15:56 2014/5/5 version 0.9 debug。。。。
12:24 2014/5/6 version 1.0 正在进行第一个的调试,还是读入的问题啊!!!
while(scan2.hasNext()){
Route b=new Route();
这里的b一定要在里面new啊@@@@@
version 1.1 已经完善了第一个功能。而且测试通过。准备添加第二个算法。

 

文章版权归 FindHao 所有丨本站默认采用CC-BY-NC-SA 4.0协议进行授权|
转载必须包含本声明,并以超链接形式注明作者 FindHao 和本文原始地址:
https://www.findhao.net/easycoding/71

你可能喜欢:(相似内容推荐和广告都使用了谷歌的推荐系统,需要对本站取消广告屏蔽才能显示。感谢点击↓广告支持博主~)

Find

新浪微博(FindSpace博客)QQ群:不安分的Coder(375670127) 不安分的Coder

发表评论

电子邮件地址不会被公开。 必填项已用*标注

*