关于查询公交车线路换乘的算法！
小弟最想做一个查询公交车线路的小系统。
原理是这样，就是输入出发地，目的地。系统就可以找到相应的公交车线路。这里的线路有可能一条线路就可以到达，也可能要在中途换乘其它线路才可以到达。
在这个查询里面，我现在只想到用“回溯法”去实现。
请问那位高手之前也做过类似的东西，有没有更好的算法去实现呢？
问题点数：30、回复次数：14Top
1 楼caihanchao（超超）回复于 2006-03-18 16:38:40 得分 0
UPUPUPUPTop
2 楼enjsky（郭志军）回复于 2006-03-18 16:51:09 得分 0
好好看看 " 运筹学 " 里面的"中国邮递员问题 " 就是早最短路径的Top
3 楼luoboqingcai（萝卜青菜）回复于 2006-03-18 17:04:27 得分 0
A* ?Top
4 楼dh20156（风之石）回复于 2006-03-18 18:21:16 得分 10
原来研究了一下，没有优化：
Create Procedure GetTheLine
@start varchar(20),/*始发站*/
@end varchar(20),/*终点站*/
@Max int /*最大换乘次数*/
As
If @start<>''
Begin
Set nocount on
Create Table #ts(placeA varchar(8000),placeB varchar(10))
Insert into #ts Select distinct placeA+'→'+placeB,placeB From station Where placeA=@start
declare @i int
Set @i = 0
While (@i<@Max)
Begin
If (Select count(1) From station,#ts Where station.placeA=#ts.placeB)>1
Begin
If (Select count(1) From #ts,station Where station.placeA=#ts.placeB And charindex(station.placeB,#ts.placeA)>0)<@Max
Begin
Insert into #ts Select #ts.placeA+'→'+station.placeB,station.placeB From station,#ts Where station.placeA=#ts.placeB
End
End
Else
Begin
Update #ts Set #ts.placeA=#ts.placeA+'→'+station.placeB,#ts.placeB=station.placeB From station,#ts Where station.placeA=#ts.placeB
End
Select distinct * into #Tmp From #ts
Delete From #ts
Insert Into #ts Select * from #Tmp
Drop Table #Tmp
Set @i = @i+1
End
Set nocount off
/*
If @end<>''
Begin
--所有从始发站点出发经过终点站的乘车路线
Select distinct *,len(replace(placeA,'→','')) As changeTimes From #ts Where placeB=@end Order by changeTimes
End
Else
Begin
--所有从始发站点出发的乘车路线
Select distinct *,len(replace(placeA,'→','')) As changeTimes From #ts Order by placeB,changeTimes
End
*/
--最短乘车路线
Select Top 1 *,len(replace(placeA,'→','')) As changeTimes From #ts Where placeB=@end Order by placeB,changeTimes
Drop Table #ts
End
GO
Set nocount on
Create Table station(placeA varchar(10),placeB varchar(10),placeType varchar(10),placeName varchar(10))
Insert into station Select 'a','b','公路','A公路'
Union Select 'b','c','公路','B公路'
Union Select 'c ','d','公路','C公路'
Union Select 'd','e','公路','D公路'
Union Select 'e','f','公路','E公路'
Union Select 'f','g','公路','F公路'
Union Select 'g','h','公路','G公路'
Union Select 'a','c','公路','I公路'
Union Select 'c','g','公路','J公路'
Union Select 'g','e','公路','K公路'
Union Select 'e','i','公路','L公路'
Union Select 'i','j','公路','M公路'
Union Select 'i','k','公路','N公路'
Union Select 'j','k','公路','O公路'
Union Select 'k','l','公路','P公路'
Union Select 'l','m','公路','Q公路'
Union Select 'k','n','公路','R公路'
Set nocount off
declare @s varchar(20),@e varchar(20),@Max int
Set @s = 'a'
Set @e = 'n'
Set @Max = 20
exec GetTheLine @s,@e,@Max
Drop Table station
Drop Procedure GetTheLineTop
5 楼charles_y（每天上网一小时）回复于 2006-03-18 19:13:46 得分 0
参考Dijkstra最短路径算法
不过还要考虑很多方面：路径最短、转车次数最少....Top
6 楼henry3695（henry(老师说学好正则可以赚美元的)）回复于 2006-03-18 20:53:20 得分 10
数据表的设计,这个问题我曾经考虑过,数据库设计很重要
id BusNo Station NextStation
1 1 aa bb
2 1 bb cc
3 1 cc dd
4 2 bb aa
5 2 aa ee
6 2 ee ccTop
7 楼caihanchao（超超）回复于 2006-03-20 16:50:44 得分 0
UPUPUPTop
8 楼yespie（yespie）回复于 2006-03-20 17:30:39 得分 0
不错不错，是好东西。
Top
9 楼gelaozide（青蛙伯爵）回复于 2006-03-20 18:01:16 得分 0
markTop
10 楼caihanchao（超超）回复于 2006-03-24 09:32:36 得分 0
继续讨论！
呵。。。。有没有更好的方法呢？Top
11 楼nmchenliang（小亮）回复于 2006-04-25 11:30:55 得分 10
我觉得用广度优先搜索就可以解决问题，不需要用迪杰斯特拉，因为两个公交站间的权值可以理解成1，如果在全国的公路交通系统中求A到B怎样走最近，可以用迪杰斯特拉。Top
12 楼zlkingdom（风之悲伤）回复于 2006-04-25 12:04:58 得分 0
我觉得应该还是优先确定下来表的设计，然后根据表结构来设计程序，不过算法方面一直没想好用什么可以达到最优效果Top
13 楼chenmin9（明明）回复于 2006-04-25 12:12:35 得分 0
up,up
Top
14 楼accpbenson（叮噹大雄☆☆☆☆☆）回复于 2006-04-25 14:16:48 得分 0
關注ingTop
