圖論結(jié)課論文

《圖論結(jié)課論文》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫(kù)。

1、乘公交，看奧運(yùn)通信學(xué)院10級(jí)研一8班學(xué)號(hào)【摘要】本文要解決的問題是以即將舉行的08年北京奧運(yùn)會(huì)為背景而提出的。人們?yōu)榱四墁F(xiàn)場(chǎng)觀看奧運(yùn)會(huì)，必然會(huì)面對(duì)出行方式與路線選擇的問題。因此如何快速、高效地從眾多可行路線中選出最優(yōu)路線成為了解決此問題的關(guān)鍵。鑒于公交系統(tǒng)網(wǎng)絡(luò)的復(fù)雜性，我們沒有采用常規(guī)的Dijkstra算法，而采用了高效的廣度優(yōu)先算法。其基本思想是從經(jīng)過起（始）點(diǎn)的路線出發(fā)，搜尋出轉(zhuǎn)乘次數(shù)不超過兩次的可行路線，然后對(duì)可行解進(jìn)行進(jìn)一步處理。為滿足不同查詢者要求，我們對(duì)三個(gè)問題都分別建立了以時(shí)間、轉(zhuǎn)乘次數(shù)、費(fèi)用最小為目標(biāo)的

2、優(yōu)化模型。本文的主要特點(diǎn)在于，所用算法的效率十分顯著。在對(duì)原始數(shù)據(jù)僅做簡(jiǎn)單預(yù)處理的條件下，搜索任意站點(diǎn)間的最優(yōu)路線所需的平均時(shí)間不超過0.5秒。另外，本文所建立的模型簡(jiǎn)單、所用算法比較清晰，易于程序?qū)崿F(xiàn)，對(duì)公交線路自主查詢計(jì)算機(jī)系統(tǒng)的實(shí)現(xiàn)具有現(xiàn)實(shí)指導(dǎo)作用。關(guān)鍵字：轉(zhuǎn)乘次數(shù)廣度優(yōu)先算法查詢效率實(shí)時(shí)系統(tǒng)一問題的重述為了迎接2008年奧運(yùn)會(huì)，北京公交做了充分的準(zhǔn)備，首都的公交車大都煥然一新，增強(qiáng)了交通的安全性和舒適性，公交線路已達(dá)800條以上，使得公眾的出行更加通暢、便利。但同時(shí)也面臨多條線路的選擇問題。為滿足公眾查詢公交線

3、路的選擇問題，某公司準(zhǔn)備研制開發(fā)一個(gè)解決公交線路選擇問題的自主查詢計(jì)算機(jī)系統(tǒng)。這個(gè)系統(tǒng)的核心是線路選擇的模型與算法，另外還應(yīng)該從實(shí)際情況出發(fā)考慮，滿足查詢者的各種不同需求。需要解決的問題有：1、僅考慮公汽線路，給出任意兩公汽站點(diǎn)之間線路選擇問題的一般數(shù)學(xué)模型與算法。并根據(jù)附錄數(shù)據(jù)，利用模型算法，求出以下6對(duì)起始站到終到站最佳路線。(1)、S3359→S1828(2)、S1557→S0481(3)、S0971→S0485(4)、S0008→S0073(5)、S0148→S0485(6)、S0087→S36762、同時(shí)考慮

4、公汽與地鐵線路，解決以上問題。二符號(hào)說明：第i條公汽線路標(biāo)號(hào),i=1,2…10400,當(dāng)時(shí),表示上行公汽路線,當(dāng)時(shí),表示與上行路線相對(duì)應(yīng)的下行公汽路線；：經(jīng)過第i條公汽路線的第g個(gè)公汽站點(diǎn)標(biāo)號(hào)；13：第j條地鐵路線標(biāo)號(hào),j=1,2；：經(jīng)過第j條地鐵線路的第h個(gè)地鐵站點(diǎn)標(biāo)號(hào)；：轉(zhuǎn)乘n次的路線；：選擇第k種路線的總時(shí)間；：選擇第k種路線公汽換乘公汽的換乘次數(shù)；：選擇第k種路線地鐵換乘地鐵的換乘次數(shù)；：選擇第k種路線地鐵換乘公汽的換乘次數(shù)；：選擇第k種路線公汽換乘地鐵的換乘次數(shù)；：第k種路線、乘坐第m輛公汽的計(jì)費(fèi)方式，其中：

5、表示實(shí)行單一票價(jià)，表示實(shí)行分段計(jì)價(jià)；：第k種路線，乘坐第m輛公汽的費(fèi)用；：選擇第k種路線的總費(fèi)用；：選擇第k種路線，乘坐第m輛公汽需要經(jīng)過的公汽站個(gè)點(diǎn)數(shù)；：選擇第k種路線，乘坐第n路地鐵需要經(jīng)過的地鐵站個(gè)點(diǎn)數(shù)；：表示對(duì)于第k種路線的第m路公汽的路線是否選擇步行，為0-1變量，表示不選擇步行，表示選擇步行；：對(duì)于第k種路線的第n路地鐵的路線是否選擇步行，為0-1變量，表示不選擇步行，表示選擇步行；三模型假設(shè)3.1基本假設(shè)1、相鄰公汽站平均行駛時(shí)間(包括停站時(shí)間)：3分鐘2、相鄰地鐵站平均行駛時(shí)間(包括停站時(shí)間)：2.5分

6、鐘3、公汽換乘公汽平均耗時(shí)：5分鐘(其中步行時(shí)間2分鐘)4、地鐵換乘地鐵平均耗時(shí)：4分鐘(其中步行時(shí)間2分鐘)135、地鐵換乘公汽平均耗時(shí)：7分鐘(其中步行時(shí)間4分鐘)6、公汽換乘地鐵平均耗時(shí)：6分鐘(其中步行時(shí)間4分鐘)7、公汽票價(jià)：分為單一票價(jià)與分段計(jì)價(jià)兩種；單一票價(jià)：1元其中分段計(jì)價(jià)的票價(jià)為：0～20站：1元21～40站：2元40站以上：3元8、地鐵票價(jià)：3元（無論地鐵線路間是否換乘）9、假設(shè)同一地鐵站對(duì)應(yīng)的任意兩個(gè)公汽站之間可以通過地鐵站換乘，且無需支付地鐵費(fèi)3.2其它假設(shè)10、查詢者轉(zhuǎn)乘公交的次數(shù)不超過兩次；

7、11、所有環(huán)行公交線路都是雙向的；12、地鐵線T2也是雙向環(huán)行的；13、各公交車都運(yùn)行正常，不會(huì)發(fā)生堵車現(xiàn)象；14、公交、列車均到站停車四問題的分析在北京舉行奧運(yùn)會(huì)期間，公眾如何在眾多的交通路線中選擇最優(yōu)乘車路線或轉(zhuǎn)乘路線去看奧運(yùn)，這是我們要解決的核心問題。針對(duì)此問題，我們考慮從公交線路的角度來尋求最優(yōu)線路。首先找出過任意兩站點(diǎn)（公眾所在地與奧運(yùn)場(chǎng)地）的所有路線，將其存儲(chǔ)起來，形成數(shù)據(jù)文件。這些路線可能包含有直達(dá)公交線路，也有可能是兩條公交線路通過交匯而形成的（此時(shí)需要轉(zhuǎn)乘公交一次），甚至更多公交線路交匯而成。然后在這

8、些可行路線中搜尋最優(yōu)路線。對(duì)于路線的評(píng)價(jià)，我們可以分別以總行程時(shí)間，總轉(zhuǎn)乘次數(shù)，總費(fèi)用為指標(biāo)，也可以將三種指標(biāo)標(biāo)準(zhǔn)化后賦以不同權(quán)值形成一個(gè)綜合指標(biāo)。而最優(yōu)路線則應(yīng)是總行程時(shí)間最短，總費(fèi)用最少或總轉(zhuǎn)乘次數(shù)最少，或者三者皆有之。之所以這樣考慮目標(biāo)，是因?yàn)閷?duì)于不同年齡階段的查詢者，他們追求的目標(biāo)會(huì)有所不同，比如青年人比較熱衷于比賽，因而