公交換乘簡(jiǎn)單算法

1、公交換乘簡(jiǎn)單算法: 三個(gè)表(最簡(jiǎn)單化，不考慮模糊查詢，單行線等其他東西)：站點(diǎn)表 stop(stop_id,stop_name)2，路線表 line(line_id,line_name)3,路線站點(diǎn)表(點(diǎn)線路關(guān)系表)linestops( line_id, stop_id, seq )此處的seq指某站點(diǎn)在某線路中 的順序?，F(xiàn)在分析算法：1，直達(dá)線路首先根據(jù)兩個(gè)站點(diǎn)名獲取兩個(gè)站點(diǎn)各自的id，這里定義為id1,id2然后查詢select line_id from(select line_id from linestops where stop_id = id1) A,(select line_id

2、 from linestops where stop_id = id2) Bwhere A.line_id = B.line_id即得到可直達(dá)的線路列表一次換乘首先根據(jù)兩個(gè)站點(diǎn)名獲取兩個(gè)站點(diǎn)各自的id，這里定義為id1,id2然后搜尋兩個(gè)站點(diǎn)通過直達(dá)方式各自能夠到達(dá)的站點(diǎn)集合，最后他們的交集就是我們所需要 的換乘站點(diǎn)。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 dist

3、inct stop_id from linestops where line_id in(select line_id from linestops where stop_id = id1)Bwhere A.stop_id= B.stop_id得到換乘站(可能有多個(gè)或0個(gè))后，剩下的就是顯示能夠到達(dá)換乘站的兩邊線路，這通過 前面的直達(dá)查詢即可。3，二次換乘首先根據(jù)兩個(gè)站點(diǎn)名獲取兩個(gè)站點(diǎn)各自的id，這里定義為id1,id2算法的中心思想是：站點(diǎn)1能夠通過直達(dá)到達(dá)的所有站點(diǎn)集合A，站點(diǎn)2能夠通過直達(dá)到達(dá) 的所有站點(diǎn)集合B，A和B之間有直達(dá)的線路。步 步來：站點(diǎn)1能夠通過直達(dá)到達(dá)的所有站點(diǎn)集合A：s

4、elect distinct stop_id from linestops where line_id in(select line_id from linestops where stop_id = id1)站點(diǎn)2能夠通過直達(dá)到達(dá)的所有站點(diǎn)集合B：select distinct stop_id from linestops where line_id in(select line_id from linestops where stop_id = id2)而直達(dá)的查詢是select line_id from(select line_id from linestops where stop_i

5、d = idl) C,(select line_id from linestops where stop_id = id2) Dwhere 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】)Dwhere C

6、.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條)，對(duì)列舉的的每一條假設(shè)命 名為X線，下一步就是找出可

7、以從站點(diǎn)1到達(dá)X任意一個(gè)站點(diǎn)的直達(dá)線路、和可以從站點(diǎn)2 到達(dá)X任意一個(gè)站點(diǎn)的直達(dá)線路即可。那么與前面的算法相似，我們?cè)谡军c(diǎn)1所有能夠到達(dá)的站點(diǎn)中去尋找和線路X相交的站點(diǎn)， 然后再去找這兩個(gè)點(diǎn)的線路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 ) Bwhere A.stop_id = B.st

8、op_id找到站點(diǎn)了，下面就是根據(jù)已經(jīng)解決的直達(dá)查詢找線路了。站點(diǎn)2類似。以上的算法有一個(gè)優(yōu)點(diǎn)，全部是sql完成搜尋，所以asp代碼只需寥寥幾行循環(huán)而已。但是缺點(diǎn)是：慢,畢竟可能涉及了數(shù)百次sql查詢。而且只是用最簡(jiǎn)單的sql方法去算出所有 可以換乘的方案，不涉及最優(yōu)/最短的算法。如果是最短路徑，那得用特殊結(jié)構(gòu)和算法。另外：根據(jù)出行者輸入的起點(diǎn)和終點(diǎn)，確定出行要選擇的起始公交站點(diǎn)A和目的公交站點(diǎn)B。搜索 數(shù)據(jù)庫，查詢站點(diǎn)A和站點(diǎn)B之間是否有相同的車經(jīng)過，如果有一條或幾條直達(dá)線路，通 過比較選擇距離最短的公交線路推薦給出行者。如果沒有，則計(jì)算站點(diǎn)A和站點(diǎn)B之間有 沒有一個(gè)公共站點(diǎn)C，從站點(diǎn)C可以

9、換乘到達(dá)站點(diǎn)B。這就有兩種情況：(1)如果有，屬于一 次換乘。計(jì)算站點(diǎn)A和公共站點(diǎn)C之間有沒有相同的公交車經(jīng)過并存入集合X；同樣，計(jì)算 站點(diǎn)B和公共站點(diǎn)C之間有沒有相同的公交車經(jīng)過并存入集合Y。將這兩個(gè)集合比較后就可 以得到從站點(diǎn)A經(jīng)過公共站點(diǎn)C到達(dá)站點(diǎn)B的公交線路，在這些線路中進(jìn)行比較，選擇距 離最短的推薦給出行者。(2)如果沒有公共站點(diǎn)C，就出現(xiàn)了要換乘兩次的情況。將經(jīng)過站 點(diǎn)A的每條公交線路的所有站點(diǎn)存入集合O；同樣，經(jīng)過站點(diǎn)B的每條線路的所有站點(diǎn)存入 集合P。比較這兩個(gè)集合，先乘經(jīng)過站點(diǎn)A的某一路車到達(dá)某一站點(diǎn)D,計(jì)算站點(diǎn)D與站點(diǎn) B之間有沒有公共站點(diǎn)E,如果有則站點(diǎn)D、E為換乘站點(diǎn)。

10、這種方案可能有多種，比較選擇 距離最短的推薦給出行者。如果不存在公共站點(diǎn)E，說明經(jīng)過兩次換乘無法從站點(diǎn)A到達(dá)站 點(diǎn)B，停止搜索計(jì)算。公交出行最優(yōu)路線具體算法：輸入起始站點(diǎn)A和目的站點(diǎn)B； 搜索系統(tǒng)數(shù)據(jù)庫，經(jīng)過起始站點(diǎn)A的公交線路存為X(i)(i=1,2,3,m,m為正整數(shù))，經(jīng)過 目的站點(diǎn)B的公交線路存為Y(j)(j=1,2,3,n,.n為正整數(shù))； 判斷是否有X(i)=Y(j)，將滿足條件的存入2。若Z=1，則該條公交線路X(i)即Y(j)為從站 點(diǎn)A到站點(diǎn)B的直達(dá)最優(yōu)線路，輸出結(jié)果并結(jié)束運(yùn)算。Z31，計(jì)算Z中各條線路的距離， 選擇一條距離最短的線路，輸出結(jié)果并結(jié)束運(yùn)算；搜索系統(tǒng)數(shù)據(jù)庫，公交

11、線路X(i)所包含的站點(diǎn)存為O(i,u)(u=1,2,3島g為正整數(shù))公交線 路Y(j)所包含的站點(diǎn)存為P(j,v)(v=1,2,3,h,h為正整數(shù))；判斷是否有O(i,u)= P(j,v)，將滿足條件的存入W。若W=1，則站點(diǎn)O(i,u)即P(j,v)為從站 點(diǎn)A到站點(diǎn)B的一次換乘站點(diǎn)，公交線路X(i)，Y(j)為換乘一次的最優(yōu)路線，輸出結(jié)果并結(jié) 束運(yùn)算。若W31，分別計(jì)算每條換乘路線的距離，選擇一條距離最短的線路，輸出結(jié)果并 結(jié)束運(yùn)算；搜索系統(tǒng)數(shù)據(jù)庫，經(jīng)過站點(diǎn)O(i,u)的公交線路存為R(k)(k=1,2,3,p,p為正整數(shù))，公交線 路R(k)所包含的站點(diǎn)存為G(k,t)(t=1,2,3

12、,q,q為正整數(shù))；判斷是否有G(k,t)=P(j,v)，將滿足條件的存入、。若S = 1，則站點(diǎn)G(k,t)即P(j,v)為從站點(diǎn) A到站點(diǎn)B的二次換乘站點(diǎn)，公交線路X，R(k)，Y(j)為換乘二次的最優(yōu)路線，輸出結(jié)果并 結(jié)束運(yùn)算。若S31，分別計(jì)算每條換乘二次的路線距離，選擇一條距離最短的線路，輸出 結(jié)果并結(jié)束運(yùn)算；以上步驟沒有找到合適的公交線路，輸出“沒有找到換乘次數(shù)不超過兩次的最優(yōu)公交線 路”，結(jié)束運(yùn)算。本文討論的公交出行最優(yōu)路線算法，主要是以距離為標(biāo)準(zhǔn)。在得出了換乘方案之后，可以進(jìn) 一步考慮時(shí)間因素，從而找到更具優(yōu)勝性的換乘方案，這有待進(jìn)行進(jìn)一步的探討、研究。一、公交換乘問題的算法分

13、為兩個(gè)步驟：1、構(gòu)造并求解換乘矩陣，獲得公交換乘方案(即從起點(diǎn)到終點(diǎn)最少換乘次數(shù)，及換乘站點(diǎn))。 有三種實(shí)現(xiàn)形式：、求得所有節(jié)點(diǎn)T矩陣，兩個(gè)節(jié)點(diǎn)直達(dá)設(shè)為1，兩個(gè)節(jié)點(diǎn)不通或需要換乘設(shè)為0；參見公 共交通系統(tǒng)最佳路徑算法求得所有線路的T矩陣，兩條線路相交設(shè)為1，兩個(gè)線路不相交設(shè)為0；參見基于鄰接 矩陣的公交換乘算法的研究(注該算法屬于理想化算法)通過上述第2個(gè)步驟縮小范圍，然后用第一個(gè)步驟求得精確結(jié)果2、根據(jù)最少換乘次數(shù)，縮小求解范圍，求解起始站點(diǎn)與目標(biāo)站點(diǎn)間的最短路徑，進(jìn)而得到 最佳路徑。最短路徑獲得有以下幾種形式：、最簡(jiǎn)單的實(shí)現(xiàn)方法：如果上面1的最少換乘次數(shù)、換乘站點(diǎn)都能求解出來，只需要查詢

14、換乘次數(shù)最少的情況下，所有可能的路徑中站點(diǎn)數(shù)最少的線路即為所求(前提，假設(shè)所有站 點(diǎn)之間的距離大致相等)；、如果上面1只求出來最少換乘次數(shù)，這時(shí)需要用算法求最短路徑，常用的方法是改進(jìn) Dijkstra算法，也就是在Diskstra算法中增加了一條判斷最少換乘算法的一項(xiàng)；、在游戲設(shè)計(jì)程序中，經(jīng)常要涉及到最短路徑的上述，最常采用的算法是A*算法，參見 游戲地圖最短路徑搜索設(shè)計(jì)與實(shí)現(xiàn)和A算法、K（=3）條漸次短路徑搜索算法，這種算法國外用的比較多，由于該算法比較麻煩，國內(nèi) 研究不太多，參見K（W3）條漸次短路徑搜索算法的研究、一種新的Kth最短路徑搜索算 法和城市軌道交通換乘票務(wù)清分模型的研究（碩士

15、論文）、螞蟻算法，參見一種仿Dijkstra的螞蟻算法其中，步驟中都需要依靠最少換乘次數(shù)來達(dá)到降低復(fù)雜度的目的。二、上述算法如能得到很好的實(shí)現(xiàn)，需要建立一個(gè)好的數(shù)據(jù)結(jié)構(gòu)1、數(shù)據(jù)存儲(chǔ)形式我曾問過兩個(gè)實(shí)際搞過這方面的人，一個(gè)人采用數(shù)組來存儲(chǔ)，另外一個(gè)所采用鏈表與數(shù)組相 結(jié)合的方式（即長(zhǎng)鏈表采用數(shù)組，其它采用鏈表的方式），其實(shí)，之所以有上述兩個(gè)存儲(chǔ)形式， 主要是因?yàn)檫@兩個(gè)人算法中側(cè)重面不同，前一個(gè)側(cè)重實(shí)現(xiàn)最少換乘次數(shù)，后一個(gè)則側(cè)重最短 路徑的實(shí)現(xiàn)。2、數(shù)據(jù)結(jié)構(gòu)存儲(chǔ)，可參考城市公交網(wǎng)絡(luò)出行路徑選擇的計(jì)算機(jī)算法研究、基于GIS的 標(biāo)準(zhǔn)公交基礎(chǔ)信息系統(tǒng)基于GIS的公交乘客出行路徑選擇模型，考慮到公交換乘，

16、所以 通常情況下，把相近的站點(diǎn)（站點(diǎn)名一樣但地理位置不同的、站點(diǎn)名不一樣但地理位置很接 近的）作為公交網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)中一個(gè)節(jié)點(diǎn)。3、兩個(gè)節(jié)點(diǎn)之間弧段權(quán)值的選?。ㄓ?jì)算最短路徑需要）：通常情況下，用兩個(gè)節(jié)點(diǎn)之間的距 離代替，但也有人用公交車在這兩個(gè)節(jié)點(diǎn)之間的速度或行車時(shí)間來作為權(quán)值。下圖是沈陽公 交網(wǎng)給出來的環(huán)路車參數(shù)，根據(jù)該參數(shù)和兩個(gè)站點(diǎn)之間的距離可以求出站點(diǎn)之間的行車時(shí)間 （正常）。當(dāng)然因素考慮的越齊全，越人性化，但是程序上就增加了很多難度，比如：考慮“等車時(shí)間、站點(diǎn)距離、線路的熱度（通往商業(yè)區(qū)）、時(shí)間（上班高峰期等）”等因素，這些因 素都很難量化，所以，通常情況下，最簡(jiǎn)單的方法用距離來作為兩個(gè)節(jié)點(diǎn)之間弧段的權(quán)值。1. select a.線路 from（select線路，站點(diǎn)所屬from LineSite where站點(diǎn)名稱=火車站）A, （select線路，站點(diǎn)所屬from LineSite where站點(diǎn)名稱=省博物館）B wh