一種改進(jìn)的公交換乘算法的實(shí)現(xiàn)

1、本欄目責(zé)任編輯:李桂瑾人工智能及識(shí)別技術(shù)1引言目前,實(shí)現(xiàn)公交換乘現(xiàn)有的算法和方法:迪杰斯特拉算法、螞蟻算法、依靠GIS 組件等。其中迪杰斯拉算法在公交站點(diǎn)很多的情況下,數(shù)據(jù)量大,運(yùn)算速度慢;螞蟻算法難于理解;GIS 組件成本高。相對(duì)上述已有方法,用鄰接矩陣方法實(shí)現(xiàn)公交換乘能夠彌補(bǔ)上述不足。南昌市公交線路存在內(nèi)外線、來(lái)返路線一致、來(lái)返路線不一致等情況。某系統(tǒng)模塊要實(shí)現(xiàn)以不依靠第三方組件、乘車路線較優(yōu)為約束條件的公交換乘。通過(guò)對(duì)鄰接矩陣實(shí)現(xiàn)公交換乘方法進(jìn)行了改進(jìn),增加實(shí)現(xiàn)來(lái)返路線不一致、內(nèi)外線、最少站點(diǎn)等功能。本文首先介紹了改進(jìn)的鄰接矩陣實(shí)現(xiàn)公交換乘的基本理論,然后闡述了怎樣用改進(jìn)的鄰接矩陣實(shí)現(xiàn)公

2、交換乘。2鄰接矩陣實(shí)現(xiàn)公交換乘理論2.1鄰接矩陣實(shí)現(xiàn)公交換乘基本思想把每條公交線作為圖中一個(gè)頂點(diǎn),任意兩條公交線路之間的聯(lián)系取決兩者之間有無(wú)交點(diǎn)(共同的?？空军c(diǎn),相應(yīng)地該兩條線路之間的矩陣元素值為1或者0。這樣就把城市公交線路系統(tǒng)可以抽象為n*n 鄰接矩陣,可以借用鄰接矩陣的特性和算法,來(lái)解決公交線路換乘問(wèn)題。2.2線路矩陣的建立假定有1路、2路、3路、4路這四條公交線路,如圖1。圖中1、2路有交點(diǎn);3、4路有交點(diǎn);2、4有交點(diǎn),相應(yīng)的鄰接矩陣A 如圖2。 圖1 圖2圖32.3鄰接矩陣得到換乘路線在矩陣A 中,(V1,V4為0,則V1到V4經(jīng)過(guò)一次換乘不能到達(dá);(V1,V2為1,則V1到V2經(jīng)

3、過(guò)一次換乘能到達(dá)。(V1,V4在矩陣A*A 為1,說(shuō)明經(jīng)過(guò)二次換乘能夠到達(dá)?！爸虚g線路”是哪條呢?矩陣A 的第一行為t1=(1,1,0,0第四列的轉(zhuǎn)置為t2=(0,1,1,1。t1&t2=(1&0,1&1,0&1,0&1=(0,1,0,0=t3。t3為中的第2個(gè)元素為1,則說(shuō)明“中間線路”是線絡(luò)2。2.4實(shí)現(xiàn)n 次換乘矩陣的建立和運(yùn)算原理2.4.1矩陣的建立一次換乘矩陣為A ,n 次換乘矩陣為A 的n 次方,表達(dá)式為:A n =A*A A 。2.4.2矩陣運(yùn)算原理以1路、4路為例。在初次矩陣A 中a(1,4=0;經(jīng)過(guò)A*A (圖3之后aa(1,4=1。這

4、表明1路中的任何站點(diǎn)經(jīng)過(guò)一次轉(zhuǎn)乘是不能到達(dá)4路中的任何點(diǎn);要到達(dá),必須經(jīng)過(guò)兩次換乘。運(yùn)算過(guò)程:1*0+1*1+0*1+0*1=20=>1過(guò)程原理:1*1,前面“1”來(lái)源于第一行的第二個(gè)數(shù),后面“1”來(lái)源于第二行的第四個(gè)數(shù)。這表明2路是1路和4路之間的“橋梁”。3鄰接矩陣實(shí)現(xiàn)公交換乘的具體方式3.1針對(duì)具體線路如何構(gòu)建鄰接矩陣城市公交具體線路各式各樣,但我們可以歸納了三種情況:內(nèi)外線、往返線路不一致、往返線路一致三種情況。對(duì)于往返一致的線路可以作為一個(gè)頂點(diǎn);內(nèi)外線、往返不一致可以分開作為兩個(gè)不同的頂點(diǎn)。如圖4:圖41路為V1,2路往線為V2,2路返線為V3,3路內(nèi)線為V4,3路外線為V5。

5、V2與V3;V4與V5都認(rèn)為有交點(diǎn)。3.2如何實(shí)現(xiàn)公交換乘收稿日期:2007-06-29作者簡(jiǎn)介:許軍林(1980-,男,江西臨川人,東華理工大學(xué)碩士研究生,研究方向:計(jì)算機(jī)網(wǎng)絡(luò)與分布式數(shù)據(jù)庫(kù);蔣年德(1971-,男,廣西全州人,教授,博士,研究方向:網(wǎng)絡(luò)與分布式數(shù)據(jù)庫(kù)、數(shù)字圖像處理技術(shù)。一種改進(jìn)的公交換乘算法的實(shí)現(xiàn)許軍林,蔣年德(東華理工大學(xué),江西撫州344000摘要:針對(duì)公交線路中存在往返路線不一致、內(nèi)外線路等情況,對(duì)用改進(jìn)的鄰接矩陣方法實(shí)現(xiàn)這一類型的公交換乘進(jìn)行了研究。最后通過(guò)對(duì)線路結(jié)果集進(jìn)行篩選、比較實(shí)現(xiàn)了最少換乘、最少站點(diǎn)為約束條件的公交換乘查詢模塊。關(guān)鍵詞:往返路線;內(nèi)外線;鄰接矩

6、陣;最少換乘;最少站點(diǎn)中圖分類號(hào):TP301文獻(xiàn)標(biāo)識(shí)碼:A 文章編號(hào):1009-3044(200714-30517-02A Realization of Improved Bus Change ArithmeticXU Jun-lin,JIANG Nian-de(East China Institute of Technology,Fuzhou 344000,ChinaAbstract:There are go-return route and out-in routes in bus route,use the method of better adjacency matrix to imp

7、lement this kind of bus change.Finally,by selecting better in the sets of result,it can achieve the aim of least bus change and stations in bus change module.Key words:go-return route;out-in route;adjacency matrix;least bus change;leaststations517人工智能及識(shí)別技術(shù)電腦知識(shí)與技術(shù)本欄目責(zé)任編輯:李桂瑾(上接第499頁(yè)本文將神經(jīng)網(wǎng)絡(luò)技術(shù)應(yīng)用于商業(yè)銀行信用

8、風(fēng)險(xiǎn)評(píng)估中。結(jié)果表明,神經(jīng)網(wǎng)網(wǎng)絡(luò)技術(shù)具有較好的判別功能。其優(yōu)點(diǎn)在于:(1基于主成分的SOM神經(jīng)網(wǎng)絡(luò)模型在算法上和分類效果明顯優(yōu)于BP神經(jīng)網(wǎng)絡(luò);(2神經(jīng)網(wǎng)絡(luò)方法是一種穩(wěn)健的、非參數(shù)的方法,具有很強(qiáng)的非線性映射能力,其學(xué)習(xí)經(jīng)驗(yàn)的能力強(qiáng),分類精度高;(3神經(jīng)網(wǎng)絡(luò)采用分布式存儲(chǔ)結(jié)構(gòu),容錯(cuò)能力強(qiáng)網(wǎng)絡(luò)中少量單元的局部缺損不會(huì)造成網(wǎng)絡(luò)的癱瘓.影響全局.反映了神經(jīng)網(wǎng)絡(luò)的魯棒性。參考文獻(xiàn):1Beaver W.H.Financial ratios as predictors of failureJ.Jour-nal of Accounting Research,1966,(4:7ll02.2王春峰,萬(wàn)海暉.組合預(yù)

9、測(cè)在商業(yè)銀行信用風(fēng)險(xiǎn)評(píng)估中的應(yīng)用J.管理工程學(xué)報(bào),1999,13(1:58.3方洪全,曾勇對(duì).銀行信用風(fēng)險(xiǎn)評(píng)價(jià)體系的比較J.系統(tǒng)工程理論方法應(yīng)用,2004,13(3:214-217.4許東,吳錚.基于Matlab6.x的系統(tǒng)分析與設(shè)計(jì)神經(jīng)網(wǎng)絡(luò)M,西安:西安電子科技大學(xué)出版社,2002.5何曉群.多元統(tǒng)計(jì)分析M.北京:中國(guó)人民大學(xué)出版社, 2004.在實(shí)現(xiàn)公交換乘之前,我們需要做的事是:估計(jì)公交系統(tǒng)中各站點(diǎn)互相到達(dá)最大的換乘數(shù)。因?yàn)楣痪€路是經(jīng)過(guò)嚴(yán)格規(guī)劃好的,因此不會(huì)很大,假設(shè)為4,則我們?cè)跀?shù)據(jù)庫(kù)中分別建立矩陣A、A2、A3、A4。數(shù)據(jù)庫(kù)中保存線路信息時(shí)需要設(shè)定方向字段,以表明此線路是單向還是雙

10、向。3.2.1借助鄰接矩陣得初步結(jié)果集(a求出所有經(jīng)過(guò)起始站點(diǎn)X的路線集合set1和經(jīng)過(guò)所有目的站點(diǎn)Y的路線集合set2。假設(shè)set1=1,23;set2=6,215。把set1和set2的元素分別組成數(shù)對(duì)(V1,V6、(V1,V215、(V23,V6、(V23, V215。(b根據(jù)鄰接矩陣A n(n=1,2,3,4查出所有數(shù)對(duì)的值。以(V1,V6對(duì)應(yīng)的數(shù)據(jù)值為例。先在矩陣A中進(jìn)行查找,如果A中a16為1即數(shù)據(jù)庫(kù)矩陣數(shù)據(jù)表中(V1,V6為1,則說(shuō)明在站點(diǎn)乘1,再乘6線即可達(dá)Y點(diǎn)。(c如果A中a16為0,則在A2中查a16,如果為1,則說(shuō)明X站點(diǎn)經(jīng)過(guò)二次換乘可達(dá)到Y(jié)站點(diǎn)。(d如果A,A2中a16

11、,都為0,則在A3中進(jìn)行查找。如果為1,則說(shuō)明X站點(diǎn)經(jīng)過(guò)三次換乘可以達(dá)到Y(jié)站點(diǎn)。(e中間需要換乘的路線就是:用相應(yīng)矩陣中第1行和第6列的轉(zhuǎn)置進(jìn)行與運(yùn)算,在得到的行列式中元素不為零對(duì)應(yīng)的線路。3.2.2從初步結(jié)果集中得到正確和較優(yōu)結(jié)果3.2.2.1如何判斷方向相一致的相交線路因?yàn)榫€路中存在單向行駛的路線,所以我們要對(duì)初步結(jié)果集進(jìn)行篩選。例如:從A點(diǎn)要B點(diǎn),只有圖5中的第三種情況才能到達(dá)。如何判斷呢?抽取線路a的站點(diǎn)組成字符串L1:AC,抽取線路b的站點(diǎn)組成字符串L2:BC。通過(guò)判斷其站點(diǎn)字符在字符中的相對(duì)位置得到兩個(gè)布爾值,然后把兩個(gè)布爾值進(jìn)行“與”運(yùn)算。b1=L1.charAt(轉(zhuǎn)站>L

12、1.charAt(起站;b2=L2.charAt(終站>L2. charAt(轉(zhuǎn)站;Result=b1&&b2;If(trueok Else false。3.2.2.2如何實(shí)現(xiàn)線路結(jié)果優(yōu)化大部分公交乘客在選擇出行路線時(shí),首先考慮的是換乘次數(shù),其次是出行耗時(shí)和距離長(zhǎng)短。而出行耗時(shí)與換乘的次數(shù)、等車時(shí)間、公交車沿途?？空军c(diǎn)耗時(shí)以及距離的長(zhǎng)短密切相關(guān)。因此,對(duì)于出行耗時(shí)和距離長(zhǎng)短,可以轉(zhuǎn)化為換乘次數(shù)最少的基礎(chǔ)上公交畫沿途?？空军c(diǎn)多少的問(wèn)題。(a實(shí)現(xiàn)最少換乘本文實(shí)現(xiàn)的方式是:先判斷起始點(diǎn)X到目的站點(diǎn)有沒(méi)有直達(dá)車,有則返回;否則在矩陣A中判斷有沒(méi)有換乘一次的方案,有返回;否則在矩陣A2中進(jìn)行判斷。(b實(shí)現(xiàn)最少站點(diǎn)在相同的換乘次數(shù)中,我們可以把乘車線路所有經(jīng)過(guò)的站點(diǎn)組成數(shù)組,數(shù)組長(zhǎng)度越少的說(shuō)明經(jīng)過(guò)的站點(diǎn)越少。這樣相應(yīng)乘車的時(shí)間越少。圖54結(jié)束語(yǔ)本文分析了公交網(wǎng)絡(luò)中公交路線類型,在文獻(xiàn)1的基礎(chǔ)上改進(jìn)了公交線路模型,使模型與實(shí)際交通路線更相符合。提出對(duì)鄰接矩陣的改進(jìn)和完善方法,使改進(jìn)后的方法更易解決實(shí)際中的公交線路模型;把改進(jìn)后的公交換乘方法應(yīng)用到南昌市公交系統(tǒng),較好地實(shí)現(xiàn)了最少換乘、最少站點(diǎn)的公交換乘。因此,對(duì)于