站长论坛

标题: SQL实现最优坐地铁方案 [打印本页]

作者: superadmin 时间: 2007-11-30 12:42
标题: SQL实现最优坐地铁方案
坐地铁有时候不一定要坐最少站的，有时是希望能坐换乘次数最少的，应该怎么改造才能把所有的方案都取出来，然后按换乘次数、经过站点数依次排序?
　　lineID state orderid

　　1 广州东 1

　　1 体育中心2

　　1 体育西 3

　　1 烈士陵园4

　　1 公园前 6

　　1 西门口 7

　　2 火车站 1

　　2 纪念堂 2

　　2 公园前 3

　　2 中大 4

　　2 客村 5

　　2 琶洲 6

　　2 万胜围 7

　　3 广州东 1

　　3 体育西 2

　　3 珠江新城3

　　3 客村 4

　　3 市桥 5

　　4 万胜围 1

　　4 金洲 2

　　如上面数据，想查询“广州东”至“中大”，大家通过程序计算列出全部的方案。

　Peak Wong：

　　SQL code　　

DECLARE @tb TABLE(
lineID int, state nvarchar(10), orderid int)
INSERT @tb
SELECT 1, N'广州东', 1  UNION ALL
SELECT 1, N'体育中心', 2  UNION ALL
SELECT 1, N'体育西', 3  UNION ALL
SELECT 1, N'烈士陵园', 4  UNION ALL
SELECT 1, N'公园前', 6  UNION ALL
SELECT 1, N'西门口', 7  UNION ALL
SELECT 2, N'火车站', 1  UNION ALL
SELECT 2, N'纪念堂', 2  UNION ALL
SELECT 2, N'公园前', 3  UNION ALL
SELECT 2, N'中大', 4  UNION ALL
SELECT 2, N'客村', 5  UNION ALL
SELECT 2, N'琶洲', 6  UNION ALL
SELECT 2, N'万胜围', 7  UNION ALL
SELECT 3, N'广州东', 1  UNION ALL
SELECT 3, N'体育西', 2  UNION ALL
SELECT 3, N'珠江新城', 3  UNION ALL
SELECT 3, N'客村', 4  UNION ALL
SELECT 3, N'市桥', 5  UNION ALL
SELECT 4, N'万胜围', 1  UNION ALL
SELECT 4, N'金洲', 2
DECLARE
@state_start nvarchar(10),
@state_stop nvarchar(10)
SELECT
@state_start = N'广州东',
@state_stop = N'中大'

-- 查询
DECLARE @re TABLE(
path nvarchar(max),
state_count int,
start_lineID int,
start_state nvarchar(10),
current_lineID int,
current_state nvarchar(10),
current_orderid int,
flag int,
lineIDs nvarchar(max),
level int
)
DECLARE
@level int,
@rows int
SET
@level = 0

-- 开始
INSERT @re
SELECT
path = CONVERT(nvarchar(max),
         RTRIM(A.lineID) + N'{'
            + RTRIM(A.orderid) + N'.' + A.state
      ),
state_count = 0,
start_lineID = A.lineID,
start_state = A.state,
current_lineID = A.lineID,
current_state = A.state,
current_orderid = A.orderid,
flag = CASE
         WHEN A.state = @state_stop THEN 0
         ELSE NULL END,
lineIDs = ',' + RTRIM(A.lineID) + ',',
level = -(@level + 1)
FROM @tb A
WHERE state = @state_start
SET @rows = @@ROWCOUNT
WHILE @rows > 0
BEGIN
SELECT
      @level = @level + 1
INSERT @re
-- 同一 LineID
SELECT
      path = CONVERT(nvarchar(max),
            A.path
                  + N'->'
                  + RTRIM(B.orderid) + N'.' + B.state
         ),
      state_count = A.state_count + 1,
      A.start_lineID, A.start_state,
      current_lineID = B.lineID,
      current_state = B.state,
      current_orderid = B.orderid,
      flag = CASE
            WHEN B.state = @state_stop THEN 0
            ELSE A.flag END,
      A.lineIDs,
      level = @level
FROM @re A, @tb B
WHERE A.flag <> 0
      AND A.level = @level - 1
      AND A.current_lineID = B.lineID
      AND A.current_orderid + A.flag = B.orderid

UNION ALL
-- 不同 LineID
SELECT
      path = CONVERT(nvarchar(max),
            A.path + N')->'
                  + RTRIM(B.lineID) + N'{'
                  + RTRIM(B.orderid) + N'.' + B.state
         ),
      state_count = A.state_count + 1,
      A.start_lineID, A.start_state,
      current_lineID = B.lineID,
      current_state = B.state,
      current_orderid = B.orderid,
      flag = CASE
            WHEN B.state = @state_stop THEN 0
            ELSE NULL END,
      A.lineIDs + RTRIM(B.lineID) + ',',
      level = - @level
FROM @re A, @tb B
WHERE A.flag <> 0
      AND state_count = @level - 1
      AND A.current_lineID <> B.lineID
      AND A.current_state = B.state
      AND NOT EXISTS(
            SELECT * FROM @re
            WHERE CHARINDEX(',' + RTRIM(B.lineID) + ',', A.lineIDs) > 0)
SET @rows = @@ROWCOUNT

INSERT @re
-- 不同 LineID 的第1站正向
SELECT
      path = CONVERT(nvarchar(max),
            A.path
                  + N'->'
                  + RTRIM(B.orderid) + N'.' + B.state
         ),
      state_count = A.state_count + 1,
      A.start_lineID, A.start_state,
      current_lineID = B.lineID,
      current_state = B.state,
      current_orderid = B.orderid,
      flag = CASE
            WHEN B.state = @state_stop THEN 0
            ELSE 1 END,
      A.lineIDs,
      level = @level
FROM @re A, @tb B
WHERE A.flag IS NULL
      AND A.level = - @level
      AND A.current_lineID = B.lineID
      AND A.current_orderid + 1 = B.orderid
UNION ALL
-- 不同 LineID 的第1站反向
SELECT
      path = CONVERT(nvarchar(max),
            A.path
                  + N'->'
                  + RTRIM(B.orderid) + N'.' + B.state
         ),
      state_count = A.state_count + 1,
      A.start_lineID, A.start_state,
      current_lineID = B.lineID,
      current_state = B.state,
      current_orderid = B.orderid,
      flag = CASE
            WHEN B.state = @state_stop THEN 0
            ELSE - 1 END,
      A.lineIDs,
      level = @level
FROM @re A, @tb B
WHERE A.flag IS NULL
      AND A.level = - @level
      AND A.current_lineID = B.lineID
      AND A.current_orderid - 1 = B.orderid

SET @rows = @rows + @@ROWCOUNT
END

SELECT
-- *,
path = path + N'}',
state_count
FROM @re
WHERE flag = 0

　　结果(数字5,7是要经过多少站:

　　3{1.广州东-> 2.体育西-> 3.珠江新城-> 4.客村)-> 2{5.客村-> 4.中大} 5

　　1{1.广州东-> 2.体育中心-> 3.体育西)-> 3{2.体育西-> 3.珠江新城-> 4.客村)-> 2{5.客村-> 4.中大} 7

作者: superadmin 时间: 2007-11-30 12:42
下面这个包含要换乘多少次

　　SQL code

DECLARE @tb TABLE(
lineID int, state nvarchar(10), orderid int)
INSERT @tb
SELECT 1, N'广州东', 1  UNION ALL
SELECT 1, N'体育中心', 2  UNION ALL
SELECT 1, N'体育西', 3  UNION ALL
SELECT 1, N'烈士陵园', 4  UNION ALL
SELECT 1, N'公园前', 6  UNION ALL
SELECT 1, N'西门口', 7  UNION ALL
SELECT 2, N'火车站', 1  UNION ALL
SELECT 2, N'纪念堂', 2  UNION ALL
SELECT 2, N'公园前', 3  UNION ALL
SELECT 2, N'中大', 4  UNION ALL
SELECT 2, N'客村', 5  UNION ALL
SELECT 2, N'琶洲', 6  UNION ALL
SELECT 2, N'万胜围', 7  UNION ALL
SELECT 3, N'广州东', 1  UNION ALL
SELECT 3, N'体育西', 2  UNION ALL
SELECT 3, N'珠江新城', 3  UNION ALL
SELECT 3, N'客村', 4  UNION ALL
SELECT 3, N'市桥', 5  UNION ALL
SELECT 4, N'万胜围', 1  UNION ALL
SELECT 4, N'金洲', 2
DECLARE
@state_start nvarchar(10),
@state_stop nvarchar(10)
SELECT
@state_start = N'广州东',
@state_stop = N'中大'

-- 查询
DECLARE @re TABLE(
path nvarchar(max),
state_count int,
line_count int,
start_lineID int,
start_state nvarchar(10),
current_lineID int,
current_state nvarchar(10),
current_orderid int,
flag int,
lineIDs nvarchar(max),
level int
)
DECLARE
@level int,
@rows int
SET
@level = 0

-- 开始
INSERT @re
SELECT
path = CONVERT(nvarchar(max),
         RTRIM(A.lineID) + N'{'
            + RTRIM(A.orderid) + N'.' + A.state
      ),
state_count = 0,
line_count = 1,
start_lineID = A.lineID,
start_state = A.state,
current_lineID = A.lineID,
current_state = A.state,
current_orderid = A.orderid,
flag = CASE
         WHEN A.state = @state_stop THEN 0
         ELSE NULL END,
lineIDs = ',' + RTRIM(A.lineID) + ',',
level = -(@level + 1)
FROM @tb A
WHERE state = @state_start
SET @rows = @@ROWCOUNT
WHILE @rows > 0
BEGIN
SELECT
      @level = @level + 1
INSERT @re
-- 同一 LineID
SELECT
      path = CONVERT(nvarchar(max),
            A.path
                  + N'->'
                  + RTRIM(B.orderid) + N'.' + B.state
         ),
      state_count = A.state_count + 1,
      A.line_count,
      A.start_lineID, A.start_state,
      current_lineID = B.lineID,
      current_state = B.state,
      current_orderid = B.orderid,
      flag = CASE
            WHEN B.state = @state_stop THEN 0
            ELSE A.flag END,
      A.lineIDs,
      level = @level
FROM @re A, @tb B
WHERE A.flag <> 0
      AND A.level = @level - 1
      AND A.current_lineID = B.lineID
      AND A.current_orderid + A.flag = B.orderid

UNION ALL
-- 不同 LineID
SELECT
      path = CONVERT(nvarchar(max),
            A.path + N')->'
                  + RTRIM(B.lineID) + N'{'
                  + RTRIM(B.orderid) + N'.' + B.state
         ),
      state_count = A.state_count + 1,
      line_count = A.line_count + 1,
      A.start_lineID, A.start_state,
      current_lineID = B.lineID,
      current_state = B.state,
      current_orderid = B.orderid,
      flag = CASE
            WHEN B.state = @state_stop THEN 0
            ELSE NULL END,
      A.lineIDs + RTRIM(B.lineID) + ',',
      level = - @level
FROM @re A, @tb B
WHERE A.flag <> 0
      AND state_count = @level - 1
      AND A.current_lineID <> B.lineID
      AND A.current_state = B.state
      AND NOT EXISTS(
            SELECT * FROM @re
            WHERE CHARINDEX(',' + RTRIM(B.lineID) + ',', A.lineIDs) > 0)
SET @rows = @@ROWCOUNT

INSERT @re
-- 不同 LineID 的第1站正向
SELECT
      path = CONVERT(nvarchar(max),
            A.path
                  + N'->'
                  + RTRIM(B.orderid) + N'.' + B.state
         ),
      state_count = A.state_count + 1,
      A.line_count,
      A.start_lineID, A.start_state,
      current_lineID = B.lineID,
      current_state = B.state,
      current_orderid = B.orderid,
      flag = CASE
            WHEN B.state = @state_stop THEN 0
            ELSE 1 END,
      A.lineIDs,
      level = @level
FROM @re A, @tb B
WHERE A.flag IS NULL
      AND A.level = - @level
      AND A.current_lineID = B.lineID
      AND A.current_orderid + 1 = B.orderid
UNION ALL
-- 不同 LineID 的第1站反向
SELECT
      path = CONVERT(nvarchar(max),
            A.path
                  + N'->'
                  + RTRIM(B.orderid) + N'.' + B.state
         ),
      state_count = A.state_count + 1,
      A.line_count,
      A.start_lineID, A.start_state,
      current_lineID = B.lineID,
      current_state = B.state,
      current_orderid = B.orderid,
      flag = CASE
            WHEN B.state = @state_stop THEN 0
            ELSE - 1 END,
      A.lineIDs,
      level = @level
FROM @re A, @tb B
WHERE A.flag IS NULL
      AND A.level = - @level
      AND A.current_lineID = B.lineID
      AND A.current_orderid - 1 = B.orderid

SET @rows = @rows + @@ROWCOUNT
END

SELECT
-- *,
path = path + N'}',
line_count,
state_count
FROM @re
WHERE flag = 0

　　结果, 2/3 是换乘次数(应该减一, 将上面代码中初始化 line_count 的地方从1改成0即可):

　　3{1.广州东-> 2.体育西-> 3.珠江新城-> 4.客村)-> 2{5.客村-> 4.中大} 2 5

　　1{1.广州东-> 2.体育中心-> 3.体育西)-> 3{2.体育西-> 3.珠江新城-> 4.客村)-> 2{5.客村-> 4.中大} 3 7

　　数据的问题, 我的算法依赖于 orderid 来搜索下一站, 如果这个不连续, 则无法搜索下一站

　　所以把数据改成下面的就行了

　　SQL code　

DECLARE @tb TABLE(
lineID int, state nvarchar(10), orderid int)
INSERT @tb
SELECT 1, N'广州东', 1  UNION ALL
SELECT 1, N'体育中心', 2  UNION ALL
SELECT 1, N'体育西', 3  UNION ALL
SELECT 1, N'烈士陵园', 4  UNION ALL
--SELECT 1, N'公园前', 6  UNION ALL  -- 这里站点断开了, 我的搜索要求连续
--SELECT 1, N'西门口', 7  UNION ALL
SELECT 1, N'公园前', 5  UNION ALL  -- 这里站点断开了, 我的搜索要求连续
SELECT 1, N'西门口', 6  UNION ALL
SELECT 2, N'火车站', 1  UNION ALL
SELECT 2, N'纪念堂', 2  UNION ALL
SELECT 2, N'公园前', 3  UNION ALL
SELECT 2, N'中大', 4  UNION ALL
SELECT 2, N'客村', 5  UNION ALL
SELECT 2, N'琶洲', 6  UNION ALL
SELECT 2, N'万胜围', 7  UNION ALL
SELECT 3, N'广州东', 1  UNION ALL
SELECT 3, N'体育西', 2  UNION ALL
SELECT 3, N'珠江新城', 3  UNION ALL
SELECT 3, N'客村', 4  UNION ALL
SELECT 3, N'市桥', 5  UNION ALL
SELECT 4, N'万胜围', 1  UNION ALL
SELECT 4, N'金洲', 2

　　修改后的执行结果(换乘数已经改成初始化为0)

　　3{1.广州东-> 2.体育西-> 3.珠江新城-> 4.客村)-> 2{5.客村-> 4.中大} 1 5

　　3{1.广州东-> 2.体育西)-> 1{3.体育西-> 4.烈士陵园-> 5.公园前)-> 2{3.公园前-> 4.中大} 2 6

　　1{1.广州东-> 2.体育中心-> 3.体育西-> 4.烈士陵园-> 5.公园前)-> 2{3.公园前-> 4.中大} 1 6

　　1{1.广州东-> 2.体育中心-> 3.体育西)-> 3{2.体育西-> 3.珠江新城-> 4.客村)-> 2{5.客村-> 4.中大} 2 7

　　如果 orderid 在实际数据中确实有不连续的问题, 则可以在处理之前先把数据导到临时表, 生成连续的 orderid, 再用我的算法来查询结果。这次的算法相比之前的算法有改进, 只有换乘才会判断是否已经走过此线路, 其他方面也略有调整, 应该比以前的好。你可以测试一下!

　　实际使用时, 算法上可以稍做调到:

　　1. 直接计算出 next_orderid, 而不是每次用 flag 去算, 这样可以提高 join 效率

　　2. 表变量改成临时表, 这样可以在相关的列上建立索引, 从而更快的与原表 join (当然, 原表相关的列上也要有索引)

欢迎光临站长论坛 (http://tzlink.com/bbs/)