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

2、交換乘。2鄰接矩陣實現公交換乘理論2.1鄰接矩陣實現公交換乘基本思想把每條公交線作為圖中一個頂點,任意兩條公交線路之間的聯系取決兩者之間有無交點(共同的停靠站點,相應地該兩條線路之間的矩陣元素值為1或者0。這樣就把城市公交線路系統可以抽象為n*n 鄰接矩陣,可以借用鄰接矩陣的特性和算法,來解決公交線路換乘問題。2.2線路矩陣的建立假定有1路、2路、3路、4路這四條公交線路,如圖1。圖中1、2路有交點;3、4路有交點;2、4有交點,相應的鄰接矩陣A 如圖2。 圖1 圖2圖32.3鄰接矩陣得到換乘路線在矩陣A 中,(V1,V4為0,則V1到V4經過一次換乘不能到達;(V1,V2為1,則V1到V2經

3、過一次換乘能到達。(V1,V4在矩陣A*A 為1,說明經過二次換乘能夠到達。“中間線路”是哪條呢?矩陣A 的第一行為t1=(1,1,0,0第四列的轉置為t2=(0,1,1,1。t1&t2=(1&0,1&1,0&1,0&1=(0,1,0,0=t3。t3為中的第2個元素為1,則說明“中間線路”是線絡2。2.4實現n 次換乘矩陣的建立和運算原理2.4.1矩陣的建立一次換乘矩陣為A ,n 次換乘矩陣為A 的n 次方,表達式為:A n =A*A A 。2.4.2矩陣運算原理以1路、4路為例。在初次矩陣A 中a(1,4=0;經過A*A (圖3之后aa(1,4=1。這

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

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

6、陣;最少換乘;最少站點中圖分類號:TP301文獻標識碼:A 文章編號: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人工智能及識別技術電腦知識與技術本欄目責任編輯:李桂瑾(上接第499頁本文將神經網絡技術應用于商業銀行信用

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

9、測在商業銀行信用風險評估中的應用J.管理工程學報,1999,13(1:58.3方洪全,曾勇對.銀行信用風險評價體系的比較J.系統工程理論方法應用,2004,13(3:214-217.4許東,吳錚.基于Matlab6.x的系統分析與設計神經網絡M,西安:西安電子科技大學出版社,2002.5何曉群.多元統計分析M.北京:中國人民大學出版社, 2004.在實現公交換乘之前,我們需要做的事是:估計公交系統中各站點互相到達最大的換乘數。因為公交線路是經過嚴格規劃好的,因此不會很大,假設為4,則我們在數據庫中分別建立矩陣A、A2、A3、A4。數據庫中保存線路信息時需要設定方向字段,以表明此線路是單向還是雙

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

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

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