[求助]公交查询系统中的换乘问题

wjlone

我有个问题咨询一下
小弟我的毕业设计公交查询系统,但是我的数据库设计一直困扰着我,我想设计支持两次换乘的系统,想用算法实现,但是没有什么思路,请高手指点,
小弟万分感谢!!!!!!!!!!
如果有做好的给我做参考也行.谢谢啊!!!
我的邮箱wjlq001@126.com

[ 本帖最后由 风花雪月 于 2007-4-2 09:22 编辑 ]

风花雪月

csdn 上的讨论，你可以参考一下
另外在5楼还给了一个方案

------------------------------------------------------
现要用一个公交查询(TNND,我朋友的毕业设计,可是这实在属于费力不讨好的设计).
如果要用C/S结构的话还将就,可是要命的是要用B/S结构来实现,比这个更要命的是要用ASP
大家出出主意啊

呵呵,不要告诉我去看迪杰特斯拉算法或者弗洛伊德算法啊
现在就是想讨论一下怎么实现好一些
------------------------------------------------------
cime63(归去来) ( ) 信誉：1002006-3-21 13:50:04得分: 0
包括数据库的设计
想了半天都没想好怎么存储会在程序实现时方便一些
------------------------------------------------------
p54188(热爱生活 疼爱老婆) ( ) 信誉：1002006-3-21 13:57:05得分: 0
asp?的确挺可恶的
帮顶~
------------------------------------------------------
huwei2003(凡) ( ) 信誉：1002006-3-21 14:10:01得分: 0
UP
------------------------------------------------------
cime63(归去来) ( ) 信誉：1002006-3-21 14:10:41得分: 0
我有想过用ASP调用COM组件,然后用VC写个COM组件
但是现在还不能确定数据库的结构啊
想了半天,总觉得在写程序的时候会很麻烦
------------------------------------------------------
BookSirSwordsMan(书生剑客) ( ) 信誉：1002006-3-21 14:11:08得分: 0
up
========================================================
我一定要超过他！！！！！！
做出我最强的东西！！！！！
再和他一比高下！！！！！！
========================================================
cho__cho(CHO) ( ) 信誉：1002006-3-21 14:27:21得分: 0
------------------------------------------------------
呵呵，我曾想过，拿来共享一下，讨论我的方法是否合理吧（很粗糙的）
数据库dbbus：表TbStation
(CREATE TABLE IF NOT EXISTS tbstation (
ID tinyint(3) unsigned NOT NULL auto_increment,
bus text ,
station text ,
PRIMARY KEY (ID),
KEY ID (ID)
);
很垃圾的设计，但我现在只是想和你们一起讨论讨论的
查询站点，记录每个站点所经过的车次，再查车，再查站，反复查询（递归），将每次查询得到的结果存放在一个多维数组中......
程序现在还没时间写出来，这个方法是我在一本讲数据结构的书上看的
请大家建议，我会尽快抽时间将程序写出来
------------------------------------------------------
cime63(归去来) ( ) 信誉：1002006-3-21 14:35:15得分: 0
我再想一下
------------------------------------------------------
Response_chen(俺村俺最丑) ( ) 信誉：952006-3-21 15:24:31得分: 0
偶的想法，尽供参考：

图的长度问题

偶的实现

基本表：tStations(所有站的集合) , tBuses(所有公交路径集合)

然后运用求图所有路径的算法就可得结果！

B/S ,C/S实现方式是一样的
------------------------------------------------------
sz315(名剑) ( ) 信誉：1002006-3-21 15:44:51得分: 0
我做过这个。
------------------------------------------------------
rd16() ( ) 信誉：922006-3-21 15:45:51得分: 0
楼主的意思可能是：

如果没有直达车就要列出转车路线。

这个我以前做过，不过没有做出来。关注中。。。。
------------------------------------------------------
rd16() ( ) 信誉：922006-3-21 15:47:11得分: 0
Tsz315(名剑)

是B/S吗。。看看代码
------------------------------------------------------
cime63(归去来) ( ) 信誉：1002006-3-21 15:49:01得分: 0
嗯,意思就是,没有直达车的话,查出换乘的车次,车站等等
我觉得最多换乘三次就够了
------------------------------------------------------
cime63(归去来) ( ) 信誉：1002006-3-21 15:50:41得分: 0
Tsz315(名剑)
同rd16() ( ) 信誉：92 一样,希望看看代码
如果不行的话,至少谈一下思路
3Q
------------------------------------------------------
netsd(极品非车) ( ) 信誉：1002006-3-21 15:58:38得分: 0
其实跟B/S C/S没有关系.看样子是楼主知道算法,是不知道在ASP中怎么实现.除了用COM还真没有更好的办法.不过ASP调用COM挺可误的,COM有改动还在再注册.
楼主有算法分享出来吧,以前我也搞过,也没搞出来
------------------------------------------------------
rd16() ( ) 信誉：922006-3-21 16:00:28得分: 0
------------------------------------------------------
Tnetsd(极品非车)
数据量大的话B/S不好做，除非有非常好的算法.
------------------------------------------------------
rd16() ( ) 信誉：922006-3-21 16:04:57得分: 0
------------------------------------------------------
楼主，这里有答案了。

http://blog.csdn.net/iuhxq/archive/2005/09/08/475037.aspx
------------------------------------------------------
cime63(归去来) ( ) 信誉：1002006-3-21 16:30:10得分: 0
存储过程啊
看来得放弃ACCESS数据库了
------------------------------------------------------
chaos_blue(chaos（混沌）) ( ) 信誉：1002006-3-21 16:39:29得分: 0
mark
------------------------------------------------------
rd16() ( ) 信誉：922006-3-21 16:42:53得分: 0
Tcime63(归去来)
在实际项目中，这种东西不可能用ACCESS来做。
------------------------------------------------------
scjtswj() ( ) 信誉：1002006-3-21 16:47:11得分: 0
不做过
顶
------------------------------------------------------
cime63(归去来) ( ) 信誉：1002006-3-21 16:48:43得分: 0
------------------------------------------------------
rd16() ( ) 信誉：922006-03-21 16:42:00得分: 0
Tcime63(归去来)

在实际项目中，这种东西不可能用ACCESS来做。

=================================================
是这样
可是我那朋友如果什么都学过的话就不用让我给他做毕业设计了
------------------------------------------------------
cime63(归去来) ( ) 信誉：1002006-3-21 17:02:49得分: 0
小灰那个只支持一次转乘啊

其实一次转乘不用存储过程做起来也不难的

[ 本帖最后由 风花雪月 于 2007-4-2 09:26 编辑 ]

风花雪月

iuhxq(小灰) ( ) 信誉：1002006-3-21 17:09:03得分: 0



if exists (select * from dbo.sysobjects where id = object_id(N‘[dbo].[t]‘) and OBJECTPROPERTY(id, N‘IsUserTable‘) = 1)
drop table [dbo].[t]
GO

CREATE TABLE [dbo].[t] (
[id] [int] IDENTITY (1, 1) NOT NULL ,
[lid] [nvarchar] (50) ,
[name] [nvarchar] (50) ,
[type] [int] NOT NULL
)
GO

insert into t (lid,[name],[type])
select "11","城站火车站",0
union all select "11","葵巷建国路口",0
union all select "11","菜市桥",0
union all select "11","潮鸣寺巷",0
union all select "11","宝善桥建国路口",0
union all select "11","宝善桥",0
union all select "11","市体育馆",0
union all select "11","武林广场",0
union all select "11","武林门",0
union all select "11","武林们马塍路口",0
union all select "11","八字桥",0
union all select "11","浙大西溪校区",0
union all select "11","庆丰村",0
union all select "11","教工路口",0
union all select "11","花园新村",0
union all select "11","浙江工商大学",0
union all select "11","电子科技大学",0
union all select "11","翠苑新村",0
union all select "57","大关小区",0
union all select "57","通信市场",0
union all select "57","德胜新村",0
union all select "57","潮王路口",0
union all select "57","朝晖五区",0
union all select "57","朝晖三区",0
union all select "57","西湖文化广场东",0
union all select "57","武林广场",0
union all select "57","武林小广场",0
union all select "57","半道红",0
union all select "57","文三路口",0
union all select "57","上宁桥",0
union all select "57","花园新村",0
union all select "57","浙江工商大学",0
union all select "57","文一路口",0
union all select "57","教工路北口",0
union all select "57","大关桥西",0
union all select "57","上塘路口",0
union all select "57","大关西六苑",0
union all select "57","香积寺路口",0
union all select "57","大关小区",0
union all select "14","武林小广场",0
union all select "14","昌化新村",0
union all select "14","长寿桥",0
union all select "14","延安路口",0
union all select "14","中大广场",0
union all select "14","众安桥",0
union all select "14","浙一医院",0
union all select "14","大学路北口",0
union all select "14","庆春门",0
union all select "14","金衙庄",0
union all select "14","总管塘",0
union all select "14","华东家具市场",0
union all select "14","近江村",0
union all select "14","汽车南站",0
union all select "14","汽车南站",1
union all select "14","近江村",1
union all select "14","华东家具市场",1
union all select "14","总管塘",1
union all select "14","金衙庄",1
union all select "14","庆春门",1
union all select "14","大学路北口",1
union all select "14","浙一医院",1
union all select "14","众安桥",1
union all select "14","中大广场",1
union all select "14","延安路口",1
union all select "14","长寿桥",1
union all select "14","昌化新村",1





iuhxq(小灰) ( ) 信誉：1002006-3-21 17:09:19得分: 0



union all select "14","武林小广场",1
union all select "K105","火车东站",0
union all select "K105","汽车东站",0
union all select "K105","严家弄",0
union all select "K105","景芳五区",0
union all select "K105","景御路口",0
union all select "K105","庆春东路",0
union all select "K105","采荷新村",0
union all select "K105","观音塘小区",0
union all select "K105","总管塘",0
union all select "K105","章家桥",0
union all select "K105","浙二医院",0
union all select "K105","官巷口",0
union all select "K105","湖滨",0
union all select "K105","胜利剧院",0
union all select "K105","孩儿巷",0
union all select "K105","延安新村",0
union all select "K105","武林小广场",0
union all select "K105","杭州大厦",0
union all select "K105","中北桥",0
union all select "K105","施家桥",0
union all select "K105","建国北路文晖路口",0
union all select "K105","文晖大桥东",0
union all select "K105","机神村",0
union all select "K105","天城路口",0
union all select "K105","新塘路口",0
union all select "K105","火车东站",0
union all select "39","闸口",0
union all select "39","水澄桥",0
union all select "39","海月桥",0
union all select "39","美政桥",0
union all select "39","复兴路北口",0
union all select "39","三廊庙",0
union all select "39","木材新村",0
union all select "39","二凉亭",0
union all select "39","望江门外",0
union all select "39","汽车南站",0
union all select "39","近江村",0
union all select "39","华东家具市场",0
union all select "39","总管塘",0
union all select "39","城站火车站",0
union all select "K101","城站火车站",0
union all select "K101","总管塘",0
union all select "K101","观音塘小区",0
union all select "K101","采荷新村",0
union all select "K101","红菱新村",0
union all select "K101","凤起东路口",0
union all select "K101","双菱路北口",0
union all select "K101","市红会医院",0
union all select "K101","建国路口",0
union all select "K101","新华路口",0
union all select "K101","中北路口",0
union all select "K101","延安路口",0
union all select "K101","浙大湖滨校区",0
union all select "K101","昌化新村",0
union all select "K101","市府大楼",0
union all select "K101","武林门马塍路口",0
union all select "K101","八字桥",0
union all select "K101","浙大西溪校区",0
union all select "K101","庆丰村",0
union all select "K101","玉古路天目山路口",0
union all select "K101","西湖体育馆",0
union all select "21/K21","城站火车站",0
union all select "21/K21","章家桥",0
union all select "21/K21","新城隧道东口",0
union all select "21/K21","解放路秋涛路口",0
union all select "21/K21","采荷新村",0
union all select "21/K21","红菱新村",0
union all select "21/K21","双菱路北口",0
union all select "21/K21","市红会医院",0
union all select "21/K21","建国路口",0
union all select "21/K21","新华路口",0
union all select "21/K21","中北路口",0
union all select "21/K21","延安路口",0
union all select "21/K21","浙大湖滨校区",0
union all select "21/K21","昌化新村",0
union all select "21/K21","市府大楼",0
union all select "21/K21","武林门马塍路口",0
union all select "21/K21","八字桥",0
union all select "21/K21","浙大西溪校区",0
union all select "21/K21","庆丰村",0
union all select "21/K21","跑马场",0
union all select "21/K21","黄龙体育中心",0
union all select "21/K21","浙大附中",0
union all select "21/K21","求是路",0
union all select "21/K21","西湖体育馆",0
union all select "58/K58","大关小区",0
union all select "58/K58","上塘路香积寺路口",0
union all select "58/K58","大关西六苑",0
union all select "58/K58","上塘路口",0
union all select "58/K58","大关桥西",0
union all select "58/K58","教工路北口",0
union all select "58/K58","文一路口",0
union all select "58/K58","浙江工商大学",0
union all select "58/K58","花园新村",0
union all select "58/K58","上宁桥",0
union all select "58/K58","文三新村",0
union all select "58/K58","八字桥",0
union all select "58/K58","武林门马塍路口",0
union all select "58/K58","武林小广场",0
union all select "58/K58","武林广场",0
union all select "58/K58","中北桥",0
union all select "58/K58","朝晖一区",0
union all select "58/K58","朝晖三区",0
union all select "58/K58","朝晖五区",0
union all select "58/K58","潮王路口",0
union all select "58/K58","德胜新村",0
union all select "58/K58","通信市场",0





iuhxq(小灰) ( ) 信誉：1002006-3-21 17:09:28得分: 0



union all select "58/K58","大关小区",0
union all select "K101","西湖体育馆",1
union all select "K101","玉古路天目山路口",1
union all select "K101","庆丰村",1
union all select "K101","浙大西溪校区",1
union all select "K101","八字桥",1
union all select "K101","武林门马塍路口",1
union all select "K101","市府大楼",1
union all select "K101","昌化新村",1
union all select "K101","浙大湖滨校区",1
union all select "K101","延安路口",1
union all select "K101","中北路口",1
union all select "K101","新华路口",1
union all select "K101","建国路口",1
union all select "K101","市红会医院",1
union all select "K101","双菱路北口",1
union all select "K101","凤起东路口",1
union all select "K101","红菱新村",1
union all select "K101","采荷新村",1
union all select "K101","观音塘小区",1
union all select "K101","总管塘",1
union all select "K101","城站火车站",1

/****** Object:Stored Procedure dbo.SearchScript Date: 2005-9-8 10:28:35 ******/
if exists (select * from dbo.sysobjects where id = object_id(N‘[dbo].[Search]‘) and OBJECTPROPERTY(id, N‘IsProcedure‘) = 1)
drop procedure [dbo].[Search]
GO

SET QUOTED_IDENTIFIER OFF
GO
SET ANSI_NULLS ON
GO


/****** Object:Stored Procedure dbo.SearchScript Date: 2005-9-8 10:28:35 ******/
CREATE proc Search
@name1 nvarchar(50),
@name2 nvarchar(50)
as

--中转站
create table #tmp
(
tmp_id int identity(1,1),
tmp_name NVARCHAR(50)
)

--站点队列
create table #tmp1
(
tmp1_id int identity(1,1),
tmp1_name NVARCHAR(50)
)


--查找结果
create table #result
(
r_id int,
r_lid nvarchar(50),
r_name nvarchar(50),
r_type int
)

--直达
insert into #result
select c.*from t a,t b,t c where
a.lid=b.lid and a.[type]=b.[type] and a.idand a.[name] = @name1 and b.[name] = @name2
and c.id>=a.id and c.id<=b.id order by c.id

if @@rowcount>0 begin
select * from #result
end
else begin
--换车
DECLARE @CurrenName NVARCHAR(50)
SET @CurrenName = @name1
change:
/*
--车次入栈
insert into #tmp (tmp_lid)
select distinct lid from t where [name] = @CurrenName
DECLARE @CurrenBus NVARCHAR(50)
SELECT 1 @CurrenBus = tmp_lid FROM #tmp
*/
INSERT INTO #tmp1 (tmp1_name)
SELECT DISTINCT b.[name] FROM t a,t b WHERE a.[name] = @CurrenName AND b.lid = a.lid AND b.[name] <> @CurrenName

INSERT INTO #tmp (tmp_name)
select d.[tmp1_name]from t a,t b,t c, #tmp1 d where
a.lid=b.lid and a.[type]=b.[type] and a.idand a.[name] = d.[tmp1_name] and b.[name] = @name2
and c.id>=a.id and c.id<=b.id

IF @@rowcount>0 BEGIN
select distinct c.*from t a,t b,t c,#tmp d where
a.lid=b.lid and a.[type]=b.[type] and a.id and a.[name] = @name1 and b.[name] = d.tmp_name
and c.id>=a.id and c.id<=b.id order by c.id

select distinct c.*from t a,t b,t c,#tmp d where
a.lid=b.lid and a.[type]=b.[type] and a.id and a.[name] = d.tmp_name and b.[name] = @name2
and c.id>=a.id and c.id<=b.id order by c.id
END
--SELECT * FROM #tmp
end

drop table #result
drop table #tmp1
drop table #tmp
GO

SET QUOTED_IDENTIFIER OFF
GO
SET ANSI_NULLS ON
GO

exec search ‘文一路口‘,‘总管塘‘

cime63(归去来) ( ) 信誉：1002006-3-21 17:17:44得分: 0

http://community.csdn.net/Expert ... 8.xml?temp=.1395227

http://www.gistime.com/ReadNews.asp?NewsID=210

http://www.gistime.com/ReadNews.asp?NewsID=209

http://blog.csdn.net/bfbd/archive/2005/03/16/321216.aspx

http://topic.csdn.net/t/20050107/13/3706990.html

http://hnqyyz.com/aosai/bak/www. ... list.asp@id=368.htm

http://www.programfan.com/club/old_showbbs.asp?id=38154

http://www.3s2go.com/oldbbs/viewthread.php?tid=6978

http://www.it023.com/software/de ... 079583853d4755.html
=================================================
上面是我搜到的相关内容
小灰那个能讲讲思路吗?
另:早就知道小灰这个人了,不过今天才知道是个女孩子

iuhxq(小灰) ( ) 信誉：1002006-3-21 17:32:46得分: 0

to cime63(归去来) :

本人性别：男

换车思路：
从起点站寻找所有可以到达的站点，然后从这些站点找到达目的地的路线

cime63(归去来) ( ) 信誉：1002006-3-21 20:09:48得分: 0

呵呵
你博客上有人叫姐呢
或者那不是你的博客

cime63(归去来) ( ) 信誉：1002006-3-21 23:35:52得分: 0

我准备写个COM组件
然后调用

这样会不会好些呢?有没有跟我讨论一下?

cime63(归去来) ( ) 信誉：1002006-3-22 8:00:14得分: 0

顶上去
昨晚看了下COM的写法今晚再把算法写成COM吧

zlz_212() ( ) 信誉：1002006-3-22 8:08:44得分: 0

http://community.csdn.net/Expert ... 5.xml?temp=.8170587

hdt(倦怠) ( ) 信誉：1202006-3-22 8:25:12得分: 0

好好看看数据结构里 图 那一章

boylez(boylez) ( ) 信誉：1002006-3-22 8:27:53得分: 0
mark

cime63(归去来) ( ) 信誉：1002006-3-22 8:35:45得分: 0

呵呵
我要一直顶下去
直到解决这个问题
然后在不影响我朋友毕业答辩的情况下公开源代码
大家多提供点思路
谢谢哈

zmacro(zmacro) ( ) 信誉：972006-3-22 8:38:11得分: 0
up

liuyan55(ayan) ( ) 信誉：952006-3-22 8:38:26得分: 0
看！
tiaoci(我挑刺，我快乐) ( ) 信誉：1002006-3-22 8:50:47得分: 0

首先要对公交线路建立模型，

至于用CS 还是用 BS并不是很总要

像小灰这样乱写代码是没有用处的

最简单的：比方公交车上行和下行的线路可能不一样

iuhxq(小灰) ( ) 信誉：1002006-3-22 8:52:34得分: 0

支持开源！

tiaoci(我挑刺，我快乐) ( ) 信誉：1002006-3-22 8:54:50得分: 0

站点之间的路况可能不同（短的路线可能需要开的时间反而长）

tiaoci(我挑刺，我快乐) ( ) 信誉：1002006-3-22 8:56:31得分: 0

搜索结果要看你是需要最省钱还是最快到达

tiaoci(我挑刺，我快乐) ( ) 信誉：1002006-3-22 9:00:13得分: 0

不同公交路线站点可能同一个，但是站名不一致，

yzujjcb() ( ) 信誉：1002006-3-22 9:05:08得分: 0

Mark,学习学习

cime63(归去来) ( ) 信誉：1002006-3-22 9:05:34得分: 0

我想适当简单化处理

走的站点数就认为是时间,或者说长度
当然上行线路和下行线路的确可能是不一样的

hdt(倦怠) ( ) 信誉：1202006-3-22 9:06:47得分: 0

其实就是个有向图嘛

iuhxq(小灰) ( ) 信誉：1002006-3-22 9:11:03得分: 0

如果考虑时间或者路程，那就要加权了

计算各条通路的权值，取最小的。

kent3721(Kent) ( ) 信誉：992006-3-22 9:44:10得分: 0

有向图的问题。在存储过程里实现，b/s和C/s都是一样的！

cime63(归去来) ( ) 信誉：1002006-3-22 9:50:52得分: 0

我在CSDN里搜索过,邹建(MSSQL区的版主???)写过一个存储过程来实现,可是有人说记录达到9000条的时候,搜索整整用了三十多分钟

那样根本不行嘛

pbwf(书生) ( ) 信誉：1002006-3-22 9:58:38得分: 0

俺学习.

hdt(倦怠) ( ) 信誉：1202006-3-22 10:06:04得分: 0

关键看你的数据库设计，和算法。

nameone(萨达姆) ( ) 信誉：992006-3-22 10:36:39得分: 0

UP

net205(向MVP学习！) ( ) 信誉：1002006-3-22 10:59:41得分: 0

好帖，学习.....

[ 本帖最后由 风花雪月 于 2007-4-2 10:01 编辑 ]

风花雪月

slayerbb(名字被抢了) ( ) 信誉：1002006-3-22 11:23:06得分: 0

n个笛卡尔。。最多转乘3次 这个我同意

这样的话
设计为

出发点的车

终点站的车

中转车

开始罗列出出发和终点的车，

然后利用这两路车的交点来定位中转车

我觉得思路就是这样了。。

关键是如何提高效率。。。。

除非定义多表....

huangyj(天外飞仙的师傅) ( ) 信誉：982006-3-22 11:34:31得分: 0

其实关键还是算法和数据结构的设计吧

yuesongboy(可极) ( ) 信誉：1002006-3-22 12:24:10得分: 0

up

smile9961(正是江南好风景，落花时节又逢君。) ( ) 信誉：982006-3-22 13:24:33得分: 0

关注！

lcllcl987(毛爷爷) ( ) 信誉：1002006-3-22 14:01:56得分: 0
关注

luxianFX(路线) ( ) 信誉：1002006-3-22 15:14:00得分: 0

这个做物流的也会用到,关注

rogerfhl() ( ) 信誉：1002006-3-22 15:18:15得分: 0

关注学习接分！！！！

true_mas() ( ) 信誉：1002006-3-22 16:31:00得分: 0

很有趣啊
谁知道算法？
想知道！！！

twtetgso(*学习再学习*) ( ) 信誉：992006-3-22 17:35:50得分: 0

顶，以前试着作过，但没作出来，感觉比较复杂

cime63(归去来) ( ) 信誉：1002006-3-22 18:14:05得分: 0

大家一起来讨论啊
我准备ASP+MSQQL(存储过程)+COM(最短路径的算法)

只有晚上才有点时间,所以进展不快啊
Chulangzi(楚浪子－我要变强！) ( ) 信誉：1002006-3-22 19:06:50得分: 0

MARK，学习

windbey(北风) ( ) 信誉：1002006-3-22 19:34:16得分: 0
mark!

ljlyy(亮亮) ( ) 信誉：992006-3-22 19:36:35得分: 0

我只能顶一下了。
来学习的。

Rifhvk(Xscc.Com) ( ) 信誉：1002006-3-22 19:39:59得分: 0

。。。。你知道么，楼主。

前几天，我在应聘回来坐车的时候，突然想，如果我开公司招聘人，问他的问题就是：写个公交车查询算法。。。。。。。。。。。。。。。。。。。

bigcarp(新鲜鲤鱼) ( ) 信誉：992006-3-22 19:55:59得分: 0

关注

cime63(归去来) ( ) 信誉：1002006-3-22 20:12:50得分: 0

Rifhvk(Xscc.Com) ( ) 信誉：1002006-03-22 19:39:00得分: 0
。。。。你知道么，楼主。

前几天，我在应聘回来坐车的时候，突然想，如果我开公司招聘人，问他的问题就是：写个公交车查询算法。。。。。。。。。。。。。。。。。。。

==================================================
希望到时你能给我免试^-^^-^^-^^-^^-^^-^^-^^-^^-^^-^^-^^-^^-^^-^^-^^-^

myblessu(继续混着，到被人赶走为止) ( ) 信誉：1002006-3-22 20:41:16得分: 0

我也刚做了一个公交线路查询,还不是很好,继续改进中, http://www.hi.gov.cn/V5/bus/

prcgolf(小鸟) ( ) 信誉：1002006-3-22 21:08:57得分: 0

up

cime63(归去来) ( ) 信誉：1002006-3-22 21:20:35得分: 0

myblessu(继续混着，到被人赶走为止) ( ) 信誉：1002006-03-22 20:41:00得分: 0

我也刚做了一个公交线路查询,还不是很好,继续改进中, http://www.hi.gov.cn/V5/bus/

==============================================
我对海口不熟,所以输了几个都不能查
请问你的能查到换乘几次的?

gauss(Powered-by-Internet) ( ) 信誉：1002006-3-22 21:44:26得分: 0

关于效率,其实不用即时计算.

后台另外写程序定期更新,每两个节点之间穷举.就算一个城市有500个站,两个站之间有10条路径,那也只是500x500x10=2500000(2.5M)条记录而已. 一条记录占用1K, 数据库也只是几个G左右.

mouce(杂草) ( ) 信誉：1002006-3-22 22:00:36得分: 0

呵呵 我也是给朋友做一个基于asp的公车查询系统的毕业论文 感觉还好啦 比我自己的容易 不过还没开始做 尽量赶出算法跟大家讨论。。。 嗯 我的暂时还没考虑上下行的不同跟效率问题

cime63(归去来) ( ) 信誉：1002006-3-22 23:22:34得分: 0

楼上的谈谈

我以前也觉得不难的
谁知道越想越复杂
也许是走错路了

myblessu(继续混着，到被人赶走为止) ( ) 信誉：1002006-3-22 23:25:23得分: 0

cime63(归去来),

你输入的时候应该有提示,要输入存在的站点,比如“海口宾馆”到“海事局”

我这只是2次换乘，在海口比较小，我在海口20多年，好象根本不需要换乘这么多次。更多次的换乘其实不是很实用。
ideasky(ideasky) ( ) 信誉：762006-3-23 0:04:01得分: 0
调用sina的公交查询系统。。。。

cime63(归去来) ( ) 信誉：1002006-3-23 0:08:19得分: 0

myblessu(继续混着，到被人赶走为止) ( ) 信誉：1002006-03-22 23:25:00得分: 0

cime63(归去来),

你输入的时候应该有提示,要输入存在的站点,比如“海口宾馆”到“海事局”

我这只是2次换乘，在海口比较小，我在海口20多年，好象根本不需要换乘这么多次。更多次的换乘其实不是很实用。

==============================
我想再大些的城市三次换乘也就差不多了
再多了意义不大了
但是三次换乘还是不太容易的

baggio785(狗狗) ( ) 信誉：1002006-3-23 0:09:23得分: 0

我的思路:
表1:路线表，即所有公交线路
表2：站点表，所有站点
表3，表1和表2的对应关系表
表4，直达表，即某两个站点是直达的，主要字段，起始站点，终点站，线路
表5，一次换乘，起点站，线路一，换乘站，线路二，终点站
表6，二次换乘，起点站，线路一，换乘站一，线路二，换乘站二，线路三，终点站

表2稍微有点麻烦，因为站点名并不是唯一的，比如搜索某个站点时，可能不知道站点名称，而是输入了周围的标识性建筑，所以站点名要有好几个

表1、2、3数据填充完毕后，开始对4、5、6进行数据填充，如果你看懂了我说的意思了，算法应该明白的，只不过可以在算法上研究一下，找出合适的算法

yyueuee() ( ) 信誉：1002006-3-23 0:17:22得分: 0
www.source520.com 2万源代码狂下载

tony_zeng(海龙) ( ) 信誉：1002006-3-23 2:17:51得分: 0

简单的东西，我不考虑怎么弄个好算法了，只是解决一下问题，能够得出结果即可：

三个表（最简单化，不考虑模糊查询，单行线等其他东西）：
1，站点表stop(stop_id,stop_name)
2，路线表line(line_id,line_name)
3，路线站点表linestops( line_id, stop_id, seq )此处的seq指某站点在某线路中的顺序。

现在分析算法：
1，直达。
首先根据两个站点名获取两个站点各自的id，这里定义为id1,id2
然后查询
select line_id from
(select line_id from linestops where stop_id = id1) A,
(select line_id from linestops where stop_id = id2) B
where A.line_id = B.line_id
即得到科直达的线路列表

2,一次换乘
首先根据两个站点名获取两个站点各自的id，这里定义为id1,id2
然后搜寻两个站点通过直达方式各自能够到达的站点集合，最后他们的交集就是我们所需要的换乘站点。
select stop_id from
(
select distinct stop_idfrom linestops where line_id in
(select line_id from linestops where stop_id = id1)
)A,
(
select distinct stop_idfrom linestops where line_id in
(select line_id from linestops where stop_id = id1)
)B
where A.stop_id= B.stop_id
得到换乘站（可能有多个或0个）后，剩下的就是显示能够到达换乘站的两边线路，这通过前面的直达查询即可。

3，二次换乘
首先根据两个站点名获取两个站点各自的id，这里定义为id1,id2
算法的中心思想是：站点1能够通过直达到达的所有站点集合A，站点2能够通过直达到达的所有站点集合B，A和B之间有直达的线路。
一步一步来：
站点1能够通过直达到达的所有站点集合A：
select distinct stop_idfrom linestops where line_id in
(select line_id from linestops where stop_id = id1)
站点2能够通过直达到达的所有站点集合B：
select distinct stop_idfrom linestops where line_id in
(select line_id from linestops where stop_id = id2)
而直达的查询是
select line_id from
(select line_id from linestops where stop_id = id1) C,
(select line_id from linestops where stop_id = id2) D
where C.line_id = D.line_id

我们把=id1和=id2换成 in (select ....)A 和 in (select ...)B

这样最后我们的查询是
select line_id from
(select distinct line_id from linestops where stop_id in 【A】) C,
(select distinct line_id from linestops where stop_id in 【B】) D
where C.line_id = D.line_id
其中【A】是
（select distinct stop_idfrom linestops where line_id in
(select line_id from linestops where stop_id = id1))
其中【B】是
（select distinct stop_idfrom linestops where line_id in
(select line_id from linestops where stop_id = id2))
这样子我们找到了作为中间换乘的线路（可能有多条或者0条），对列举的的每一条假设命名为X线，下一步就是找出可以从站点1到达X任意一个站点的直达线路、和可以从站点2到达X任意一个站点的直达线路即可。
那么与前面的算法相似，我们在站点1所有能够到达的站点中去寻找和线路X相交的站点，然后再去找这两个点的线路
select stop_id from
(select distinct stop_idfrom linestops where line_id in
(select line_id from linestops where stop_id = id1))A,
(select stop_id from linestopswhere line_id = X ) B
where A.stop_id = B.stop_id
找到站点了，下面就是根据已经解决的直达查询找线路了。
站点2类似。


以上的算法有一个优点，全部是sql完成搜寻，所以asp代码只需寥寥几行循环而已。
但是缺点是：慢。毕竟可能涉及了数百次sql查询。而且只是用最简单的sql方法去算出所有可以换乘的方案，不涉及最优/最短的算法。如果是最短路径，那得用特殊结构和算法（我自己的数据结构课程设计就是这个方案）。

根据楼主的需要，用存储过程实现是最好的了，能够演示起来不会慢，代码又清爽，毕竟是课程设计，没必要弄得向商业站点一样，asp可直接调存储过程的。

还有一种折中方案能够加快效率，就是如上面狗狗这样建立表4、5、6把结果预先算出来，只保存路径最短的几种方案的话，表记录数不会很高的。

如果是一个运行的网站，根据用户的查询生成html文件缓存起来，到时遇到相同查询就直接读html返回即可。

dtot(那个女的很骚) ( ) 信誉：1002006-3-23 2:49:34得分: 0
Up~!!!!!!!!!

dtot(那个女的很骚) ( ) 信誉：1002006-3-23 2:57:01得分: 0

回::p54188(热爱生活 疼爱老婆) ( ) 信誉：100
ASP本来就有点可恶.............帮顶一下....................

cime63(归去来) ( ) 信誉：1002006-3-23 8:24:29得分: 0

只使用存储过程会很慢吧?
不过可以使用些加速的东东

tangqiaojie(小米虫) ( ) 信誉：1002006-3-23 9:10:45得分: 0

本人是菜鸟，只是路过，想问问：如果用ASP.NET该怎么做？多层结构？

jiang8282(雪山飞狐) ( ) 信誉：1002006-3-23 9:33:52得分: 0

去北方交大的论坛上看看,看完后还有几个牛人做公交换乘查询?

tony_zeng(海龙) ( ) 信誉：1002006-03-23 10:15:00得分: 0

哦？
楼上的给个url

alaiyeshi(七宝树八宝饭) ( ) 信誉：1002006-03-23 10:42:00得分: 0

可以考虑空间换时间
三次换乘以上的,先算出来,存储
三次以下的,实时去查询
这样就是初始化的时候麻烦一些

r_mosaic(大青蛙) ( ) 信誉：1002006-03-23 11:26:00得分: 0


应该给出每个站的坐标，这样可以通过方向判断来自动跳过不合理的路线，可以减少 3/4 的搜索。

bachelor2001(般若) ( ) 信誉：1002006-03-23 11:32:00得分: 0

为什么一定要用数据库,保存成特定的文件,如果文件的数据格式好的话,可能可以极大的提高算法!

gt5070073(了了了) ( ) 信誉：1002006-03-23 12:21:00得分: 0

可以去看看极品时刻表这个软件的算法，大同小异

tramp_man(遥知不是雪，为有暗香来) ( ) 信誉：1002006-03-23 15:17:00得分: 0

呵呵,快两年没上来csdn说话了! 我是广州坐车网的作者之一,我可以告诉你们,如果从实用性上来讲,要完全使用ASP来实现是不太可能的! 当然如果为了毕业设计而作,用ASP+SQL搞出来也就算了! 坐车网的整个系统不是单单一个网页,是asp+COM服务+SQLSERVER实现的. 所有的运算过程都在COM服务里,而asp只不是一个表现形式.我们的COM服务还可以接短信,brew,wap等...当然,商业上的东西,开源是不太可能的,呵呵! 不过大家可以在此讨论下换乘的算法,在坐车网的公交换乘核心算法中,我根本就没用到过书上的什么算法,当时只是根据我自己的一种思维方式设计出来的,后来加以改进和优化,发现我的算法非常符合公交换乘这块,当然,肯定不是最好的! 另外,换算出结果也只是完成了一部分,而实际上方案的优化也是一个重点,这是一个积累过程,我们的系统在方案上的优化已经有两三年的积累了.欢迎大家到坐车风去仔细研究下(http://www.zuoche.com).

foxflyhigher(雪狐--路漫漫其修远兮，吾将上下而求索！) ( ) 信誉：1002006-03-23 15:27:00得分: 0

牛呀，学习一下

tiaoci(我挑刺，我快乐) ( ) 信誉：1002006-03-23 16:02:00得分: 0

用SQL查或者预算两级换乘肯定不现实的，

像上海市公交车怎么也有几百辆，站点怎么也该上千了

如果是两次换乘，那该有多少路线啊

tiaoci(我挑刺，我快乐) ( ) 信誉：1002006-03-23 16:09:00得分: 0

像这种查询根本就不需要使用数据库

把所有车次/站点信息全部装入内存建立一个网络图

然后使用图论中的搜索算法搜就是了

zeusvenus(清柳)(C#/ASP.NET) ( ) 信誉：1282006-03-23 16:46:00得分: 0

最省事的办法就是调用Google和Baidu地图的API，公开的。

cime63(归去来) ( ) 信誉：1002006-03-23 19:07:00得分: 0
tiaoci(我挑刺，我快乐) ( ) 信誉：1002006-03-23 16:09:00得分: 0

像这种查询根本就不需要使用数据库

把所有车次/站点信息全部装入内存建立一个网络图

然后使用图论中的搜索算法搜就是了

=====================================
开玩笑了

tramp_man(遥知不是雪，为有暗香来)所说的正是我所想的
不使用COM恐怕是不行的

tony_zeng(海龙) ( ) 信誉：1002006-03-23 23:42:00得分: 0

都是牛人啊，都不看题目，楼主要的是课程设计的方案，还要求要用asp和数据库，各位老大一个要自定义数据文件保存路线结构，一个要用com组件。都是牛人，杀鸡都用牛刀。换个马桶还得是太空船用带吸的。小的佩服，给大家磕几个头！！！

cime63(归去来) ( ) 信誉：1002006-03-24 08:17:00得分: 0

tony_zeng(海龙) ( ) 信誉：1002006-03-23 23:42:00得分: 0

都是牛人啊，都不看题目，楼主要的是课程设计的方案，还要求要用asp和数据库，各位老大一个要自定义数据文件保存路线结构，一个要用com组件。都是牛人，杀鸡都用牛刀。换个马桶还得是太空船用带吸的。小的佩服，给大家磕几个头！！！

===================================================
呵呵,我是楼主,同时是我想到用COM的
当然其实纯粹存储过程也行,就是速度得不到保证,不过对毕业设计来说足够了

但是我想既然想了这么久,不如做好一点,做成自己的一份作品

[ 本帖最后由 风花雪月 于 2007-4-2 09:57 编辑 ]

风花雪月

在给一个方案

根据出行者输入的起点和终点，确定出行要选择的起始公交站点A和目的公交站点B。搜索数据库，查询站点A和站点B之间是否有相同的车经过，如果有一条或几条直达线路，通过比较选择距离最短的公交线路推荐给出行者。如果没有，则计算站点A和站点B之间有没有一个公共站点C，从站点C可以换乘到达站点B。这就有两种情况：(1)如果有，属于一次换乘。计算站点A和公共站点C之间有没有相同的公交车经过并存入集合X；同样，计算站点B和公共站点C之间有没有相同的公交车经过并存入集合Y。将这两个集合比较后就可以得到从站点A经过公共站点C到达站点B的公交线路，在这些线路中进行比较，选择距离最短的推荐给出行者。（2）如果没有公共站点C，就出现了要换乘两次的情况。将经过站点A的每条公交线路的所有站点存入集合O；同样，经过站点B的每条线路的所有站点存入集合P。比较这两个集合，先乘经过站点A的某一路车到达某一站点D，计算站点D与站点B之间有没有公共站点E,如果有则站点D、E为换乘站点。这种方案可能有多种，比较选择距离最短的推荐给出行者。如果不存在公共站点E，说明经过两次换乘无法从站点A到达站点B，停止搜索计算。

公交出行最优路线具体算法：

1） 输入起始站点A和目的站点B；

2） 搜索系统数据库，经过起始站点A的公交线路存为X(i)(i=1,2,3…,m,m为正整数)，经过目的站点B的公交线路存为Y(j)(j=1,2,3,…n,.n为正整数)；

3） 判断是否有X(i)=Y(j)，将满足条件的存入Z。若Z＝1，则该条公交线路X(i)即Y(j)为从站点A到站点B的直达最优线路，输出结果并结束运算。Z≥1，计算Z中各条线路的距离，选择一条距离最短的线路，输出结果并结束运算；

4） 搜索系统数据库，公交线路X(i)所包含的站点存为O(i,u)(u=1,2,3…,g,g为正整数)公交线路Y(j)所包含的站点存为P(j,v)(v=1,2,3…,h,h为正整数)；

5） 判断是否有O(i,u)= P(j,v)，将满足条件的存入W。若W＝1，则站点O(i,u)即P(j,v)为从站点A到站点B的一次换乘站点，公交线路X(i)，Y(j)为换乘一次的最优路线，输出结果并结束运算。若W≥1，分别计算每条换乘路线的距离，选择一条距离最短的线路，输出结果并结束运算；

6） 搜索系统数据库，经过站点O(i,u)的公交线路存为R(k)(k=1,2,3…,p,p为正整数)，公交线路R(k)所包含的站点存为G(k,t)(t=1,2,3…,q,q为正整数)；

7）判断是否有G(k,t)=P(j,v)，将满足条件的存入S。若S＝1，则站点G(k,t)即P(j,v)为从站点A到站点B的二次换乘站点，公交线路X (i)，R(k)，Y(j)为换乘二次的最优路线，输出结果并结束运算。若S≥1，分别计算每条换乘二次的路线距离，选择一条距离最短的线路，输出结果并结束运算；

8） 以上步骤没有找到合适的公交线路,输出“没有找到换乘次数不超过两次的最优公交线路”，结束运算。

本文讨论的公交出行最优路线算法，主要是以距离为标准。在得出了换乘方案之后，可以进一步考虑时间因素，从而找到更具优胜性的换乘方案，这有待进行进一步的探讨、研究。

[ 本帖最后由 风花雪月 于 2007-4-2 09:54 编辑 ]

wudian30

我以前的毕业设计正好是 公交查询系统
ASP+SQL
代码 数据库 论文
有需要的话 联系我 QQ:85116454