2002高教社杯全國(guó)大學(xué)生數(shù)學(xué)建模競(jìng)賽題目

1、2016江西財(cái)經(jīng)大學(xué)數(shù)學(xué)建模競(jìng)賽（A題）基于車流量分析的城市交通管理參賽隊(duì)員：王嚴(yán)康、蔡姬、熊苗苗參賽隊(duì)編號(hào)：20160302016年5月20日5月25日2016江西財(cái)經(jīng)大學(xué)數(shù)學(xué)建模競(jìng)賽承諾書我們仔細(xì)閱讀了江西財(cái)經(jīng)大學(xué)數(shù)學(xué)建模競(jìng)賽的競(jìng)賽章程。我們完全明白，在競(jìng)賽開始后參賽隊(duì)員不能以任何方式（包括電話、電子郵件、網(wǎng) 上咨詢等）與隊(duì)外的任何人研究、討論與賽題有關(guān)的問題。我們知道，抄襲別人的成果是違反競(jìng)賽規(guī)則的 ，如果引用別人的成果或其他公開的 資料（包括網(wǎng)上查到的資料），必須按照規(guī)定的參考文獻(xiàn)的表述方式在正文引用處和參 考文獻(xiàn)中明確列出。我們鄭重承諾，嚴(yán)格遵守競(jìng)賽規(guī)則，以保證競(jìng)賽的公正、公平性。如

2、有違反競(jìng)賽規(guī) 則的行為，我們將受到嚴(yán)肅處理。我們參賽選擇的題號(hào) 是（從A/B/C中選擇一項(xiàng)填寫）： A我們的參賽隊(duì)編號(hào) 為 2016030 參賽隊(duì)員（打印并簽名）：隊(duì)員1.姓名王嚴(yán)康專業(yè)班級(jí)14計(jì)算機(jī)一班隊(duì)員2.姓名蔡姬專業(yè)班級(jí)14計(jì)算機(jī)一班隊(duì)員3.姓名熊苗苗專業(yè)班級(jí)14計(jì)算機(jī)一班日期：2016 年5月25 日貳2016江西財(cái)經(jīng)大學(xué)數(shù)學(xué)建模競(jìng)賽編號(hào)和閱卷專用頁(yè)參賽隊(duì)編號(hào)：參賽隊(duì)員填寫參賽隊(duì) 員姓名所有數(shù)學(xué)類與計(jì)算機(jī)類課程成績(jī) （意愿參加全國(guó)競(jìng)賽者填寫）是否選 修建模 課程是否愿 參加全 國(guó)競(jìng)賽在校獲 獎(jiǎng)項(xiàng)目王嚴(yán)康高數(shù)1:90 ;高數(shù)2:90 ;線代：93; C+: 83; C語(yǔ)言：71;數(shù)據(jù)結(jié)

3、構(gòu)：79； Python : 67是是無蔡姬高數(shù)1:95 ;高數(shù)2:94 ;線代：92; C+: 90; C語(yǔ)言：74;數(shù)據(jù)結(jié)構(gòu)：85; Python : 76是是無熊苗苗高數(shù)1:79 ;高數(shù)2:67 ;線代：60; C+: 80; C語(yǔ)言：70;數(shù)據(jù)結(jié)構(gòu)：70; Python : 79是是無閱卷填寫，參賽者不得填寫評(píng)分（百分制）評(píng)閱人最終得分小組評(píng)價(jià)負(fù)責(zé)人閱卷 專家 評(píng)語(yǔ)備注1、是否選修數(shù)學(xué)建模：指本學(xué)期是否選修了數(shù)學(xué)建模課程2、是否有意愿參加全國(guó)競(jìng)賽 ：指參加今年的全國(guó)大學(xué)生數(shù)學(xué)建模競(jìng)賽，一經(jīng)選定，不得退賽，否則將建議學(xué)生所在學(xué)院給予處分。培訓(xùn)時(shí)間：2016年8月5日開始。江西財(cái)經(jīng)大學(xué)數(shù)學(xué)

4、建模競(jìng)賽組委會(huì)2016年5月15日制定叁基于車流量分析的城市交通管理摘 要根據(jù)問題城市私家車數(shù)量越來越多，交通管理技術(shù)跟不上導(dǎo)致交通擁堵狀況嚴(yán)重， 日益增長(zhǎng)的交通需求與城市道路基礎(chǔ)建設(shè)之間的矛盾已成為目前城市交通的主要矛盾。 由于交通問題已經(jīng)開始影響人們的正常生產(chǎn)生活。本篇論文從道路的實(shí)時(shí)車流量變化來控制車的行車路線，減少行車壓力大的路口的 壓力，提高機(jī)動(dòng)車到達(dá)目的地的效率。一、車流量監(jiān)控模型我們分析采用路段平均行程速度、交通流量、路段飽和度、三個(gè)評(píng)價(jià)指標(biāo)來綜合放 映道路擁堵情況。我們選取八一廣場(chǎng)周圍為例，為了避免數(shù)據(jù)的不完整性導(dǎo)致對(duì)應(yīng)時(shí)事 件結(jié)果的不確定性，綜合考慮我們采用模糊綜合平價(jià)模型來

5、對(duì)問題進(jìn)行分析和求解。列出非常順暢、順暢、緩慢、擁堵和嚴(yán)重?fù)矶挛鍌€(gè)評(píng)判標(biāo)準(zhǔn)來綜合評(píng)價(jià)。確定出其隸屬度rx，通過已確定的模糊評(píng)價(jià)矩陣 R得出擁擠度系數(shù)B。二、最優(yōu)子結(jié)構(gòu)優(yōu)化路線模型基于模型一所求擁擠系數(shù)B,與道路長(zhǎng)度綜合分析，算出有關(guān)行車時(shí)間權(quán)值t，通過 建立多段圖模型，求解到達(dá)目的地的最優(yōu)路線即權(quán)值之和最?。倳r(shí)間T）的結(jié)果。在n個(gè)路口之間建立連通路線，最多設(shè)置n（n-1）/2條線路，最少需n-1條線路使起 點(diǎn)到達(dá)終點(diǎn)，所以可將問題轉(zhuǎn)化為：在可能的線路中選擇 n-1條，求得起始路口到目的 路口的最短加權(quán)值，使得所耗費(fèi)的總時(shí)間（各邊權(quán)值之和）最短。本算法綜合考慮整體城市的交通網(wǎng)絡(luò)情況，此時(shí)的交通

6、狀態(tài)是一種不斷變化的動(dòng)態(tài) 過程，具有很強(qiáng)的隨機(jī)性和偶然性。而交通擁堵的潛伏、發(fā)展和產(chǎn)生與具有連貫性和相關(guān)性的特點(diǎn)，交通阻塞的發(fā)生與它 的過去和現(xiàn)狀緊密相關(guān)，因此，有可能通過對(duì)交通狀態(tài)的現(xiàn)狀和歷史進(jìn)行綜合分析。對(duì)不 確定或不精確的知識(shí)或信息中做出推理。模型假設(shè)在每輛機(jī)動(dòng)車都設(shè)有道路實(shí)時(shí)監(jiān)控的狀況，會(huì)采取算法給出的建議。【關(guān)鍵字】：交通管理模糊模型評(píng)價(jià)多段圖最優(yōu)子結(jié)構(gòu)動(dòng)態(tài)算法10一、問題重述1.1 問題背景（ 1）機(jī)動(dòng)車數(shù)量持續(xù)增長(zhǎng)。隨著我國(guó)經(jīng)濟(jì)社會(huì)持續(xù)快速發(fā)展，群眾購(gòu)車剛性需求旺盛，汽車保有量繼續(xù)呈快速 增長(zhǎng)趨勢(shì)， 2015 年新注冊(cè)登記的汽車達(dá) 2385 萬輛，保有量?jī)粼?1781萬輛，均為歷

7、史最 高水平。汽車占機(jī)動(dòng)車的比率迅速提高，近五年汽車占機(jī)動(dòng)車比率從47.06%提高到61.82%，群眾機(jī)動(dòng)化出行方式經(jīng)歷了從摩托車到汽車的轉(zhuǎn)變，交通出行結(jié)構(gòu)發(fā)生了根本 性變化。（ 2）私家車保有量上升。2015 年，小型載客汽車達(dá) 1.36 億輛，其中，以個(gè)人名義登記的小型載客汽車（私 家車）達(dá)到 1.24 億輛，占小型載客汽車的 91.53%。與 2014 年相比，私家車增加 1877 萬輛，增長(zhǎng) 17.77%。全國(guó)有 40 個(gè)城市的汽車保有量超過百萬輛，北京、成都、深圳、 上海、重慶、天津、蘇州、鄭州、杭州、廣州、西安 11 個(gè)城市汽車保有量超過 200 萬 輛。全國(guó)平均每百戶家庭擁有 3

8、1 輛私家車，北京、成都、深圳等大城市每百戶家庭擁 有私家車超過 60 輛。（3）交通問題日益突出。 隨著城市人口以及城市交通流的增加，城市特別是大城市的交通問題普通成為焦點(diǎn) 問題。路網(wǎng)不暢、設(shè)施不足、交通擁堵等問題越來越突出；行車難、停車難、交通秩序 混亂等問題日益突顯，對(duì)城市交通管理造成的沖擊和壓力越來越大。城市道路交通擁擠 堵塞問題已成為制約經(jīng)濟(jì)發(fā)展、降低人民生活質(zhì)量、削弱經(jīng)濟(jì)活力的瓶頸之一。解決交通堵塞問題勢(shì)在必行。據(jù)美國(guó)得克薩斯州運(yùn)輸研究所 2006年底公布的數(shù)據(jù)顯示， 被稱為“汽車王國(guó)” 的美 國(guó)每年因交通堵塞造成的經(jīng)濟(jì)損失高達(dá) 1000億美元。 2007年中國(guó)社科院數(shù)量經(jīng)濟(jì)與技

9、術(shù)經(jīng)濟(jì)研究所測(cè)算， 北京市每天因?yàn)槎萝囋斐傻纳鐣?huì)成本達(dá)到 4000 萬元，每年損失 146 億元。對(duì)于交通堵塞這個(gè)世界性難題，各國(guó)政府和民間都在為解決這個(gè)問題進(jìn)行廣泛的 研究。1.2 問題提出在經(jīng)濟(jì)發(fā)展越來越快，私家車數(shù)量越來越多，交通為題日益突出的大背景下，如何 解決交通擁堵問題成為我們研究的主要問題。根據(jù)近幾年來各地的道路現(xiàn)狀，我們可以看到，即使是在道路不斷拓寬新建的條件下，交通壓力仍持續(xù)增大，機(jī)動(dòng)車的增長(zhǎng)帶來了越來越多的問題。這時(shí)候，在現(xiàn)有交通條件下提高交通管理技術(shù)就顯得尤為重要。本次數(shù)學(xué)建模大賽題目就致力于為交通管理技術(shù)提供新方法，提出算法，建立數(shù)學(xué) 模型，設(shè)計(jì)出更優(yōu)良的交通管理技術(shù)，

10、提供更智能的技術(shù)和方法。問題分析主要分為兩個(gè)過程如下：1：我們主要目的是求得各個(gè)路口的實(shí)時(shí)的車流量信息，首先選取的實(shí)體地點(diǎn)是八一廣場(chǎng)附近的路線，由于路口較復(fù)雜，我們只監(jiān)測(cè)部分路口的相關(guān)時(shí)段的實(shí)時(shí)車流量，再 利用模糊模型評(píng)價(jià)方法對(duì)車流量設(shè)置評(píng)價(jià)標(biāo)準(zhǔn)，分出非常順暢，順暢，緩慢，擁堵，非 常擁堵五個(gè)等級(jí)。對(duì)于所得的數(shù)據(jù)進(jìn)行處理，建立數(shù)學(xué)模型，畫出擁堵曲線，得到各個(gè) 路口的擁堵指數(shù)bk。2：我們的主要目的是求得到達(dá)目的地的最短時(shí)間的最優(yōu)結(jié)果，首先將各個(gè)路口抽象為點(diǎn)，路抽象成連接點(diǎn)之間的線段，建立數(shù)學(xué)模型多段圖表示我們的問題。根據(jù)所求的擁堵指數(shù)bk結(jié)合各個(gè)路口之間的距離構(gòu)成多段圖的權(quán)值， 在起始路口和

11、目的路口的n個(gè)路口之間選擇最有路線，利用貪心算法和最優(yōu)子結(jié)構(gòu)算法計(jì)算多段圖的 最優(yōu)解，使得所耗費(fèi)的總時(shí)間（各邊權(quán)值之和）最短，求得道路交通管理建議最優(yōu)路線， 實(shí)現(xiàn)智能管理交通。三、模型假設(shè)（1）假設(shè)無交通事故發(fā)生，無惡劣天氣、自然災(zāi)害等的影響。（2）機(jī)動(dòng)車的型號(hào)大小、行能等完全相同， 忽略其他影響不大的交通模型，所有道 路都是相同的類型。（3）各個(gè)路口規(guī)模相同，擁堵情況只集中在早晚高峰期間。（4）只考慮機(jī)動(dòng)車，忽略其他自行車等各種車輛。（5）各個(gè)機(jī)動(dòng)車速度都只受到車流量的影響，排除個(gè)人因素。四、符號(hào)設(shè)計(jì)符號(hào)符號(hào)說明X評(píng)價(jià)因素集Z五種服務(wù)標(biāo)準(zhǔn)評(píng)判集W各項(xiàng)指標(biāo)所占權(quán)重Y交通狀態(tài)變量集bk交通擁堵指

12、數(shù)V車流速度A路段占有率K車流密度T到達(dá)總時(shí)間S路程五、模型的建立和求解5.1車流量監(jiān)控模型5.1.1問題分析根據(jù)題設(shè)要求，我們?nèi)“艘粡V場(chǎng)周圍為研究對(duì)象，如圖所示,5.1.2問題評(píng)價(jià)標(biāo)準(zhǔn)按照道路擁堵程度的不同劃分為五個(gè)級(jí)別，分別為非常暢通、暢通、緩慢、擁堵和 嚴(yán)重?fù)矶?。通過浮動(dòng)車數(shù)據(jù)的回歸擬合分析，并參考相關(guān)的標(biāo)準(zhǔn)，分別確定三個(gè)評(píng)價(jià)指 標(biāo)不同評(píng)價(jià)等級(jí)的閾值。（1）路段不同時(shí)段平均行程速度評(píng)判標(biāo)準(zhǔn)為了確定路段不同時(shí)段平均行程速度的評(píng)判標(biāo)準(zhǔn)，根據(jù)車速調(diào)查相關(guān)理論1和交通 流參數(shù)之間的關(guān)系可得出主干道平均行程速度的評(píng)判標(biāo)準(zhǔn)（見表1）。服務(wù)等級(jí)非常順暢順暢緩慢擁堵嚴(yán)重?fù)矶轮鞲傻?45，+x)(35,4

13、5 )(25,35)(15,25 )(0,15)表一平均行程速度評(píng)判標(biāo)準(zhǔn)單位：km/h（2）車流量評(píng)判標(biāo)準(zhǔn)由于車流量取決于路段平均行程速度和自由流速度，為使評(píng)價(jià)結(jié)果具有一致性，利 用浮動(dòng)車調(diào)查數(shù)據(jù)進(jìn)行平均行程速度回歸擬合分析。主干道的回歸擬合方程如下：bk=7.665e-8xA2-0/000047328x+1.00009 （ 程序見附件 1）data 1quadratic4000500090000.9 0.B -0.70.6 0.5 -0.4 ”0.3、丿0,2 I1101 00020003000（上圖反應(yīng)了車流量與擁堵系數(shù)之間的數(shù)量關(guān)系）依據(jù)平均行程速度評(píng)判標(biāo)準(zhǔn)的劃分，確定不同的車流量擁堵級(jí)

14、別，具體結(jié)果如表 所示。服務(wù)等級(jí);非常順暢順暢緩慢擁堵嚴(yán)重?fù)矶轮鞲傻?000:(4000,5000)(3000,4000)(2000,3000)表nrbJ = s gj式中，。令取值為0,1, 越接近1,道路越堵；反之，道路 越順暢。其中擁堵指數(shù)與擁堵程度的對(duì)應(yīng)關(guān)系如下圖所示：擁堵指數(shù)與擁堵對(duì)應(yīng)關(guān)系評(píng)價(jià)指標(biāo)非常順暢順暢緩慢擁堵嚴(yán)重?fù)矶聯(lián)矶轮笖?shù)0,0.20.2,0.40.4,0.60.6,0.80.8,15.1.4 模型的求解根據(jù)檢測(cè)的數(shù)據(jù)，我們將其分為0:00 5:00,5:00-7:00,7:00-9:00 等9個(gè)階段來分 析(見表格111)表格111時(shí) 間0:005:007:009:001

15、1:0013:0016:0018:0020:005:007:009:0011:0013:0016:008:0020:0023:000.150.20.80.910.750.890.950.450.38實(shí)施刖 擁擠度評(píng)價(jià)非常 順暢順暢嚴(yán)重 擁堵嚴(yán)重 擁堵嚴(yán)重 擁堵嚴(yán)重 擁堵嚴(yán)重 擁堵緩慢順暢實(shí)施后 擁擠度0,150.170.680.840.590.780.770.350.36評(píng)價(jià)非常 順暢非常 順暢擁堵嚴(yán)重 擁堵緩慢擁堵?lián)矶马槙稠槙?.2最優(yōu)子結(jié)構(gòu)優(yōu)化路線5.2.1冋題分析根據(jù)5.1所求的擁堵指數(shù)和道路長(zhǎng)度綜合分析，求解到達(dá)目的地的最優(yōu)路線。在n個(gè)路口之間建立連通路線，最多設(shè)置n（n-1）/2條線

16、路，最少需n-1條線路使起 點(diǎn)到達(dá)終點(diǎn)，所以可將問題轉(zhuǎn)化為：在可能的線路中選擇 n-1條，求得起始路口到目的 路口的最短加權(quán)值，使得所耗費(fèi)的總時(shí)間（各邊權(quán)值之和）最短。5.2.2評(píng)價(jià)標(biāo)準(zhǔn)求得到達(dá)目的地的系數(shù)作為無向連通圖邊的權(quán)值, 最短的情況為最優(yōu)路線結(jié)果.S t根據(jù)公式（1-bk）v總時(shí)間 T=t1+t2+tn5.2.3模型建立為確定帶權(quán)重的有向圖的最優(yōu)子結(jié)構(gòu)，我們根據(jù)動(dòng)態(tài)規(guī)劃算法抽象出數(shù)學(xué)模型如下:1、 頂點(diǎn)表示路口2、邊一一各個(gè)路口連通的道路3、邊的權(quán)到達(dá)目的地的系數(shù)t問題可以理解為在此網(wǎng)中找一條最短路徑，它的每條邊上的權(quán)值之和是所有路徑中 最小的-最優(yōu)子結(jié)構(gòu)。每一點(diǎn)最優(yōu)都是上一點(diǎn)最優(yōu)加

17、上這段長(zhǎng)度 即當(dāng)前最優(yōu)只與上一步有關(guān)。*Us 初始值，uj第j段的最優(yōu)值。5.2.4模型求解（1）找出最優(yōu)解的性質(zhì)，并刻畫其結(jié)構(gòu)特征；cost（ i, j）=即在各條路線中找出最權(quán)值t相加最小的值。出發(fā)點(diǎn)為0，目的地為9 即根據(jù)公式cost（k,t）=00=i=k-2min c（j, p） cost（i i, p）, jV,P V 1, JpUE（2）遞歸地定義最優(yōu)值（寫出動(dòng)態(tài)規(guī)劃方程）；以自底向上的方式計(jì)算出最優(yōu)值；根據(jù)計(jì)算最優(yōu)值時(shí)得到的信息，構(gòu)造一個(gè)最優(yōu)解。步驟1-3是動(dòng)態(tài)規(guī)劃算法的基本步驟。在只需要求出最優(yōu)值的情形, 步驟4可以省略，步驟3中記錄的信息也較少；若需要求出問題的一個(gè)最優(yōu)解，

18、則必須執(zhí)行步驟 4,步驟3中記錄的信息必須足夠多以便構(gòu)造最優(yōu)解。即：（3）用一個(gè)數(shù)組costn作為存儲(chǔ)子問題解的表格costi 表示從頂點(diǎn) i 到終點(diǎn) n-1 的最短路徑，數(shù)組 pathn 存儲(chǔ)狀態(tài)， pathi 表 示從頂點(diǎn) i 到終點(diǎn) n-1 的路徑上頂點(diǎn) i 的下一個(gè)頂點(diǎn)。則：costi=mincij+costj(i j i&k=0; i-)2.1 對(duì)頂點(diǎn) i 的每一個(gè)鄰接點(diǎn) j ，根據(jù)式 6.7 計(jì)算 costi;2.2 根據(jù)式 6.8 計(jì)算 pathi;輸出最短路徑長(zhǎng)度 cost0; 輸出最短路徑經(jīng)過的頂點(diǎn)：4.1 i=0 4.2 循環(huán)直到 pathi=n-14.2.1 輸出 pat

19、hi; 4.2.2 i=pathi;( 6)形象描述如下：由于多段圖將頂點(diǎn)劃分為氐個(gè)互不相交的子集.所以，多 段圖劃分為Jt段，每一段包含頂點(diǎn)的一個(gè)子集口不失一般 性，將多段圖的頂點(diǎn)按照段的順序進(jìn)行編號(hào)，同一段內(nèi) 頂點(diǎn)的相互順序無關(guān)緊要。假設(shè)圖中的頂點(diǎn)個(gè)數(shù)為從 則源點(diǎn)的編號(hào)為0,終點(diǎn)啲編號(hào)為刃亠并且，對(duì)圖中的 任何一條邊（血V）,頂點(diǎn)M的編號(hào)小于頂點(diǎn)卩的編號(hào)。下面考慮多段圖的最短路徑問題的填表形式.用一個(gè)數(shù)組costn作為存儲(chǔ)子問題解的表格，表示 從頂點(diǎn)i到終點(diǎn)ml的最短路徑，數(shù)組pathn存儲(chǔ)狀態(tài)，pathfi 表示從頂點(diǎn)i到終點(diǎn)n-1的路徑上頂點(diǎn)i的下一個(gè)頂點(diǎn)。則動(dòng)態(tài)規(guī)劃函數(shù)為：costE

20、QarnlnlCij+costU (ijn且頂點(diǎn)j是頂點(diǎn)i的鄰接點(diǎn))(1)(2)pathi=使 Cij+costj瑕小的 j 對(duì)多段圖的邊価“)，用q”表示邊上的權(quán)值，將從源點(diǎn)s到終 點(diǎn)t的最短路徑記為船矢紐 則從源點(diǎn)0到終點(diǎn)9的最短路徑 tf(O, 9)由下式確定：川(0, 9)=minc01+ d(l9), %+ d(2f 9), c03+ (3, 9)這是最后一個(gè)階段的決策，它依賴于d(l, 9). d9) 和(3, 9)的計(jì)算結(jié)果，而(1, 9)二min%十“ 9), 口打十(59)必2, 9) =minc24+d(4, 9), c25+7(5,9), c2,+rf(6, 9)rf(3

21、, 9) =min(t35+d(5, 9), c3fr+rf(9)再向前推導(dǎo)，有：d(6, 9)=minc67+rf(7, 9), c礎(chǔ)+d(8, 9)=min6+7, 5+3=8(68)d(59 9)=minc57+rf(7,9), csg+d(8,9)=min8+7, 6+3=9(5 8)rf(4, 9)=mine47+rf(7,鄉(xiāng)),c+rffS, 9)=min5+7, 6+3=9(48)rf(3, 9)=minq5+rf(5, 9), c36+J(6, 9)=min4+9, 7+8=13(3-5)rf(2,9), c2-+rf(5, 9), c26+d(6, 9)=min6+9, 7+

22、9,8+8=15(2-4)rf(l, 9)=minc14+rf(4, 9), cl5+rf(5, 9)=min9+9, 8+9=17(15)rf(O, 9)=minrftl+rf(l, 9), c”+d(2, 9),弘+rf(3, 9)=min4+17, 2+15,3+13=16(0-3)最后，得到最短路徑為03589?長(zhǎng)度為16。16六、參考文獻(xiàn)1 交通管理調(diào)度局城市車速分類統(tǒng)計(jì)， 20112 盛春行，張?jiān)?，基于貝葉斯網(wǎng)絡(luò)模型的交通狀態(tài)預(yù)測(cè) J ， 山東交通科技， 20093 韓中庚，數(shù)學(xué)建模競(jìng)賽 獲獎(jiǎng)?wù)撐木x與點(diǎn)評(píng) M ，北京 科學(xué)出版社，20074 齊峰，杜瀟芳，殷瑋，世博會(huì)交通需求分析

23、與交通策略淺議 J ，2006(7) 81-835 王亮，孟福榮，孫靜，深圳交通擁堵問題的研究， 2013.06.106 陳慧南，算法設(shè)計(jì)與分析 -c+ 語(yǔ)言描述(第二版)，電子工業(yè)出版社， 2012.7七、附錄，代碼附件 1Matlab:a=500 1000 3000 4500 6000;0.9 0.45 0.3 0.45 0.9; y=polyfit(a (1，：)， a(2,:),2);y=7.6615e-8 -0.000473328 1.00009 poly2str(y)ans=7.665e-8xA2-0.000047328x+1.00009附件 2c+：#include#includ

24、e#include#include#defineMAX 100#definen 12 /* 頂點(diǎn)數(shù) */#definek 5/* 段數(shù) */int cnn;void init(int cost) / 初始化圖int i,j;for(i=0;i13;i+) for(j=0;j13;j+) cij=MAX;c12=9;c13=7;c14=3; c15=2;c26=4; c27=2;c28=1; c36=2;c37=7; c48=11;c57=11; c58=8;c69=6; c610=5;c79=4; c710=3;c810=5; c811=6;c912=4; c1012=2;c1112=5;void fgraph(int cost,int path,int d) / 使用向前遞推算法求多段 圖的最短路