公交车站点查询的算法讨论

Question

参考这个：http://search.csdn.net/Expert/topic/681/681717.xml?temp=.7095911

Answer 1

关于“公交出行算法”网上或论坛有不少了！
现在问题只是把现成的算法，用t-sql表达出来！

Answer 2

to libin_ftsafe(子陌红尘) 
你提供的帖子里介绍的方法和我想的一样，但是如果转1次车用此方法还行，但是转2次的话运算太多，效率不高。我个人认为可能要在数据库设计上下点功夫。我也在考虑中……

Answer 3

可以借助于oracle中的bom算法完成（我觉得是可以完成的）

Answer 4

--示例--示例数据
create table Line(lineID int,state nvarchar(10),orderid int,primary key(lineID,orderid))
insert Line select 1,'鼓楼'  ,1
union  all  select 1,'新街口',2
union  all  select 1,'汽车站',3
union  all  select 1,'火车站',4
union  all  select 2,'新街口',1
union  all  select 2,'飞机场',2
union  all  select 2,'天安门',3
union  all  select 3,'天安门',1
union  all  select 3,'石门坎',2
union  all  select 3,'驾校'  ,3
go--查询的存储过程
create proc p_qry
@begin_state nvarchar(10),
@end_state nvarchar(10)
as
set nocount on
declare @l int
set @l=0
select lineID,line=cast('('+rtrim(lineID)+': '+rtrim(state) as varchar(8000))
,state,orderid=orderid+1,level=@l,gid=1
into #t from Line where state=@begin_state
while @@rowcount>0 and not exists(select * from #t where state=@end_state)
begin
set @l=@l+1
insert #t(line,lineID,state,orderid,level,gid)
select 
line=a.line+case
when a.lineID=b.lineID
then '->'+rtrim(b.state)
else ') => ('+rtrim(b.lineID)+': '+rtrim(b.state)
end,
lineID=b.lineID,state=b.state,orderid=b.orderid+1,@l,
case when a.lineID=b.lineID then a.gid else a.gid+1 end
from #t a,Line b
where a.level=@l-1
and(
a.lineID=b.lineID and a.orderid=b.orderid
or 
a.state=b.state and a.lineID<>b.lineID)
end
select 起点站=@begin_state
,终点站=@end_state
,转车次数=gid
,经过站数=case when gid<3 then @l else @l-gid+2 end
,乘车线路=line+')' 
from #t where level=@l and state=@end_state
go--调用
exec p_qry '鼓楼','火车站'
exec p_qry '鼓楼','飞机场'
exec p_qry '鼓楼','石门坎'
go--删除测试
drop table Line
drop proc p_qry/*--测试结果
起点站        终点站        转车次数        经过站数        乘车线路                                                                                                                                                                                                                                                             
---------- ---------- ----------- ----------- ---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- 
鼓楼         火车站        1           3           (1: 鼓楼->新街口->汽车站->火车站)起点站        终点站        转车次数        经过站数        乘车线路                                                                                                                                                                                                                                                             
---------- ---------- ----------- ----------- ---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- 
鼓楼         飞机场        2           3           (1: 鼓楼->新街口) => (2: 新街口->飞机场)起点站        终点站        转车次数        经过站数        乘车线路                                                                                                                                                                                                                                                             
---------- ---------- ----------- ----------- ---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- 
鼓楼         石门坎        3           5           (1: 鼓楼->新街口) => (2: 新街口->飞机场->天安门) => (3: 天安门->石门坎)
--*/

Answer 5

--功能完全实现的工交算法，但是速度不快create table Line(lineID int,state nvarchar
(10),orderid int,primary key(lineID,orderid))
insert Line select 1,'鼓楼'  ,1
union  all  select 1,'新街口',2
union  all  select 1,'汽车站',3
union  all  select 1,'火车站',4
union  all  select 2,'新街口',1
union  all  select 2,'飞机场',2
union  all  select 2,'天安门',3
union  all  select 3,'天安门',1
union  all  select 3,'石门坎',2
union  all  select 3,'驾校'  ,3
go-- 查询的存储过程
create proc p_qry
@begin_state nvarchar(10),
@end_state nvarchar(10)
as
set nocount on
declare @l int
--正向搜索线路
set @l=0
--把数据插入临时表
select lineID,line=cast('('+rtrim(lineID)
+': '+rtrim(state) as varchar(8000))
,state,orderid=orderid+1,level=@l,gid=1
into #t from Line where state=@begin_state
while @@rowcount>0 and not exists(select * from 
#t where state=@end_state) and exists(select * from line where state=@end_state)
begin
set @l=@l+1
-- 如果循环次数大于所有站点数，则跳出循环
if @l>(select count(*) from line)
break
else 
--把数据插入临时表
insert #t(line,lineID,state,orderid,level,gid)
select 
line=a.line+case
when a.lineID=b.lineID
then '->'+rtrim(b.state)
else ') => ('+rtrim(b.lineID)+': '+rtrim(b.state)
end,
lineID=b.lineID,state=b.state,orderid=b.orderid+1,
@l,
case when a.lineID=b.lineID then a.gid else 
a.gid+1 end
from #t a,Line b
where a.level=@l-1
and(
a.lineID=b.lineID and a.orderid=b.orderid
or 
a.state=b.state and a.lineID<>b.lineID)
continue
end-- 
-- 如果正向思索存在线路，则选择出来
if exists(select 起点站=@begin_state
,终点站=@end_state
,转车次数=gid
,经过站数=case when gid<3 then @l else @l-gid+2 
end
,乘车线路=line+')' 
from #t where level=@l and state=@end_state)begin
select 起点站=@begin_state
,终点站=@end_state
,转车次数=gid
,经过站数=case when gid<3 then @l else @l-gid+2 
end
,乘车线路=line+')' 
from #t where level=@l and state=@end_stateend
--如果正向搜索不存在线路，则反向搜索
if not exists(select 起点站=@begin_state
,终点站=@end_state
,转车次数=gid
,经过站数=case when gid<3 then @l else @l-gid+2 
end
,乘车线路=line+')' 
from #t where level=@l and state=@end_state)begin--反向搜索线路向搜索线路
set nocount onset @l=0
select lineID,line=cast('('+rtrim(lineID)
+': '+rtrim(state) as varchar(8000))
,state,orderid=orderid-1,level=@l,gid=1
into #m from Line where state=@begin_state
while @@rowcount>0 and not exists(select * from 
#m where state=@end_state) and exists(select * from line where state=@end_state)
begin
set @l=@l+1
if @l>(select count(*) from line)
break
else 
insert #m(line,lineID,state,orderid,level,gid)
select 
line=a.line+case
when a.lineID=b.lineID
then '->'+rtrim(b.state)
else ') => ('+rtrim(b.lineID)+': '+rtrim(b.state)
end,
lineID=b.lineID,state=b.state,orderid=b.orderid-1,
@l,
case when a.lineID=b.lineID then a.gid else 
a.gid+1 end
from #m a,Line b
where a.level=@l-1
and(
a.lineID=b.lineID and a.orderid=b.orderid
or 
a.state=b.state and a.lineID<>b.lineID)
continue
end
select 起点站=@begin_state
,终点站=@end_state
,转车次数=gid
,经过站数=case when gid<3 then @l else @l-gid+2 
end
,乘车线路=line+')' 
from #m where level=@l and state=@end_state-- 从正反两面判断是否存在路线，如果不存在，则提示！
if not exists(select 起点站=@begin_state
,终点站=@end_state
,转车次数=gid
,经过站数=case when gid<3 then @l else @l-gid+2 
end
,乘车线路=line+')' 
from #t where level=@l and state=@end_state) 
and 
not exists(select 起点站=@begin_state
,终点站=@end_state
,转车次数=gid
,经过站数=case when gid<3 then @l else @l-gid+2 
end
,乘车线路=line+')' 
from #m where level=@l and state=@end_state) -- print '没有符合条件的记录，请重新输入数据！！！' 
begin
print '没有找到符合条件的记录'
end
end
go--调用 exec p_qry '石门坎','鼓楼'
exec p_qry '火车站','鼓楼'
exec p_qry '鼓楼','石门坎'
exec p_qry '石门坎','鼓楼'
go-- 删除测试
drop table Line
drop proc p_qry

Answer 6

--那位大哥还能不能帮我完善一下，假如做的好的话，我可以出钱买算法，请大家给我再优化一下，主要是
--速度问题
create table Line(lineID int,state nvarchar
(10),orderid int,primary key(lineID,orderid))
insert Line select 1,'鼓楼'  ,1
union  all  select 1,'新街口',2
union  all  select 1,'汽车站',3
union  all  select 1,'火车站',4
union  all  select 2,'新街口',1
union  all  select 2,'飞机场',2
union  all  select 2,'天安门',3
union  all  select 3,'天安门',1
union  all  select 3,'石门坎',2
union  all  select 3,'驾校'  ,3
go-- 查询的存储过程
create proc p_qry
@begin_state nvarchar(10),
@end_state nvarchar(10)
as
set nocount on
declare @l int
--正向搜索线路
set @l=0
--把数据插入临时表
select lineID,line=cast('('+rtrim(lineID)
+': '+rtrim(state) as varchar(8000))
,state,orderid=orderid+1,level=@l,gid=1
into #t from Line where state=@begin_state
while @@rowcount>0 and not exists(select * from 
#t where state=@end_state) and exists(select * from line where state=@end_state)
begin
set @l=@l+1
-- 如果循环次数大于所有站点数，则跳出循环
if @l>(select count(*) from line)
break
else 
--把数据插入临时表
insert #t(line,lineID,state,orderid,level,gid)
select 
line=a.line+case
when a.lineID=b.lineID
then '->'+rtrim(b.state)
else ') => ('+rtrim(b.lineID)+': '+rtrim(b.state)
end,
lineID=b.lineID,state=b.state,orderid=b.orderid+1,
@l,
case when a.lineID=b.lineID then a.gid else 
a.gid+1 end
from #t a,Line b
where a.level=@l-1
and(
a.lineID=b.lineID and a.orderid=b.orderid
or 
a.state=b.state and a.lineID<>b.lineID)
continue
end-- 
-- 如果正向思索存在线路，则选择出来
if exists(select 起点站=@begin_state
,终点站=@end_state
,转车次数=gid
,经过站数=case when gid<3 then @l else @l-gid+2 
end
,乘车线路=line+')' 
from #t where level=@l and state=@end_state)begin
select 起点站=@begin_state
,终点站=@end_state
,转车次数=gid
,经过站数=case when gid<3 then @l else @l-gid+2 
end
,乘车线路=line+')' 
from #t where level=@l and state=@end_stateend
--如果正向搜索不存在线路，则反向搜索
if not exists(select 起点站=@begin_state
,终点站=@end_state
,转车次数=gid
,经过站数=case when gid<3 then @l else @l-gid+2 
end
,乘车线路=line+')' 
from #t where level=@l and state=@end_state)begin--反向搜索线路向搜索线路
set nocount onset @l=0
select lineID,line=cast('('+rtrim(lineID)
+': '+rtrim(state) as varchar(8000))
,state,orderid=orderid-1,level=@l,gid=1
into #m from Line where state=@begin_state
while @@rowcount>0 and not exists(select * from 
#m where state=@end_state) and exists(select * from line where state=@end_state)
begin
set @l=@l+1
if @l>(select count(*) from line)
break
else 
insert #m(line,lineID,state,orderid,level,gid)
select 
line=a.line+case
when a.lineID=b.lineID
then '->'+rtrim(b.state)
else ') => ('+rtrim(b.lineID)+': '+rtrim(b.state)
end,
lineID=b.lineID,state=b.state,orderid=b.orderid-1,
@l,
case when a.lineID=b.lineID then a.gid else 
a.gid+1 end
from #m a,Line b
where a.level=@l-1
and(
a.lineID=b.lineID and a.orderid=b.orderid
or 
a.state=b.state and a.lineID<>b.lineID)
continue
end
select 起点站=@begin_state
,终点站=@end_state
,转车次数=gid
,经过站数=case when gid<3 then @l else @l-gid+2 
end
,乘车线路=line+')' 
from #m where level=@l and state=@end_state-- 从正反两面判断是否存在路线，如果不存在，则提示！
if not exists(select 起点站=@begin_state
,终点站=@end_state
,转车次数=gid
,经过站数=case when gid<3 then @l else @l-gid+2 
end
,乘车线路=line+')' 
from #t where level=@l and state=@end_state) 
and 
not exists(select 起点站=@begin_state
,终点站=@end_state
,转车次数=gid
,经过站数=case when gid<3 then @l else @l-gid+2 
end
,乘车线路=line+')' 
from #m where level=@l and state=@end_state) -- print '没有符合条件的记录，请重新输入数据！！！' 
begin
print '没有找到符合条件的记录'
end
end
go--调用 exec p_qry '石门坎','鼓楼'
exec p_qry '火车站','鼓楼'
exec p_qry '鼓楼','石门坎'
exec p_qry '石门坎','鼓楼'
go-- 删除测试
drop table Line
drop proc p_qry