最優(yōu)公交車選乘問題的算法分析及實現(xiàn).pdf

1、本論文主要針對三個公交車換乘問題建立了合理的圖模型然后設計了高效的算法，通過應用這些算法設計并實現(xiàn)了一個公交車查詢系統(tǒng)。
　　 本文充分考慮了用戶的需求，分別以最短路徑（即最小時間）、最少換乘、最小費用三個目標函數(shù)提出了三個算法問題，然后針對這三個問題建立了圖模型，通過對不同問題的性質(zhì)和結構的分析，提出了一些圖模型上數(shù)據(jù)壓縮的方法。然后在這些圖模型上設計了高效的算法，同時對這些算法進行了時間復雜度分析。對于最短路徑問題，本文直接

2、建立圖上的最短路徑模型，并用Dijkstra算法進行求解。對于最少換乘問題，本文建立了兩個模型，一個是用車次最為頂點集建立的圖模型，通過特殊賦值來得到一個最短路徑問題，另一個則是用連接接矩陣的連乘來表示的連通性質(zhì)的模型。對于最小費用問題，本文可以使用前面兩個問題建立的相同模型，只是在邊上賦的值不同，兩個站點間的邊的權值則為這兩個站點間直達的最便宜公交車費用，這樣，在建立的圖模型下本文也僅僅只需要使用用Dijkstra算法進行一個最短路徑

3、問題的求解即可。
　　 最后本文設計并實現(xiàn)了一個公交車換乘系統(tǒng)，該系統(tǒng)采用B/S結構，而前臺界面主要使用了Extjs庫與HTML相結合的技術實現(xiàn)，后臺數(shù)據(jù)庫則用的是SQLSEVER2000。該系統(tǒng)擁有一般客戶和管理員兩個角色，一般客戶能在不需要登錄的情況下直接進行站點查詢、線路查詢、站站查詢等，其中站站查詢要求輸入兩個站點，然后根據(jù)上面提到的三個目標最短路徑、最少換乘、最小費用查詢兩個站點間的最優(yōu)乘車路線。而管理員則能對數(shù)據(jù)庫里