谁有公交换乘的算法？或思路？求教！万分感谢！

同意 leeky(雅痞·千年虫) ( ) 信誉：94 應該是最短路径或者最最小花费

成都市公共交通成用引导系统
张元标将海峰李经伟
( 成都理工大学应用数学系 )一．总体思想点击地图任意两个车站——始发站和目的站，或通过对话框输入；系统调用数据库，通过搜索算法，找出从始发站到达目的站的公交路径，并算出路径长度；返回信息，为用户提供参考。
二.地图处理•网格化地图
扫描下来的地图图片是由连续点构成的，可以把这个地图图片认为是一个有限实数平面区域；在这个有限实数平面区域内的任意一点，即任意一实数对（x,y），一一对应于地图上的一个点。
　　　　　
三．数据库四．算法1.算法思想
1.1.输入查询信息
通过用户点击地图或文本输入，系统便获得用户提供的始发站点坐标和目的站点坐标,调用数据库，得到始发站和目的站的网眼标号s1和s2（由程序自动生成）。1.2．提出车站集概念
在现实生活中，存在着这样的情况：两车站间的距离较短，允许从一车站步行到另一车站，这样就为查找最佳路径提供更大的空间。
这样，就可以实现这些情况：从始发站步行到另一站A，再从站A乘公交车直达目的站；或从始发站乘公交车直达到另一站B，再从站B步行到目的站；或从始发站乘公交车到中转站C，再从中转站C步行到中转站D，再从中转站D乘公交车到目的站；或是以上情况的多种组合。
为了实现这些情况，有必要提出车站集的概念。车站集是以某个车站所在网眼为中心，加上该网眼在8个方向上与该网眼相邻的8个网眼，把这共9个网眼所覆盖的车站作为该车站对应的车站集.有了这个车站集的概念，系统就有了更大的查找空间进行模糊查找最佳路径。1.3．模糊查找
在现实生活中，乘用公交车有两种情况：直达或转车。模糊查找分别考虑这两种情况。1.3.1．直达
直达就是在途径始发车站集车站和目的车站集车站的公交路线中找出相同的公交路线，即为直达路线。•找出路线集合•找出直达路线
•说明
若直达路线的始发车站与用户提供的始发车站不同或直达路线的目的车站与用户提供的目的车站不同，则是需要步行达到的。1．3．2．转车
转车就是从始发车站集车站出发，到中转站集车站A转车到达目的站集车站，相当于寻找两条交线的交点。•找出路线集合•找出扩展车站集合
•找出模糊车站集合•找出转车路线1．4．路径的度量
有了以上的算法，就可以找到从始发站到目的站的转车路径，这样的路径很可能有多条；为了比较多条路径的长短，系统是以站为单位进行衡量的，即从某站A到站A紧跟的下一站的距离为1站，作为1个单位长度。1．5．记录查找经验
为了提高查找速度，系统把查找过的路径作为经验存储到数据库中。当用户进行查找时，先访问数据库，如果用户输入的始发站和目的站在数据库中已有记录，则直接从数据库中凋出信息；如果没有记录再调用查找算法进行查找。

其实可以不需要考虑步行的问题，这个问题可以在数据库方面解决，比如说对于一个车站来说可以有一个站名，和一个地点编号，查找时可按地点编号查找，也就是说相近的车站可能就使用的个地点编号，这种情况在北京是比较多的，比如说大北窑与八王坟，好些车实际停的就几步距离，就可以用一个编号。
公交换乘可以先算出两点间的全部路线，然后算出每条路线的公里数，换乘次数，然后根据需求来显示，至于全部路线，当然也要有要求，否则会出现比如从北京到天津就可能会有北京 ->广州 -> 天津的路线出来，要考虑到行车的方向与目的地的方向是否不什么有太大的偏差，这只是思路，至于实际算法可能有很多地方要考虑，如公交可能一会儿向北，一会儿向东，也可能你要去西面，而公交是向东走两站又折回的祝你好运，同时关注这个问题

以前的贴主　　题：  高难度的算法～～走过路过的请进来看一下
作　　者：  baggio785 (狗狗)
等　　级：
信誉值：  99
所属论坛：  MS-SQL Server 数据库开发
问题点数：  100
回复次数：  13
发表时间：  2004-05-20 20:54:33



我现在做公交线路的换乘
直达的和一次换乘的都搞定了
现在就差二次换乘了，程序已经写好了，但是速度太慢
请大家帮帮忙～～
表结构如下，我只列一些主要的字段线路表－line
自增     线路名
id       line_name站点表-stop
自增     站点名
id       stop_name线路站点表－line_stop
自增     线路ID     站点ID     上行还是下行     顺序
id       line_id    stop_id     upordown        serial我的思路是：
1 根据起始站点的ID－startid，得到与startid直达的站点（change_stop_1）,并得到它们之间的线路(change_line_1)
2 根据终点站点的ID－endid，得到与endid直达的站点（change_stop_2）,并得到它们之间的线路(change_line_2)
3 判断change_stop_1和change_stop_2是否直达请大家帮我看看，程序我已经写好了，但是还不够优化，希望大家根据我的提供的这些，帮我想想好办法
如果需要的话，我可以把程序贴出来，之所以没有贴出来，只怕大家没有耐心看下去


回复人： zjcxc(邹建) ( ) 信誉：316  2004-05-20 21:19:00  得分:0

  在你的线路站点表－line_stop
中加一下字段,下站ID即:
线路站点表－line_stop
自增     线路ID     站点ID     下站ID    上行还是下行     顺序
id       line_id    stop_id    next_id   upordown        serial
这样就好查询多了(个人觉得速度也快)--直达站就一次查询
select * from line_stop
where stop_id=@起点站ID  and next_id=@终点站ID
--一次换乘就这样查询:
select * from line_stop a
where stop_id=@起点站ID  and exists(
select 1 from line_stop
where next_id=@终点站ID and stop_id=a.next_id)
--二次换就这样查询
select * from line_stop a
where stop_id=@起点站ID  and exists(
select 1 from line_stop aa
where stop_id=a.next_id and exists(
select 1 from line_stop
where stop_id=a.next_id
and next_id=@终点站ID))

接上Top

回复人： playyuer(双规干部) ( ) 信誉：112  2004-05-20 22:12:00  得分:0

  展开网络
在网络中，一个项目可以有多个上级。例如，下面的数据显示一些城市间的航班：Departure                          Destination
---------------------------------- ----------------------------------
Chicago                            New York
Chicago                            Milwaukee
Denver                             Chicago
Seattle                            Chicago
Seattle                            Denver
Seattle                            San Francisco                     对于上述数据而言，一个常见的问题就是找到给定的两个城市之间的所有航线：Itineraries
----------------------------------
Seattle, Chicago, New York
Seattle, Denver, Chicago, New York若要解决这一问题，可以将"展开层次结构"一节中的示例作如下更改：需要增加两个输入参数：目标城市和搜索深度限制。
当前的路线保存在另一个临时表中，仅当到达目标时才显示。
为避免在网络中循环展开，不应展开出现在当前路线中的城市。
下面的示例（不是来自 pubs 数据库）显示了这些更改：CREATE PROCEDURE route
(@current char(20), @dest char(20), @maxlevel int = 5) AS
SET NOCOUNT ON
DECLARE @level int
CREATE TABLE #stack (city char(20), level int)
CREATE TABLE #list (city char(20), level int)
INSERT #stack VALUES (@current, 1)
SELECT @level = 1WHILE @level > 0
BEGIN
   IF EXISTS (SELECT * FROM #stack WHERE level = @level)
      BEGIN
         SELECT @current = city
         FROM #stack
         WHERE level = @level
         DELETE FROM #stack
         WHERE level = @level
            AND city = @current
         DELETE FROM #list
         WHERE level >= @level
         IF EXISTS (SELECT * FROM #list WHERE city = @current)
            CONTINUE
         INSERT #list VALUES(@current, @level)
         IF(@current = @dest)
         BEGIN
            SELECT city AS itinerary
            FROM #list
            CONTINUE
         END         INSERT #stack
         SELECT destination, @level + 1
         FROM flights
         WHERE departure = @current
            AND @level < @maxlevel
         IF @@rowcount > 0
            SELECT @level = @level + 1
      END
   ELSE
      SELECT @level = @level - 1
END -- WHILE在下面的示例中，当 @level 大于 0 时，该过程执行以下步骤：通过清除当前级或其下级的所有项目 (DELETE FROM #list WHERE level > = @level)，然后添加当前城市 (INSERT #list VALUES(@current, @level))，将当前城市添加到 #list 中。
只要到达目标城市 (@current = @dest)，该过程就会显示路径 (SELECT itinerary = city FROM #list)，而且不再进一步展开该路径 (CONTINUE)。
通过在将城市添加到堆栈的 INSERT 语句中添加一个条件 (@level < @maxlevel)，限制搜索深度。
如果当前城市已经在当前路线中，WHILE 循环中最开始的 IF EXISTS 语句将跳过当前城市。如果 flights 表还包括费用信息，就可以找到最低费用路线，方法是如果当前路线的总费用低于到目前为止的最低费用，就保存当前路线：SELECT @cost = sum(cost)
FROM #list
IF @cost < @lowest_cost
BEGIN
   @lowest_cost = @cost
   TRUNCATE TABLE #best_route
   INSERT #best_route
      SELECT *
      FROM #list
END为了获得更高的效率，如果当前成本超过最佳路线的成本，则可以停止展开当前路线：IF (SELECT SUM(cost) FROM #list) > @lowest_cost
   CONTINUE如果 flights 表包括起飞和到达时间，则可以添加一个 IF 语句，以便只展开起飞时间至少比当前路线的到达时间晚一个小时的路线：IF ((SELECT SUM(cost) FROM #list) > @lowest_cost)
   AND datediff(hh, departuretime, @arrivaltime) > 1)
CONTINUE©1988-2004 Microsoft Corporation. 保留所有权利。

接上Top

回复人： zicxc(冒牌邹建 V0.2) ( ) 信誉：100  2004-05-21 09:36:00  得分:0

  正牌的下站ID加得让人看不懂，下站ID什么意义？
是stop_id在线路线路ID 的下一站？
那
--直达站就一次查询
select * from line_stop
where stop_id=@起点站ID  and next_id=@终点站ID
只是查询正好是相邻站的情况，隔站就查不到了。是stop_id在线路线路ID 能到达的站？
那样每个线路的每两个站的组合都必须列出，数据冗余也太大了用临时表（或者表变量）存放能到达的路径，用一个字段表示转乘的次数，也就是微软帮助里的算法（playyuer(双规干部) 贴的），才能解决不知道转乘几次的情况。

Top

回复人： zicxc(冒牌邹建 V0.2) ( ) 信誉：100  2004-05-21 12:15:00  得分:0

  写了个用函数解决的方法：--建表
create table line (
id       int not null IDENTITY(1,1),
line_name varchar(30)
)
gocreate table stop(
id       int not null IDENTITY(1,1),
stop_name varchar(30)
)
gocreate table line_stop(
id       int not null IDENTITY(1,1),
line_id    int not null ,
stop_id    int not null ,
upordown   smallint not null,  --1-上行，2-下行，3-上下行
serial     int not null
)
go--增加基础数据
insert line(line_name)
select '1'
union all
select '2'
union all
select '3'
union all
select '4'
goinsert Stop(Stop_name)
select 'A'
union all
select 'B'
union all
select 'C'
union all
select 'D'
union all
select 'E'
union all
select 'F'
union all
select 'G'
union all
select 'H'
union all
select 'I'
union all
select 'J'
union all
select 'K'
union all
select 'L'
union all
select 'M'
union all
select 'N'
union all
select 'O'
union all
select 'P'
union all
select 'Q'
union all
select 'R'
go
--增加线路数据
--线路，先不考虑上行下行，比较复杂，线路如下
--1-abcde
--2-fgchij
--3-klminop
--4-aocldeclare @L int
declare @S varchar(10)
declare @i int --1-ABCDE
set @L=1
set @S='ABCDE'
set @i =1
while @i<=len(@S)
begin
insert line_stop(
line_id,
stop_id,
upordown,
serial
)
select
@L,ascii(substring(@s,@i,1))-ascii('A')+1,3,@i
        set @i=@i+1
end--2-FGCHIJ
set @L=2
set @S='FGCHIJ'
set @i =1
while @i<=len(@S)
begin
insert line_stop(
line_id,
stop_id,
upordown,
serial
)
select
@L,ascii(substring(@s,@i,1))-ascii('A')+1,3,@i
        set @i=@i+1
end--3-KLMINOP
set @L=3
set @S='KLMINOP'
set @i =1
while @i<=len(@S)
begin
insert line_stop(
line_id,
stop_id,
upordown,
serial
)
select
@L,ascii(substring(@s,@i,1))-ascii('A')+1,3,@i
        set @i=@i+1
end--4-AOCLQR
set @L=4
set @S='AOCL'
set @i =1
while @i<=len(@S)
begin
insert line_stop(
line_id,
stop_id,
upordown,
serial
)
select
@L,ascii(substring(@s,@i,1))-ascii('A')+1,3,@i
        set @i=@i+1
endgo--建立函数
alter function GetPath(@BName varchar(30),@EName varchar(30))
returns @r table (Path varchar(100),LCnt int,SCnt int)
as
begin
     declare @t table (Path varchar(100),LCnt int,SCnt int,Stop_Id int)
        declare @BId int
        declare @EId int
        select @BId=id from stop where Stop_name=@BName
        if @BId is null return
        select @EId=id from stop where Stop_name=@EName
        if @EId is null return insert @t
        select path=rtrim(d.line_Name)+':'+@BName+'-'+b.Stop_name,LCnt=1,scnt=abs(a.serial-c.serial),a.Stop_Id
        from line_stop a,Stop b,(select Line_id,serial from line_stop where Stop_Id=@BId)as c,line d
        where a.Line_Id=c.Line_Id
and a.Stop_id<>@Bid
        and a.Stop_id=b.id
        and d.id=a.Line_id delete t from @t t where exists (
         select * from @t where Stop_Id=t.Stop_Id and scnt<t.scnt
        ) insert @r select Path,LCnt,SCnt from @t where Stop_id=@Eid if exists (select * from @r) return
while exists (
        select 1
        from line_stop a,Stop b,line d,@t t,line_stop x,Stop xb
        where t.Stop_Id=x.Stop_Id
        and a.Line_Id=x.Line_Id
and a.Stop_id<>t.Stop_Id
        and a.Stop_id=b.id
        and x.Stop_id=xb.id
        and d.id=a.Line_id
        and not exists (
         select * from @t where Stop_Id=a.Stop_Id and scnt<=t.scnt+abs(a.serial-x.serial)
        )
)
begin
insert @t
        select path=t.path+','+rtrim(d.line_Name)+':'+xb.Stop_name+'-'+b.Stop_name,LCnt=t.LCnt+1,scnt=t.scnt+abs(a.serial-x.serial),a.Stop_Id
        from line_stop a,Stop b,line d,@t t,line_stop x,Stop xb
        where t.Stop_Id=x.Stop_Id
        and a.Line_Id=x.Line_Id
and a.Stop_id<>t.Stop_Id
        and a.Stop_id=b.id
        and x.Stop_id=xb.id
        and d.id=a.Line_id
        and not exists (
         select * from @t where Stop_Id=a.Stop_Id and scnt<=t.scnt+abs(a.serial-x.serial)
        )
insert @r select Path,LCnt,SCnt from @t where Stop_id=@Eid
if exists (select * from @r) return
end
return
end--测试
declare @BName varchar(30)
declare @EName varchar(30)
declare @Msg varchar(100)DECLARE cur CURSOR FOR
SELECT a.Stop_Name,b.Stop_Name
FROM stop a,stop b
WHERE a.id<>b.id
ORDER BY a.idOPEN curFETCH NEXT FROM cur
INTO @BName, @ENameWHILE @@FETCH_STATUS = 0
BEGIN
     set @Msg='开始站：'+@BName+'   终止站：'+@EName
print @Msg
exec('select top 1 Path as 路径,LCnt as 线路数,SCnt as 站数 from dbo.GetPath('''+@BName+''','''+@EName+''') order by LCnt,SCnt')
FETCH NEXT FROM cur
INTO @BName, @EName
end
CLOSE cur
DEALLOCATE cur

接上Top

回复人： zicxc(冒牌邹建 V0.2) ( ) 信誉：100  2004-05-21 12:17:00  得分:0

  --结果（一部分）:
/*
开始站：A   终止站：B
路径                                                                                                   线路数         站数
---------------------------------------------------------------------------------------------------- ----------- -----------
1:A-B                                                                                                1           1开始站：A   终止站：K
路径                                                                                                   线路数         站数
---------------------------------------------------------------------------------------------------- ----------- -----------
4:A-L,3:L-K                                                                                          2           4开始站：A   终止站：L
路径                                                                                                   线路数         站数
---------------------------------------------------------------------------------------------------- ----------- -----------
4:A-L                                                                                                1           3开始站：R   终止站：I
路径                                                                                                   线路数         站数
---------------------------------------------------------------------------------------------------- ----------- -----------
4:R-L,3:L-I                                                                                          2           4开始站：R   终止站：J
路径                                                                                                   线路数         站数
---------------------------------------------------------------------------------------------------- ----------- -----------
4:R-C,2:C-J                                                                                          2           6开始站：R   终止站：K
路径                                                                                                   线路数         站数
---------------------------------------------------------------------------------------------------- ----------- -----------
4:R-L,3:L-K                                                                                          2           3开始站：R   终止站：L
路径                                                                                                   线路数         站数
---------------------------------------------------------------------------------------------------- ----------- -----------
4:R-L                                                                                                1           2开始站：R   终止站：M
路径                                                                                                   线路数         站数
---------------------------------------------------------------------------------------------------- ----------- -----------
4:R-L,3:L-M                                                                                          2           3开始站：R   终止站：N
路径                                                                                                   线路数         站数
---------------------------------------------------------------------------------------------------- ----------- -----------
4:R-O,3:O-N                                                                                          2           5开始站：R   终止站：O
路径                                                                                                   线路数         站数
---------------------------------------------------------------------------------------------------- ----------- -----------
4:R-O                                                                                                1           4
*/


Top

回复人： zjcxc(邹建) ( ) 信誉：316  2004-05-21 15:34:00  得分:0

  正牌的下站ID加得让人看不懂，下站ID什么意义？下站ID，就是按行车方向，下一个到达站的ID


Top

回复人： zicxc(冒牌邹建 V0.2) ( ) 信誉：100  2004-05-21 15:53:00  得分:0

  正牌：
这样说下面就有问题了--直达站就一次查询
select * from line_stop
where stop_id=@起点站ID  and next_id=@终点站ID/*
如果一个线路是abcd四站，那a-d是不必转乘的，你上面的查询就得不到，因为a的下一站只是b,下面的有同样的问题
*/
--一次换乘就这样查询:
select * from line_stop a
where stop_id=@起点站ID  and exists(
select 1 from line_stop
where next_id=@终点站ID and stop_id=a.next_id)
--二次换就这样查询
select * from line_stop a
where stop_id=@起点站ID  and exists(
select 1 from line_stop aa
where stop_id=a.next_id and exists(
select 1 from line_stop
where stop_id=a.next_id
and next_id=@终点站ID))

呵呵
没了

调试易

谁有公交换乘的算法？或思路？求教！万分感谢！

解决方案 »

谁有公交换乘的算法？或思路？ 求教！万分感谢！

解决方案 »

谁有公交换乘的算法？或思路？求教！万分感谢！