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

R

rake

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-11-20

• #1

我想实现这样一个东西!
在输入起点终点后,给出乘坐线路!
不用换车的部分已经完成,但是在出现换车时问题就复杂多了,想请都高手给予指点
具体一点!
(由于小弟水平太差,请给出代码最好!!!)

 

Y

yzx_1983

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-11-24

• #2

是图论中加权连通图的最短链问题吧

 

T

thinknet

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-11-24

• #3

是运筹学里的最短路问题，有公式的，要不要给你找找。

 

L

ldaan3

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-11-24

• #4

从终点站往前找，然后分一次转车、两次转车来弄。
太多了就更复杂了

 

死

死水

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-11-24

• #5

我支持你！
软件做好了，我要买一套用用，呵呵

 

R

renxiaoyaolixia

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2002-11-24

• #6

关注。我也正在学数据结构

 

Z

ztaif

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-04-06

• #7

看到这道题偶有点晕! 偶数学天天考鸭蛋!!!!!呵~~~~~~~~~

 

L

LeeChange

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-04-09

• #8

to rake:
看来你也不急.呵呵.
你希望是转车最少呀,还是希望路程最近.?

 

O

onlyonekgx

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-04-09

• #9

我记得有一本程序员杂志
上有这样的程序！

 

老

老人家

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-04-09

• #10

用递归阿

 

L

LeeChange

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-04-09

• #11

to 老人家:
呵呵，次题我不赞成用递归.
城市公交的搜索空间一般都不会太大,象这种种搜索空间不大的问题求最优解,为什么不用
广度优先呢?

 

老

老人家

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-04-09

• #12

to LeeChange
他要把说有的路线都列出来，不用递归，还有其他办法吗？
难道我题意理解错了。

 

L

LeeChange

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-04-09

• #13

我想实现这样一个东西!
在输入起点终点后,给出乘坐线路!
不用换车的部分已经完成,但是在出现换车时问题就复杂多了,想请都高手给予指点
具体一点!
(由于小弟水平太差,请给出代码最好!!!)
hehe,没看出来楼主要所有路线,见谅见谅.
呵呵,求所有路线确实要用深度优先,呵呵，但深度优先也有非递归算法的.

 

R

rake

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-06-01

• #14

我也不是不急 不过最近这事儿是放下了 想不出具体的方法搞定呀

 

H

hongyi

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-06-01

• #15

你可以参考一下全国大学生数学建模大赛，前几年有一个关于 公交车路线的设计问题
很多人都给了很好的解决方案！
时刻关注中。。。。

 

T

teleman2000

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-06-13

• #16

实现转一次车或转两次好像不难，我曾作做一个，是通过下面的方式实现的：
首先，数据库表结构是这样的：
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只是一个例子，程序中可以用数组等。
自己编这个小程序是因为到北京的时候坐公交车经常要查半天地图，完成之后搜索了一下，还可以，还没找到搜索不到的情况。用的方法不先进，因为我不懂图的算法。
不过程序很久不用了，具体的算法记不清了，思路大概是这样的。

 

魔

魔鬼大师

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-06-13

• #17

图的问题

 

魔

魔鬼大师

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2003-06-13

• #18

图的问题
看数据结构