－－里面有一个杭州的例子数据（它的出处：csdn blog又“CSDN Blog正在进行维护，预计一小时内完成。”）
－－刚才试了一下，基本都是1次转车就可到达，怀疑sql有问题
－－把线路的连通关系用图画了出来，真的是这样！！


散文一百讨论公交换乘的Web实现问题(公交查询)
作　　者： cime63 (归去来)
等　　级：
信 誉 值： 100
所属社区： .NET技术 ASP.NET
问题点数： 100
回复次数： 89
发表时间： 2006-3-21 13:43:14




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

呵呵,不要告诉我去看迪杰特斯拉算法或者弗洛伊德算法啊
现在就是想讨论一下怎么实现好一些


cime63(归去来) ( ) 信誉：100 2006-3-21 13:50:04 得分: 0



包括数据库的设计
想了半天都没想好怎么存储会在程序实现时方便一些



Top
p54188(热爱生活 疼爱老婆) ( ) 信誉：100 2006-3-21 13:57:05 得分: 0



asp?的确挺可恶的
帮顶~



Top
huwei2003(凡) ( ) 信誉：100 2006-3-21 14:10:01 得分: 0



UP



Top
cime63(归去来) ( ) 信誉：100 2006-3-21 14:10:41 得分: 0



我有想过用ASP调用COM组件,然后用VC写个COM组件
但是现在还不能确定数据库的结构啊
想了半天,总觉得在写程序的时候会很麻烦



Top
BookSirSwordsMan(书生剑客) ( ) 信誉：100 2006-3-21 14:11:08 得分: 0



up

========================================================
我一定要超过他！！！！！！
做出我最强的东西！！！！！
再和他一比高下！！！！！！
========================================================





Top
cho__cho(CHO) ( ) 信誉：100 2006-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)
);
很垃圾的设计，但我现在只是想和你们一起讨论讨论的
查询站点，记录每个站点所经过的车次，再查车，再查站，反复查询（递归），将每次查询得到的结果存放在一个多维数组中......
程序现在还没时间写出来，这个方法是我在一本讲数据结构的书上看的
请大家建议，我会尽快抽时间将程序写出来





Top
cime63(归去来) ( ) 信誉：100 2006-3-21 14:35:15 得分: 0



我再想一下



Top
Response_chen(俺村俺最丑) ( ) 信誉：95 2006-3-21 15:24:31 得分: 0




偶的想法，尽供参考：

图的长度问题

偶的实现

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

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

B/S ,C/S实现方式是一样的



Top
sz315(名剑) ( ) 信誉：100 2006-3-21 15:44:51 得分: 0



我做过这个。



Top
rd16() ( ) 信誉：92 2006-3-21 15:45:51 得分: 0



楼主的意思可能是：

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


这个我以前做过，不过没有做出来。关注中。。。。



Top
rd16() ( ) 信誉：92 2006-3-21 15:47:11 得分: 0



TO:sz315(名剑)

是B/S吗。。看看代码



Top
cime63(归去来) ( ) 信誉：100 2006-3-21 15:49:01 得分: 0



嗯,意思就是,没有直达车的话,查出换乘的车次,车站等等
我觉得最多换乘三次就够了



Top
cime63(归去来) ( ) 信誉：100 2006-3-21 15:50:41 得分: 0



TO:sz315(名剑)

同rd16() ( ) 信誉：92 一样,希望看看代码
如果不行的话,至少谈一下思路
3Q



Top
netsd(极品非车) ( ) 信誉：100 2006-3-21 15:58:38 得分: 0



其实跟B/S C/S没有关系.看样子是楼主知道算法,是不知道在ASP中怎么实现.除了用COM还真没有更好的办法.不过ASP调用COM挺可误的,COM有改动还在再注册.
楼主有算法分享出来吧,以前我也搞过,也没搞出来



Top
rd16() ( ) 信誉：92 2006-3-21 16:00:28 得分: 0



TO:netsd(极品非车)
数据量大的话B/S不好做，除非有非常好的算法.



Top
rd16() ( ) 信誉：92 2006-3-21 16:04:57 得分: 0



楼主，这里有答案了。

http://blog.csdn.net/iuhxq/archive/2005/09/08/475037.aspx



Top
cime63(归去来) ( ) 信誉：100 2006-3-21 16:30:10 得分: 0



存储过程啊
看来得放弃ACCESS数据库了



Top
chaos_blue(chaos（混沌）) ( ) 信誉：100 2006-3-21 16:39:29 得分: 0



mark




Top
rd16() ( ) 信誉：92 2006-3-21 16:42:53 得分: 0



TO:cime63(归去来)

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



Top
scjtswj() ( ) 信誉：100 2006-3-21 16:47:11 得分: 0



不做过
顶



Top
cime63(归去来) ( ) 信誉：100 2006-3-21 16:48:43 得分: 0



rd16() ( ) 信誉：92 2006-03-21 16:42:00 得分: 0


TO:cime63(归去来)

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


=================================================
是这样
可是我那朋友如果什么都学过的话就不用让我给他做毕业设计了



Top
cime63(归去来) ( ) 信誉：100 2006-3-21 17:02:49 得分: 0



小灰那个只支持一次转乘啊

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



Top
iuhxq(小灰) ( ) 信誉：100 2006-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




Top
iuhxq(小灰) ( ) 信誉：100 2006-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




Top
iuhxq(小灰) ( ) 信誉：100 2006-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.Search Script 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.Search Script 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.id<b.id
and 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 TOP 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.id<b.id
and 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<b.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<b.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 '文一路口','总管塘'





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



http://community.csdn.net/Expert/topic/4628/4628908.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.mydrs.org/program/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/develop/web_develop/asp/2004-03-18/1079583853d4755.html
=================================================
上面是我搜到的相关内容
小灰那个能讲讲思路吗?
另:早就知道小灰这个人了,不过今天才知道是个女孩子



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



to cime63(归去来) :

本人性别：男


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



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



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



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



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

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



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



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



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



http://community.csdn.net/Expert/topic/4552/4552645.xml?temp=.8170587



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



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




Top
boylez(boylez) ( ) 信誉：100 2006-3-22 8:27:53 得分: 0



mark



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



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



Top
zmacro(zmacro) ( ) 信誉：97 2006-3-22 8:38:11 得分: 0



up



Top
liuyan55(ayan) ( ) 信誉：95 2006-3-22 8:38:26 得分: 0



看！



Top
tiaoci(我挑刺，我快乐) ( ) 信誉：100 2006-3-22 8:50:47 得分: 0



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

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

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

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



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



支持开源！





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



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





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



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



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



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



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



Mark,学习学习




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



我想适当简单化处理

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



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



其实就是个有向图嘛




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



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

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



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



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



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



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

那样根本不行嘛



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



俺学习.



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



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




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



UP



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



好帖，学习.....



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



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

这样的话
设计为

出发点的车

终点站的车

中转车

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

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

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

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

除非定义多表....



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



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



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



up



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



关注！



Top
lcllcl987(毛爷爷) ( ) 信誉：100 2006-3-22 14:01:56 得分: 0



关注



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



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



Top
rogerfhl() ( ) 信誉：100 2006-3-22 15:18:15 得分: 0



关注学习接分！！！！



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



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



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



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



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



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

只有晚上才有点时间,所以进展不快啊



Top
Chulangzi(楚浪子－我要变强！) ( ) 信誉：100 2006-3-22 19:06:50 得分: 0



MARK，学习



Top
windbey(北风) ( ) 信誉：100 2006-3-22 19:34:16 得分: 0



mark!



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



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



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



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

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





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



关注



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



Rifhvk(Xscc.Com) ( ) 信誉：100 2006-03-22 19:39:00 得分: 0


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

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

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



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



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



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



up



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



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


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


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



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



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

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



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



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



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



楼上的谈谈

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



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



cime63(归去来),

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

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




Top
ideasky(ideasky) ( ) 信誉：76 2006-3-23 0:04:01 得分: 0



调用sina的公交查询系统。。。。



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



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


cime63(归去来),

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

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



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



Top
baggio785(狗狗) ( ) 信誉：100 2006-3-23 0:09:23 得分: 0



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

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


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



Top
yyueuee() ( ) 信誉：100 2006-3-23 0:17:22 得分: 0



www.source520.com 2万源代码狂下载



Top
tony_zeng(海龙) ( ) 信誉：100 2006-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_id from linestops where line_id in
(select line_id from linestops where stop_id = id1)
)A,
(
select distinct stop_id from 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_id from linestops where line_id in
(select line_id from linestops where stop_id = id1)
站点2能够通过直达到达的所有站点集合B：
select distinct stop_id from 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_id from linestops where line_id in
(select line_id from linestops where stop_id = id1))
其中【B】是
（select distinct stop_id from 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_id from linestops where line_id in
(select line_id from linestops where stop_id = id1))A,
(select stop_id from linestops where line_id = X ) B
where A.stop_id = B.stop_id
找到站点了，下面就是根据已经解决的直达查询找线路了。
站点2类似。


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

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

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

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



Top
dtot(那个女的很骚) ( ) 信誉：100 2006-3-23 2:49:34 得分: 0



Up~!!!!!!!!!



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



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



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



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



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



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



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



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



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


哦？
楼上的给个url


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


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


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


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


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


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


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


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


Top