公交換乘算法

公交換乘簡單算法:

三個表（最簡單化，不考慮模糊查詢，單行線等其他東西）：
1，站點表stop(stop_id,stop_name)
2，路線表line(line_id,line_name)
3，路線站點表(點線路關系表)linestops( line_id, stop_id, seq )此處的seq指某站點在某線路中的順序。

現在分析算法：
1，直達線路
首先根據兩個站點名獲取兩個站點各自的id，這里定義為id1,id2
然后查詢
select line_id from
(select line_id from linestops where stop_id = id1) A,
(select line_id from linestops where stop_id = id2) B
where A.line_id = B.line_id
即得到可直達的線路列表

2,一次換乘
首先根據兩個站點名獲取兩個站點各自的id，這里定義為id1,id2
然后搜尋兩個站點通過直達方式各自能夠到達的站點集合，最后他們的交集就是我們所需要的換乘站點。
select stop_id from
(
select distinct stop_id from linestops where line_id in
(select line_id from linestops where stop_id = id1)
)A,
(
select distinct stop_id from linestops where line_id in
(select line_id from linestops where stop_id = id1)
)B
where A.stop_id= B.stop_id
得到換乘站（可能有多個或0個）后，剩下的就是顯示能夠到達換乘站的兩邊線路，這通過前面的直達查詢即可。

3，二次換乘
首先根據兩個站點名獲取兩個站點各自的id，這里定義為id1,id2
算法的中心思想是：站點1能夠通過直達到達的所有站點集合A，站點2能夠通過直達到達的所有站點集合B，A和B之間有直達的線路。
一步一步來：
站點1能夠通過直達到達的所有站點集合A：
select distinct stop_id from linestops where line_id in
(select line_id from linestops where stop_id = id1)
站點2能夠通過直達到達的所有站點集合B：
select distinct stop_id from linestops where line_id in
(select line_id from linestops where stop_id = id2)
而直達的查詢是
select line_id from
(select line_id from linestops where stop_id = id1) C,
(select line_id from linestops where stop_id = id2) D
where C.line_id = D.line_id

我們把=id1和=id2換成 in (select ....)A 和 in (select ...)B

這樣最后我們的查詢是
select line_id from
(select distinct line_id from linestops where stop_id in 【A】) C,
(select distinct line_id from linestops where stop_id in 【B】) D
where C.line_id = D.line_id
其中【A】是
（select distinct stop_id from linestops where line_id in
(select line_id from linestops where stop_id = id1))
其中【B】是
（select distinct stop_id from linestops where line_id in
(select line_id from linestops where stop_id = id2))
這樣子我們找到了作為中間換乘的線路（可能有多條或者0條），對列舉的的每一條假設命名為X線，下一步就是找出可以從站點1到達X任意一個站點的直達線路、和可以從站點2到達X任意一個站點的直達線路即可。
那么與前面的算法相似，我們在站點1所有能夠到達的站點中去尋找和線路X相交的站點，然后再去找這兩個點的線路
select stop_id from
(select distinct stop_id from linestops where line_id in
(select line_id from linestops where stop_id = id1))A,
(select stop_id from linestops where line_id = X ) B
where A.stop_id = B.stop_id
找到站點了，下面就是根據已經解決的直達查詢找線路了。
站點2類似。


以上的算法有一個優點，全部是sql完成搜尋，所以asp代碼只需寥寥幾行循環而已。
但是缺點是：慢,畢竟可能涉及了數百次sql查詢。而且只是用最簡單的sql方法去算出所有可以換乘的方案，不涉及最優/最短的算法。如果是最短路徑，那得用特殊結構和算法。

另外:

根據出行者輸入的起點和終點，確定出行要選擇的起始公交站點A和目的公交站點B。搜索數據庫，查詢站點A和站點B之間是否有相同的車經過，如果有一條或幾條直達線路，通過比較選擇距離最短的公交線路推薦給出行者。如果沒有，則計算站點A和站點B之間有沒有一個公共站點C，從站點C可以換乘到達站點 B。這就有兩種情況：(1)如果有，屬于一次換乘。計算站點A和公共站點C之間有沒有相同的公交車經過并存入集合X；同樣，計算站點B和公共站點C之間有沒有相同的公交車經過并存入集合Y。將這兩個集合比較后就可以得到從站點A經過公共站點C到達站點B的公交線路，在這些線路中進行比較，選擇距離最短的推薦給出行者。（2）如果沒有公共站點C，就出現了要換乘兩次的情況。將經過站點A的每條公交線路的所有站點存入集合O；同樣，經過站點B的每條線路的所有站點存入集合P。比較這兩個集合，先乘經過站點A的某一路車到達某一站點D，計算站點D與站點B之間有沒有公共站點E,如果有則站點D、E為換乘站點。這種方案可能有多種，比較選擇距離最短的推薦給出行者。如果不存在公共站點E，說明經過兩次換乘無法從站點A到達站點B，停止搜索計算。

公交出行最優路線具體算法：

1） 輸入起始站點A和目的站點B；

2）搜索系統數據庫，經過起始站點A的公交線路存為X(i)(i=1,2,3…,m,m為正整數)，經過目的站點B的公交線路存為Y(j)(j=1,2,3,…n,.n為正整數)；

3）判斷是否有X(i)=Y(j)，將滿足條件的存入Z。若Z＝1，則該條公交線路X(i)即Y(j)為從站點A到站點B的直達最優線路，輸出結果并結束運算。Z≥1，計算Z中各條線路的距離，選擇一條距離最短的線路，輸出結果并結束運算；

4）搜索系統數據庫，公交線路X(i)所包含的站點存為O(i,u)(u=1,2,3…,g,g為正整數)公交線路Y(j)所包含的站點存為P(j,v)(v=1,2,3…,h,h為正整數)；

5） 判斷是否有O(i,u)= P(j,v)，將滿足條件的存入W。若W＝1，則站點O(i,u)即P(j,v)為從站點A到站點B的一次換乘站點，公交線路X(i)，Y(j)為換乘一次的最優路線，輸出結果并結束運算。若W≥1，分別計算每條換乘路線的距離，選擇一條距離最短的線路，輸出結果并結束運算；

6）搜索系統數據庫，經過站點O(i,u)的公交線路存為R(k)(k=1,2,3…,p,p為正整數)，公交線路R(k)所包含的站點存為G(k,t)(t=1,2,3…,q,q為正整數)；

7）判斷是否有G(k,t)=P(j,v)，將滿足條件的存入S。若S＝1，則站點G(k,t)即P(j,v)為從站點A到站點B的二次換乘站點，公交線路X (i)，R(k)，Y(j)為換乘二次的最優路線，輸出結果并結束運算。若S≥1，分別計算每條換乘二次的路線距離，選擇一條距離最短的線路，輸出結果并結束運算；

8） 以上步驟沒有找到合適的公交線路,輸出“沒有找到換乘次數不超過兩次的最優公交線路”，結束運算。

本文討論的公交出行最優路線算法，主要是以距離為標準。在得出了換乘方案之后，可以進一步考慮時間因素，從而找到更具優勝性的換乘方案，這有待進行進一步的探討、研究。