乘公交_看奧運數學建模優(yōu)秀論文

1、12007 高教社杯全國大學生數學建模競賽 高教社杯全國大學生數學建模競賽承 諾 書我們仔細閱讀了中國大學生數學建模競賽的競賽規(guī)則.我們完全明白，在競賽開始后參賽隊員不能以任何方式（包括電話、電子郵件、網上咨詢等）與隊外的任何人（包括指導教師）研究、討論與賽題有關的問題。我們知道，抄襲別人的成果是違反競賽規(guī)則的, 如果引用別人的成果或其他公開的資料（包括網上查到的資料） ，必須按照規(guī)定的參考文獻的表述方式在正文引用處和參考文獻中明確

2、列出。我們鄭重承諾，嚴格遵守競賽規(guī)則，以保證競賽的公正、公平性。如有違反競賽規(guī)則的行為，我們將受到嚴肅處理。我們參賽選擇的題號是（從 A/B/C/D 中選擇一項填寫）： B 我們的參賽報名號為（如果賽區(qū)設置報名號的話）： 所屬學校（請?zhí)顚懲暾娜?重 慶 大 學 參賽隊員 (打印

3、并簽名) ：1. 熊國剛 2. 王杰 3. 黎明 指導教師或指導教師組負責人 (打印并簽名)： 龔劬 日期： 2007 年 9 月 21

4、日賽區(qū)評閱編號（由賽區(qū)組委會評閱前進行編號）：3乘公交，看奧運 乘公交，看奧運【摘要】 【摘要】本文要解決的問題是以即將舉行的 08 年北京奧運會為背景而提出的。人們?yōu)榱四墁F場觀看奧運會，必然會面對出行方式與路線選擇的問題。因此如何快速、高效地從眾多可行路線中選出最優(yōu)路線成為了解決此問題的關鍵。鑒于公交系統(tǒng)網絡的復雜性，我們沒有采用常規(guī)的 Dijkstra 算法，而采用了高效的廣度優(yōu)先算法。其基本思想是從經過起（始）點的路線出發(fā)，搜尋出

5、轉乘次數不超過兩次的可行路線，然后對可行解進行進一步處理。為滿足不同查 詢者要求，我們對三個問題都分別建立了以時間、轉乘次數、費用最小為目標的優(yōu)化模型。針對問題一（只考慮公汽系統(tǒng)） ，我們建立了模型一并通過 VC++編程得到 了任意兩個站點間的多種最優(yōu)路線，并得出所求站點間最優(yōu)路線的最優(yōu)值，如 下表所示：出發(fā)站?終點站S3359?S1828S1557?S0481S0971?S0485S0008?S0073S0148?S0485S0087

6、?S3676最短耗時（min） 64 106 106 67 106 46最少轉乘次數 （次）1 2 1 1 2 2最少費用（元） 3 3 3 2 3 3模型二是根據問題二（同時考慮公汽和地鐵系統(tǒng)）建立的，同樣用 VC++編程得到所求站點間的最優(yōu)路線，如下表所示：出發(fā)站?終點站S3359?S1828S1557?S0481S0971?S0485S0008?S0073S0148?S0485S0087?S3676最短耗時（min） 64 106

7、 96 55 87.5 33最少轉乘次數 （次）1 2 1 1 2 0最少費用（元） 3 3 3 2 3 3對問題三（將步行考慮在內）我們建立了模型三的優(yōu)化模型，然后在模型改進里又建立了圖論模型。本文的主要特點在于，所用算法的效率十分顯著。在對原始數據僅做簡單預處理的條件下，搜索任意站點間的最優(yōu)路線所需的平均時間不超過 0.5 秒。 另外，本文所建立的模型簡單、所用算法比較清晰，易于程序實現，對公交線 路自主查詢計算機系統(tǒng)的實現具有現實