SQL 地鐵換乘方案優化：修正 OrderID 斷點與換乘計數邏輯

問題回顧

上一版演算法在實測中發現兩個關鍵問題：

1. 換乘次數計算偏差：初始化 line_count = 1 導致輸出值比實際換乘次數多 1。
2. OrderID 不連續導致搜尋中斷：1 號線原始資料中「烈士陵園」(4) 直接跳至「公園前」(6)，缺少 5，造成同線前進邏輯失效。

修正方案

1. 換乘計數歸零

將初始化插入語句中的 line_count = 1 改為 line_count = 0，最終輸出的 line_count 即為真實換乘次數。

2. 資料預處理：重新編號 OrderID

對 1 號線斷點進行修補：

-- 原始資料
SELECT 1, N'烈士陵園', 4 UNION ALL
-- SELECT 1, N'公園前', 6  -- 刪除斷點
-- SELECT 1, N'西門口', 7  -- 刪除斷點
SELECT 1, N'公園前', 5 UNION ALL  -- 重新編號
SELECT 1, N'西門口', 6 UNION ALL

原則：同一 lineID 下 orderid 必須連續遞增 1，否則同線前進邏輯 A.current_orderid + A.flag = B.orderid 將無法匹配下一站。

修正後執行結果

查詢「廣州東」→「中大」得到四條有效路徑：

最優方案為第一條：換乘 1 次、途經 5 站（3 號線直達客村再換 2 號線）。

工程化建議

1. 資料清洗自動化：建立 ETL 流程，以 ROW_NUMBER() OVER (PARTITION BY lineID ORDER BY 原始序) 重新生成連續 orderid，寫入正式查詢表。
2. 索引策略：將表變數改為暫存表 #tb、#re，於 (lineID, orderid)、(state, lineID) 建立複合索引。
3. 方向預計算：在 #tb 增加 next_orderid_forward、next_orderid_backward 欄位，避免迴圈中動態運算 current_orderid + flag。
4. 早期剪枝：在換乘步驟加入 state_count <= (SELECT MIN(state_count) FROM #re WHERE flag=0) 條件，捨棄已超過當前最佳站數的路徑。

結語

修正 OrderID 連續性與換乘計數初始值後，演算法能穩定產出正確的最優換乘方案。實務部署時，建議將資料預處理、索引建立、迴圈邏輯封裝為預存程序，並配合應用層快取，滿足高併發查詢需求。