公交乘換分析的算法設(shè)計與實現(xiàn)

1、公交乘換分析的算法設(shè)計與實現(xiàn)論文導(dǎo)讀：采用了了基于n次公交換乘的算法?；趽Q乘次數(shù)最少的最優(yōu)路徑算法n次公交換乘算法是比較符合人們出門時選擇公交線路時的實際要求的。最優(yōu)路徑，公交乘換分析的算法設(shè)計與實現(xiàn)。關(guān)鍵詞：n次公交換乘，最優(yōu)路徑1 引言目前，公交換乘算法大多是以“空間距離”最短作為第一考慮要素，如Dijkstra算法，遺傳算法，A*算法和燃燒算法等算法，這些算法不適合公交網(wǎng)絡(luò)的特點和人們在選擇公交乘車方案時往往把公交換乘次數(shù)最為第一考慮要素的實際情況，本論文在分析和總結(jié)公交站點、公交線路等公交數(shù)據(jù)的特點基礎(chǔ)之上，采用了了基于n次公交換乘的算法，使系統(tǒng)更方便，更好的滿足了生活中人們的實際需

2、求和提高了查詢的效率。2 公交乘換數(shù)據(jù)分析與抽象2.1 公交數(shù)據(jù)的分析數(shù)據(jù)是GIS的核心部分，數(shù)據(jù)的組合結(jié)構(gòu)的設(shè)計決定了系統(tǒng)功能實現(xiàn)的程度。公交數(shù)據(jù)的種類.公交數(shù)據(jù)簡單的可以分為兩類：公交數(shù)據(jù)主要有公交站點、公交線路、以及公交路段等數(shù)據(jù)組成。論文參考，最優(yōu)路徑。公交站點、線路分析.這里為了討論方便，對公交站點、線路都做簡單的處理。默認(rèn)公交站點唯一，并不存在站點同名等。默認(rèn)公交線路為完全的單向線路，不存在雙線，單雙線結(jié)合，單環(huán)行線和雙環(huán)行線等。2.2 公交數(shù)據(jù)的抽象同一公交線路兩個方向上的同名站點的抽象在同一公交線路上的同一個站點，還有其他的一些較復(fù)雜的情況都抽象成簡單的情況。3 公交乘換算法設(shè)

3、計對于公交換乘的算法，很多學(xué)者都進行了一些研究，得出了最優(yōu)的路線查詢，但對于最優(yōu)路線有著不同的理解：基于最短路徑的（如:Dijkstra算法、遺傳算法、A*算法和燃燒算法等），還有部分算法是基于換乘時間最少，所用費用最少，換乘次數(shù)等。論文參考，最優(yōu)路徑。論文參考，最優(yōu)路徑。但對公交乘客的心理調(diào)查表明:在公交換乘方案的選取上，首先要考慮的因素是到達(dá)目的地的換乘次數(shù)要最少，其次才是要求路徑最短。因此，基于最短路徑的的公交換乘算法并不能滿足實際的需要。在目前的公交換乘算法中，基于換乘次數(shù)最少的最優(yōu)路徑算法n次公交換乘算法是比較符合人們出門時選擇公交線路時的實際要求的。根據(jù)人們的出行習(xí)慣以換乘次數(shù)最少

4、為約束條件進行設(shè)計基于換乘次數(shù)最少的最優(yōu)路徑算法n次公交換乘算法描述。整個最少換乘算法的思想是一個遞歸的過程，從搜索經(jīng)過起點站或目的站點的線路開始,由線路查找該線路經(jīng)過的所有站點,再從這些站點查找經(jīng)過它們的所有線路,不斷迭代,直至找到終點站為止。算法的描述如下:步驟1 輸入乘車的起始站點和目的站點；步驟2 對起始站點A進行站點所在公交線路搜索，得到線路集合LA, 同時對目的站點所在公交線路進行搜索，得到線路集合LB；步驟3 判斷交集Result=LALB：如果Result! =null，則Result即為從A站點到B站點的直達(dá)線路，輸出結(jié)果并結(jié)束運算；步驟4 如果Result=null，將LA

5、中各線路中A站點以后所有站點不重復(fù)地加入集合UA，將集合內(nèi)每個站點作為起始站點，B作為目的站點，重新按照步驟2、3進行搜索；步驟5 如果Result!=null，則得到一次換乘的方案，輸出結(jié)果并結(jié)束運算；步驟6 如果Result=null，則重復(fù)步驟4，依次進行。設(shè)定換乘次數(shù)的上界N，然后以不大于N次換乘的方案得到可行路徑。當(dāng)換乘次數(shù)超過N時，Result仍然為null，則表示從站點A沒有可到達(dá)目的站點B的公交方案，算法結(jié)束。論文參考，最優(yōu)路徑。本算法的主要思想可由圖1表達(dá)：圖1 公交換乘算法流程圖4 公交乘換算法的實現(xiàn)本公交換乘算法的實現(xiàn)過程為：輸入所要查詢的起始站點A和結(jié)束站點B，首先，查

6、詢站點A和站點B之間是是否有直達(dá)線路，如有則返回直達(dá)線路并退出查詢；如過A、B之間沒有直達(dá)線路，返回站點A能夠直達(dá)的站點集合S，接著判斷集合S中是否有站點C能夠直達(dá)B，如存在站點C能夠直達(dá)B則返回站點C并退出查詢，如果不存在站點能夠直達(dá)B，接著查詢集合S中的站點C能夠直達(dá)的站點集合S1，依次遞歸，直到存在換乘方案使站點A能夠到達(dá)站點B或達(dá)到最大換乘次數(shù)是退出查詢。論文參考，最優(yōu)路徑。5 結(jié)語本算法從分析，設(shè)計到實現(xiàn)的過程中，是以到達(dá)目的地的換乘次數(shù)要最少為第一原則，路徑最短為第二原則，利用n次公交換乘，進行算法的描述和設(shè)計，全面闡述了公交乘換算法的原理、特點，以及公交乘換的研究現(xiàn)狀，同時結(jié)合人們的出行習(xí)慣，總結(jié)了公交乘換算法的研究方式，實現(xiàn)了n次公交乘換算法。論文參考，最優(yōu)路徑。本文研究了簡化情況下的公交乘換算法，在現(xiàn)實復(fù)雜其情況下的公交乘換算法則更加復(fù)雜，例如考慮單雙線問題等，尚有很多問題值得我們?nèi)ヌ剿骱脱芯俊⒖嘉墨I(xiàn)1尹志華,羅小龍,劉