程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 數據庫知識 >> SqlServer數據庫 >> 關於SqlServer >> SQL 實現最優坐地鐵方案(1)

SQL 實現最優坐地鐵方案(1)

編輯:關於SqlServer


    坐地鐵有時候不一定要坐最少站的,有時是希望能坐換乘次數最少的,應該怎麼改造才能把所有的方案都取出來,然後按換乘次數、經過站點數依次排序?

  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

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved