help!!!!公交车问题!!!(200分)

R

rake

Unregistered / Unconfirmed
GUEST, unregistred user!
我想实现这样一个东西!
在输入起点终点后,给出乘坐线路!
不用换车的部分已经完成,但是在出现换车时问题就复杂多了,想请都高手给予指点
具体一点!
(由于小弟水平太差,请给出代码最好!!!)
 
是图论中加权连通图的最短链问题吧
 
是运筹学里的最短路问题，有公式的，要不要给你找找。
 
从终点站往前找，然后分一次转车、两次转车来弄。
太多了就更复杂了
 
我支持你！
软件做好了，我要买一套用用，呵呵
 
关注。我也正在学数据结构
 
看到这道题偶有点晕! 偶数学天天考鸭蛋!!!!!呵~~~~~~~~~
 
to rake:
看来你也不急.呵呵.
你希望是转车最少呀,还是希望路程最近.?
 
我记得有一本程序员杂志
上有这样的程序！
 
用递归阿
 
to 老人家:
呵呵，次题我不赞成用递归.
城市公交的搜索空间一般都不会太大,象这种种搜索空间不大的问题求最优解,为什么不用
广度优先呢?
 
to LeeChange
他要把说有的路线都列出来，不用递归，还有其他办法吗？
难道我题意理解错了。
 
我想实现这样一个东西!
在输入起点终点后,给出乘坐线路!
不用换车的部分已经完成,但是在出现换车时问题就复杂多了,想请都高手给予指点
具体一点!
(由于小弟水平太差,请给出代码最好!!!)
hehe,没看出来楼主要所有路线,见谅见谅.
呵呵,求所有路线确实要用深度优先,呵呵，但深度优先也有非递归算法的.
 
我也不是不急 不过最近这事儿是放下了 想不出具体的方法搞定呀
 
你可以参考一下全国大学生数学建模大赛，前几年有一个关于 公交车路线的设计问题
很多人都给了很好的解决方案！
时刻关注中。。。。
 
实现转一次车或转两次好像不难，我曾作做一个，是通过下面的方式实现的：
首先，数据库表结构是这样的：
BUS_NBR 公交线路号
STOP_NBR 车站在线路中的序号
STOP_NAME 车站名字
CONVERSE 是否单行线
在程序中放置两个TQuery组件QryA和QryB，都联到上面的表中。输入起点A,输入终点B。
在QryA中查询A站所在的线路号（有若干条），在QryB中查询B站所经过的线路（由若干条）。然后这两个集合中的线路号进行比较，如果有重复的线路号(可用一个循环加locate函数），例如QryA和QryB中都有23路，那么这个23路就是直达。如果QryA和QryB中没有相同
的线路号，那么就说明从A站到B站必须进行转车。这个怎么办呢？先看转一次车，如下：
for i:=1 to 经过A站的线路总和do
begin
取出一条线路；
找出这条线路上的所有车站；
for j:=1 to 经过B站的线路总和do
begin
取出一条线路；
找出这条线路上的所有车站；
比较这些车站名和外循环中的车站名有没有相同；
如果相同，那么就在这个车站转车
end
end;

用类似的方法，可以实现转2次3次车，再深的层次就没有考虑了。
上面使用的QryA和QryB只是一个例子，程序中可以用数组等。
自己编这个小程序是因为到北京的时候坐公交车经常要查半天地图，完成之后搜索了一下，还可以，还没找到搜索不到的情况。用的方法不先进，因为我不懂图的算法。
不过程序很久不用了，具体的算法记不清了，思路大概是这样的。


 
图的问题
 
图的问题
看数据结构
 
您必须登录或注册才可回复。

Similar threads

D
[原]WAMP中修改PHP.ini
回复
0
查看
736
DelphiTeacher的专栏
D
D
[原]WAMP中修改PHP.ini
回复
0
查看
711
DelphiTeacher的专栏
D
D
[原]WAMP中修改PHP.ini
回复
0
查看
682
DelphiTeacher的专栏
D
S
[转]ClientDataSet加上TDataSetProvider的数据保存问题
回复
0
查看
3K
SUNSTONE的Delphi笔记
S
S
[转]ClientDataSet加上TDataSetProvider的数据保存问题
回复
0
查看
2K
SUNSTONE的Delphi笔记
S
顶部