最短路徑問(wèn)題

數(shù)學(xué)建模講座主講人：王曉峰內(nèi)容1：數(shù)學(xué)建模及其競(jìng)賽2：中國(guó)大學(xué)生數(shù)學(xué)建模競(jìng)賽歷程3：建模過(guò)程與方法4：建模案例分析5：數(shù)學(xué)建模論文的撰寫(xiě)1.數(shù)學(xué)建模及其競(jìng)賽

——什么是數(shù)學(xué)建模數(shù)學(xué)建模是構(gòu)造刻劃客觀事物原型的數(shù)學(xué)模型并用以分析、研究和解決實(shí)際問(wèn)題的一種科學(xué)方法。運(yùn)用這種科學(xué)方法，必須從實(shí)際問(wèn)題出發(fā)，遵循從實(shí)踐到認(rèn)識(shí)再實(shí)踐的認(rèn)識(shí)規(guī)律，圍繞建模的目的，運(yùn)用觀察力、想象力的抽象概括能力，對(duì)實(shí)際問(wèn)題進(jìn)行抽象、簡(jiǎn)化，反復(fù)探索，逐步完善，直到構(gòu)造出一個(gè)能夠用于分析、研究和解決實(shí)際問(wèn)題的數(shù)學(xué)模型。因此，數(shù)學(xué)建模是一種定量解決實(shí)際問(wèn)題的創(chuàng)新過(guò)程。1.數(shù)學(xué)建模及其競(jìng)賽

——數(shù)學(xué)建模競(jìng)賽題目

數(shù)學(xué)建模競(jìng)賽的題目由日常生活、工程技術(shù)、經(jīng)濟(jì)管理、社會(huì)生活等領(lǐng)域中的實(shí)際問(wèn)題簡(jiǎn)化加工而成，它對(duì)數(shù)學(xué)知識(shí)要求不一定深，一般沒(méi)有事先設(shè)定的標(biāo)準(zhǔn)答案，但留有充分余地供參賽者發(fā)揮其聰明才智和創(chuàng)造精神。從下面一些題目的標(biāo)題可以看出其實(shí)用性和挑戰(zhàn)性：“DNA序列分類(lèi)”、“血管的三維重建”、“公交車(chē)調(diào)度”、“SARS的傳播”、“奧運(yùn)會(huì)臨時(shí)超市網(wǎng)點(diǎn)設(shè)計(jì)”、“長(zhǎng)江水質(zhì)的評(píng)價(jià)和預(yù)測(cè)”——1.數(shù)學(xué)建模及其競(jìng)賽

——數(shù)學(xué)建模競(jìng)賽題目1998A、投資的收益和風(fēng)險(xiǎn)；B、災(zāi)情巡視路線1999A、自動(dòng)化車(chē)床管理；B、鉆井布局2000A、DNA序列分類(lèi)；B、鋼管訂購(gòu)和運(yùn)輸；2001A、血管的三維重建；B、公交車(chē)調(diào)度；2002A、車(chē)燈線光源優(yōu)化設(shè)計(jì)；B、彩票中的數(shù)學(xué)；2003A、SARS的傳播；B、露天礦生產(chǎn)的車(chē)輛安排；2004A、奧運(yùn)會(huì)臨時(shí)超市網(wǎng)點(diǎn)設(shè)計(jì)；B、電力市場(chǎng)的輸電阻塞管理；2005A、長(zhǎng)江水質(zhì)的評(píng)價(jià)和預(yù)測(cè)；B、DVD在線租賃；2006A、出版社的資源配置；B、艾滋病療法的評(píng)價(jià)及療效的預(yù)測(cè)；A、國(guó)人口增長(zhǎng)預(yù)測(cè)；B、乘公交，看奧運(yùn)。

A、數(shù)碼相機(jī)定位;B、高等教育學(xué)費(fèi)標(biāo)準(zhǔn)探討A、制動(dòng)器試驗(yàn)臺(tái)的控制方法分析B、眼科病床的合理安排A、儲(chǔ)油罐的變位識(shí)別與罐容表標(biāo)定B、2010年上海世博會(huì)影響力的定量評(píng)估1.數(shù)學(xué)建模及其競(jìng)賽

——數(shù)學(xué)建模競(jìng)賽的形式

競(jìng)賽評(píng)獎(jiǎng)以假設(shè)的合理性、建模的創(chuàng)造性、結(jié)果的正確性和文字表述的清晰程度為主要標(biāo)準(zhǔn)?？梢钥闯?，這項(xiàng)競(jìng)賽從內(nèi)容到形式與傳統(tǒng)的數(shù)學(xué)競(jìng)賽不同，既豐富、活躍了廣大同學(xué)的課外生活，也為優(yōu)秀學(xué)生脫穎而出創(chuàng)造了條件。數(shù)學(xué)建模競(jìng)賽以通訊形式進(jìn)行。三名大學(xué)生組成一隊(duì)，可自由地收集資料、調(diào)查研究，使用計(jì)算機(jī)和任何軟件，甚至上網(wǎng)查詢(xún)，但不得與隊(duì)外任何人包括指導(dǎo)教師討論。時(shí)間：三天。要求每個(gè)隊(duì)完成一篇包括模型的假設(shè)、建立和求解，計(jì)算方法的設(shè)計(jì)和計(jì)算機(jī)實(shí)現(xiàn)，結(jié)果的分析和檢驗(yàn)，模型的改進(jìn)等方面的論文。1.數(shù)學(xué)建模及其競(jìng)賽

——數(shù)學(xué)建模競(jìng)賽的特點(diǎn)競(jìng)賽讓同學(xué)們面對(duì)一個(gè)從未接觸過(guò)的實(shí)際問(wèn)題，運(yùn)用數(shù)學(xué)方法和計(jì)算機(jī)技術(shù)加以分析、解決，他們必須開(kāi)動(dòng)腦筋、拓寬思路，充分發(fā)揮創(chuàng)造力和想象力，培養(yǎng)同學(xué)們創(chuàng)新意識(shí)及主動(dòng)學(xué)習(xí)、獨(dú)立研究的能力。競(jìng)賽緊密結(jié)合社會(huì)熱點(diǎn)問(wèn)題，富有挑戰(zhàn)性，吸引著學(xué)生關(guān)心、投身國(guó)家的各項(xiàng)建設(shè)事業(yè)，培養(yǎng)他們理論聯(lián)系實(shí)際的學(xué)風(fēng)。競(jìng)賽需要學(xué)生在很短時(shí)間內(nèi)獲取與賽題有關(guān)的知識(shí)，鍛煉同學(xué)們收集資料的能力，提高撰寫(xiě)科技論文的文字表達(dá)水平。競(jìng)賽要三個(gè)同學(xué)共同完成一篇論文，在競(jìng)賽中要分工合作、取長(zhǎng)補(bǔ)短、求同存異，既有相互啟發(fā)，也有相互爭(zhēng)論，培養(yǎng)了學(xué)生們同舟共濟(jì)的團(tuán)隊(duì)精神和進(jìn)行協(xié)調(diào)的組織能力。競(jìng)賽是開(kāi)放型的，三天中沒(méi)有或者很少有外部的強(qiáng)制約束，同學(xué)們要自覺(jué)地遵守競(jìng)賽紀(jì)律，公平地開(kāi)展競(jìng)爭(zhēng)。誠(chéng)信意識(shí)和自律精神是建設(shè)和諧社會(huì)的基本要素之一，同學(xué)們能在競(jìng)賽中得到這種品格鍛煉對(duì)他們的一生是非常有益的。

內(nèi)容1：數(shù)學(xué)建模及其競(jìng)賽2：中國(guó)大學(xué)生數(shù)學(xué)建模競(jìng)賽歷程3：建模過(guò)程與方法3：建模案例分析4：數(shù)學(xué)建模論文的撰寫(xiě)中國(guó)大學(xué)生數(shù)學(xué)建模競(jìng)賽歷程（1）

1988.6大學(xué)生數(shù)學(xué)建模競(jìng)賽最早是1985年在美國(guó)出現(xiàn)的，葉其孝教授在美國(guó)講學(xué)期間向美國(guó)大學(xué)生數(shù)學(xué)建模競(jìng)賽發(fā)起者和負(fù)責(zé)人Fusaro教授了解這項(xiàng)競(jìng)賽的情況，商討中國(guó)學(xué)生參賽的辦法和規(guī)則。1989.2.24～26

我國(guó)大學(xué)生（北京大學(xué)、清華大學(xué)、北京理工大學(xué)共4個(gè)隊(duì)）首次參加美國(guó)大學(xué)生數(shù)學(xué)建模競(jìng)賽，自此每年我國(guó)都有同學(xué)參加這項(xiàng)競(jìng)賽。中國(guó)大學(xué)生數(shù)學(xué)建模競(jìng)賽歷程（2）1989.3《高校應(yīng)用數(shù)學(xué)學(xué)報(bào)》第4卷第1期發(fā)表葉其孝教授的文章“美國(guó)大學(xué)生數(shù)學(xué)建模競(jìng)賽及一些想法”，第一次向國(guó)內(nèi)介紹這項(xiàng)競(jìng)賽。1990.12.7～9上海市舉辦大學(xué)生（數(shù)學(xué)類(lèi)）數(shù)學(xué)模型競(jìng)賽，這是我國(guó)省、市級(jí)首次舉辦數(shù)學(xué)建模競(jìng)賽。中國(guó)大學(xué)生數(shù)學(xué)建模競(jìng)賽歷程（3）1992.11.27～291992年部分城市大學(xué)生數(shù)學(xué)模型聯(lián)賽舉行，這是全國(guó)性的首屆競(jìng)賽，10?。ㄊ校?9所院校的314隊(duì)參加。1993.10.15～171993年全國(guó)大學(xué)生數(shù)學(xué)建模競(jìng)賽舉行，16省（市）101所院校的420隊(duì)參加。中國(guó)大學(xué)生數(shù)學(xué)建模競(jìng)賽歷程（4）1994.10.28～301994年全國(guó)大學(xué)生數(shù)學(xué)建模競(jìng)賽舉行，21省（市、自治區(qū)）196所院校的870隊(duì)參加。內(nèi)容1：數(shù)學(xué)建模及其競(jìng)賽2：中國(guó)大學(xué)生數(shù)學(xué)建模競(jìng)賽歷程3：建模過(guò)程與方法4：建模案例分析5：數(shù)學(xué)建模論文的撰寫(xiě)3.建模過(guò)程簡(jiǎn)介

----什么是數(shù)學(xué)建模

把現(xiàn)實(shí)世界中的實(shí)際問(wèn)題加以提煉，抽象為數(shù)學(xué)模型，求出模型的解，驗(yàn)證模型的合理性，并用該數(shù)學(xué)模型所提供的解答來(lái)解釋現(xiàn)實(shí)問(wèn)題，我們把數(shù)學(xué)知識(shí)的這一應(yīng)用過(guò)程稱(chēng)為數(shù)學(xué)建模。3.建模過(guò)程簡(jiǎn)介

----數(shù)學(xué)建模的幾個(gè)過(guò)程（1）模型準(zhǔn)備（2）模型假設(shè)（3）模型建立（4）模型構(gòu)成（5）模型求解（6）模型分析（7）模型檢驗(yàn)（8）模型應(yīng)用

（1）模型準(zhǔn)備

了解問(wèn)題的實(shí)際背景，明確其實(shí)際意義與建模目的，掌握對(duì)象的各種信息（要收集）。用數(shù)學(xué)語(yǔ)言來(lái)描述問(wèn)題。（2）模型假設(shè)

根據(jù)實(shí)際對(duì)象的特征和建模的目的，對(duì)問(wèn)題進(jìn)行必要的、合理的簡(jiǎn)化，并用精確的語(yǔ)言提出一些恰當(dāng)?shù)募僭O(shè)，是建模至關(guān)重要的一步。如果對(duì)問(wèn)題的所有因素一概考慮，是不現(xiàn)實(shí)的，所以高超的建模者能充分發(fā)揮想象力、洞察力和判斷力，善于辨別主次，而且為了使處理方法簡(jiǎn)單，應(yīng)盡量使問(wèn)題線性化、均勻化。

（3）模型建立

在假設(shè)的基礎(chǔ)上，利用適當(dāng)?shù)臄?shù)學(xué)工具來(lái)刻劃各變量之間的數(shù)學(xué)關(guān)系，建立相應(yīng)的數(shù)學(xué)結(jié)構(gòu)。（盡量用簡(jiǎn)單的數(shù)學(xué)工具）（4）模型構(gòu)成

根據(jù)所作的假設(shè)分析對(duì)象的因果關(guān)系，利用對(duì)象的內(nèi)在規(guī)律和適當(dāng)?shù)臄?shù)學(xué)工具，構(gòu)造各個(gè)量間的等式關(guān)系或其它數(shù)學(xué)結(jié)構(gòu)。有高數(shù)、概率統(tǒng)計(jì)、圖論、排隊(duì)論、線性規(guī)劃、對(duì)策論等等。提示：建立數(shù)學(xué)模型是為了讓更多的人明了并能加以應(yīng)用，因此工具愈簡(jiǎn)單愈有價(jià)值。

（5）模型求解

利用獲取的數(shù)據(jù)資料，對(duì)模型的所有參數(shù)做出計(jì)算（估計(jì)）。可以采用解方程、畫(huà)圖形、證明定理、邏輯運(yùn)算、數(shù)值運(yùn)算等各種傳統(tǒng)的和近代的數(shù)學(xué)方法，特別是計(jì)算機(jī)技術(shù)。實(shí)際問(wèn)題的解決往往需要紛繁的計(jì)算，許多時(shí)候還得將系統(tǒng)運(yùn)行情況用計(jì)算機(jī)模擬出來(lái)，因此編程和熟悉數(shù)學(xué)軟件的能力非常重要。（6）模型檢驗(yàn)

將模型分析結(jié)果與實(shí)際情形進(jìn)行比較，以此來(lái)驗(yàn)證模型的準(zhǔn)確性、合理性和適用性。如果模型與實(shí)際較吻合，則要對(duì)計(jì)算結(jié)果給出其實(shí)際含義，并進(jìn)行解釋。如果模型與實(shí)際吻合較差,則應(yīng)該修改假設(shè)，在次重復(fù)建模過(guò)程。3.建模過(guò)程與方法

----建模全過(guò)程示意圖3.建模過(guò)程與方法

----具備的數(shù)學(xué)知識(shí)1、數(shù)學(xué)分析2、高等代數(shù)3、概率與數(shù)理統(tǒng)計(jì)4、最優(yōu)化理論5、圖論6、組合數(shù)學(xué)7、微分方程穩(wěn)定性分析8、排隊(duì)論3.建模過(guò)程與方法

----具備的應(yīng)用軟件知識(shí)1、綜合類(lèi)：Matlab,Mathematic2、統(tǒng)計(jì)類(lèi)：Spss,SAS,Statistics3、最優(yōu)解：Lindo,Lingo3.建模過(guò)程與方法

----圖論方法最短路問(wèn)題兩個(gè)指定頂點(diǎn)之間的最短路徑—給出了一個(gè)連接若干個(gè)城鎮(zhèn)的鐵路網(wǎng)絡(luò)，在這個(gè)網(wǎng)絡(luò)的兩個(gè)指定城鎮(zhèn)間，找一條最短鐵路線（Dijkstra算法）每對(duì)頂點(diǎn)之間的最短路徑（Dijkstra算法、Floyd算法）最小生成樹(shù)問(wèn)題連線問(wèn)題—欲修筑連接多個(gè)城市的鐵路設(shè)計(jì)一個(gè)線路圖，使總造價(jià)最低（prim算法、Kruskal算法）圖的匹配問(wèn)題人員分派問(wèn)題：n個(gè)工作人員去做件n份工作，每人適合做其中一件或幾件，問(wèn)能否每人都有一份適合的工作？如果不能，最多幾人可以有適合的工作？(匈牙利算法)遍歷性問(wèn)題中國(guó)郵遞員問(wèn)題—郵遞員發(fā)送郵件時(shí)，要從郵局出發(fā)，經(jīng)過(guò)他投遞范圍內(nèi)的每條街道至少一次，然后返回郵局，但郵遞員希望選擇一條行程最短的路線最大流問(wèn)題運(yùn)輸問(wèn)題最小費(fèi)用最大流問(wèn)題在運(yùn)輸問(wèn)題中，人們總是希望在完成運(yùn)輸任務(wù)的同時(shí)，尋求一個(gè)使總的運(yùn)輸費(fèi)用最小的運(yùn)輸方案3.建模過(guò)程與方法

----圖論方法（1）基本概念（2）固定起點(diǎn)的最短路（3）每對(duì)頂點(diǎn)之間的最短路3.建模過(guò)程與方法

----最短路問(wèn)題基本概念固定起點(diǎn)的最短路

從甲地到乙地之間是否有公路連通?在有多條通路的情況下，哪一條路最短?交通網(wǎng)絡(luò)可用帶權(quán)圖來(lái)表示。頂點(diǎn)表示城市名稱(chēng)，邊表示兩個(gè)城市有路連通，邊上的權(quán)值可表示兩城市之間的距離、交通費(fèi)或途中所花費(fèi)的時(shí)間等。求兩個(gè)頂點(diǎn)之間的最短路徑，不是指路徑上邊數(shù)之和最少，而是指路徑上各邊的權(quán)值之和最小。另外，若兩個(gè)頂點(diǎn)之間沒(méi)有邊，則認(rèn)為兩個(gè)頂點(diǎn)無(wú)通路，但有可能有間接通路(從其它頂點(diǎn)達(dá)到)。路徑上的開(kāi)始頂點(diǎn)(出發(fā)點(diǎn))稱(chēng)為源點(diǎn)，路徑上的最后一個(gè)頂點(diǎn)稱(chēng)為終點(diǎn)，并假定討論的權(quán)值不能為負(fù)數(shù)。從一個(gè)頂點(diǎn)到其余各頂點(diǎn)的最短路徑

問(wèn)題：給定一個(gè)帶權(quán)有向圖G與源點(diǎn)v,求從v到G中其他頂點(diǎn)的最短路徑,并限定各邊上的權(quán)值大于或等于0。

采用狄克斯特拉(Dijkstra)算法求解基本思想是：設(shè)G=(V,E)是一個(gè)帶權(quán)有向圖,把圖中頂點(diǎn)集合V分成兩組：第一組為已求出最短路徑的頂點(diǎn)集合(用S表示,初始時(shí)S中只有一個(gè)源點(diǎn),以后每求得一條最短路徑v,…vk,就將vk加入到集合S中,直到全部頂點(diǎn)都加入到S中,算法就結(jié)束了)第二組為其余未確定最短路徑的頂點(diǎn)集合(用U表示)。按最短路徑長(zhǎng)度的遞增次序依次把第二組的頂點(diǎn)加入S中。在加入的過(guò)程中,總保持從源點(diǎn)v到S中各頂點(diǎn)的最短路徑長(zhǎng)度不大于從源點(diǎn)v到U中任何頂點(diǎn)的最短路徑長(zhǎng)度。此外,每個(gè)頂點(diǎn)對(duì)應(yīng)一個(gè)距離,S中的頂點(diǎn)的距離就是從v到此頂點(diǎn)的最短路徑長(zhǎng)度,U中的頂點(diǎn)的距離從v到此頂點(diǎn)只包括S中的頂點(diǎn)為中間頂點(diǎn)的當(dāng)前最短路徑長(zhǎng)度。狄克斯特拉算法的具體步驟如下：(1)初始時(shí),S只包含源點(diǎn),即S={v},v的距離為0。U包含除v外的其他頂點(diǎn),U中頂點(diǎn)u距離為邊上的權(quán)(若v與u有邊<v,u>)或∞(若u不是v的出邊鄰接點(diǎn))。(2)從U中選取一個(gè)距離v最小的頂點(diǎn)k,把k加入S中(該選定的距離就是v到k的最短路徑長(zhǎng)度)。(3)以k為新考慮的中間點(diǎn),修改U中各頂點(diǎn)的距離：若從源點(diǎn)v到頂點(diǎn)u(u∈U)的距離(經(jīng)過(guò)頂點(diǎn)k)比原來(lái)距離(不經(jīng)過(guò)頂點(diǎn)k)短,則修改頂點(diǎn)u的距離值,修改后的距離值的頂點(diǎn)k的距離加上邊<k,u>上的權(quán)。(4)重復(fù)步驟(2)和(3)直到所有頂點(diǎn)都包含在S中。S U v0到0～6各頂點(diǎn)的距離{0} {1,2,3,4,5,6}{0,4,6,6,∞,∞,∞}{0,1}{2,3,4,5,6}

{0,4,5,6,11,∞,∞}{0,1,2}{3,4,5,6} {0,4,5,6,11,9,∞}{0,1,2,3}{4,5,6} {0,4,5,6,11,9,19}{0,1,2,3,5}{4,6} {0,4,5,6,10,9,17}{0,1,2,3,5,4} {6} {0,4,5,6,10,9,16}{0,1,2,3,5,4,6}{} {0,4,5,6,10,9,16}則v0到v1～v6各頂點(diǎn)的最短距離分別為4、5、6、10、9和16。狄克斯特拉算法如下(n為圖G的頂點(diǎn)數(shù),v0為源點(diǎn)編號(hào))：voidDijkstra(intcost[][MAXV],intn,intv0){intdist[MAXV],path[MAXV];ints[MAXV];intmindis,i,j,u;for(i=0;i<n;i++){dist[i]=cost[v0][i]; /*距離初始化*/ s[i]=0; /*s[]置空*/ if(cost[v0][i]<INF) /*路徑初始化*/ path[i]=v0; else path[i]=-1; } s[v0]=1;path[v0]=0; /*源點(diǎn)編號(hào)v0放入s中*/

for(i=0;i<n;i++)/*循環(huán)直到所有頂點(diǎn)的最短路徑都求出*/{mindis=INF; u=-1; for(j=0;j<n;j++)/*選取不在s中且具有最小距離的頂點(diǎn)u*/ if(s[j]==0&&dist[j]<mindis) {u=j;mindis=dist[j]; } s[u]=1; /*頂點(diǎn)u加入s中*/ for(j=0;j<n;j++)/*修改不在s中的頂點(diǎn)的距離*/ if(s[j]==0) if(cost[u][j]<INF&&dist[u]+cost[u][j]<dist[j]) {dist[j]=dist[u]+cost[u][j];path[j]=u;}}Dispath(dist,path,s,n,v0); /*輸出最短路徑*/}voidPpath(intpath[],inti,intv0)/*前向遞歸查找路徑上的頂點(diǎn)*/{intk;k=path[i];if(k==v0)return; /*找到了起點(diǎn)則返回*/Ppath(path,k,v0); /*找k頂點(diǎn)的前一個(gè)頂點(diǎn)*/printf("%d,",k); /*輸出k頂點(diǎn)*/}voidDispath(intdist[],intpath[],ints[],intn,intv0){inti;for(i=0;i<n;i++) if(s[i]==1) {printf(“從%d到%d的最短路徑長(zhǎng)度為:%d\t路徑為:",v0,i,dist[i]); printf("%d,",v0); /*輸出路徑上的起點(diǎn)*/Ppath(path,i,v0); /*輸出路徑上的中間點(diǎn)*/printf("%d\n",i); /*輸出路徑上的終點(diǎn)*/ } elseprintf("從%d到%d不存在路徑\n",v0,i);}每對(duì)頂點(diǎn)之間的最短路徑

問(wèn)題：對(duì)于一個(gè)各邊權(quán)值均大于零的有向圖,對(duì)每一對(duì)頂點(diǎn)vi≠vj,求出vi與vj之間的最短路徑和最短路徑長(zhǎng)度。

可以通過(guò)以每個(gè)頂點(diǎn)作為源點(diǎn)循環(huán)求出每對(duì)頂點(diǎn)之間的最短路徑。除此之外,弗洛伊德(Floyd)算法也可用于求兩頂點(diǎn)之間最短路徑。

假設(shè)有向圖G=(V,E)采用鄰接矩陣cost存儲(chǔ),另外設(shè)置一個(gè)二維數(shù)組A用于存放當(dāng)前頂點(diǎn)之間的最短路徑長(zhǎng)度,分量A[i][j]表示當(dāng)前頂點(diǎn)vi到頂點(diǎn)vj的最短路徑長(zhǎng)度。弗洛伊德算法的基本思想是遞推產(chǎn)生一個(gè)矩陣序列A0,A1,…,Ak,…,An,其中Ak[i][j]表示從頂點(diǎn)vi到頂點(diǎn)vj的路徑上所經(jīng)過(guò)的頂點(diǎn)編號(hào)不大于k的最短路徑長(zhǎng)度。

初始時(shí),有A-1[i][j]=cost[i][j]。當(dāng)求從頂點(diǎn)vi到頂點(diǎn)vj的路徑上所經(jīng)過(guò)的頂點(diǎn)編號(hào)不大于k+1的最短路徑長(zhǎng)度時(shí),要分兩種情況考慮：一種情況是該路徑不經(jīng)過(guò)頂點(diǎn)編號(hào)為k+1的頂點(diǎn),此時(shí)該路徑長(zhǎng)度與從頂點(diǎn)vi到頂點(diǎn)vj的路徑上所經(jīng)過(guò)的頂點(diǎn)編號(hào)不大于k的最短路徑長(zhǎng)度相同；另一種情況是從頂點(diǎn)vi到頂點(diǎn)vj的最短路徑上經(jīng)過(guò)編號(hào)為k+1的頂點(diǎn)。那么,該路徑可分為兩段,一段是從頂點(diǎn)vi到頂點(diǎn)vk+1的最短路徑,另一段是從頂點(diǎn)vk+1到頂點(diǎn)vj的最短路徑,此時(shí)最短路徑長(zhǎng)度等于這兩段路徑長(zhǎng)度之和。這兩種情況中的較小值,就是所要求的從頂點(diǎn)vi到頂點(diǎn)vj的路徑上所經(jīng)過(guò)的頂點(diǎn)編號(hào)不大于k+1的最短路徑。

弗洛伊德思想可用如下的表達(dá)式來(lái)描述：A-1[i][j]=cost[i][j]Ak+1[i][j]=min{Ak[i][j],Ak[i][k+1]+Ak[k+1][j]}(0≤k≤n-1)

采用弗洛伊德算法求解過(guò)程

考慮頂點(diǎn)v0,A0[i][j]表示由vi到vj,經(jīng)由頂點(diǎn)v0的最短路徑。只有從v2到v1經(jīng)過(guò)v0的路徑和從v2到v3經(jīng)過(guò)v0的路徑,不影響v2到v1和v2到v3的路徑長(zhǎng)度,因此,有：

考慮頂點(diǎn)v1,A1[i][j]表示由vi到vj,經(jīng)由頂點(diǎn)v1的最短路徑。存在路徑v0-v1-v2,路徑長(zhǎng)度為9,將A[0][2]改為9,path[0][2]改為1,因此,有：

考慮頂點(diǎn)v2,A2[i][j]表示由vi到vj,經(jīng)由頂點(diǎn)v2的最短路徑。存在路徑v3-v2-v0,長(zhǎng)度為4,將A[3][0]改為4；存在路徑v3-v2-v1,長(zhǎng)度為4,將A[3][1]改為4。存在路徑v1-v2-v0,長(zhǎng)度為7,將A[1][0]改為7。將path[3][0]、path[3][1]和path[1][0]均改為2。因此,有：

考慮頂點(diǎn)v3,A3[i][j]表示由vi到vj,經(jīng)由頂點(diǎn)v3的最短路徑。存在路徑v0-v3-v2,長(zhǎng)度為8比原長(zhǎng)度短,將A[0][2]改為8；存在路徑v1-v3-v2-v0,長(zhǎng)度為6(A[1][3]+A[3][0]=2+4=6)比原長(zhǎng)度短,將A[1][0]改為6；存在路徑v1-v3-v2,長(zhǎng)度為3,比原長(zhǎng)度短,將A[1][2]改為3；將path[0][2]、path[1][0]后path[1][2]均改為3。因此,有：

因此,最后求得的各頂點(diǎn)最短路徑長(zhǎng)度A和Path矩陣為：

從0到0路徑為：0,0 路徑長(zhǎng)度為：0從0到1路徑為：0,1 路徑長(zhǎng)度為：5從0到2路徑為：0,3,2 路徑長(zhǎng)度為：8從0到3路徑為：0,3 路徑長(zhǎng)度為：7從1到0路徑為：1,3,2,0 路徑長(zhǎng)度為：6從1到1路徑為：1,1 路徑長(zhǎng)度為：0從1到2路徑為：1,3,2 路徑長(zhǎng)度為：3從1到3路徑為：1,3 路徑長(zhǎng)度為：2從2到0路徑為：2,0 路徑長(zhǎng)度為：3從2到1路徑為：2,1 路徑長(zhǎng)度為：3從2到2路徑為：2,2 路徑長(zhǎng)度為：0從2到3路徑為：2,3 路徑長(zhǎng)度為：2從3到0路徑為：3,2,0 路徑長(zhǎng)度為：4從3到1路徑為：3,2,1 路徑長(zhǎng)度為：4從3到2路徑為：3,2 路徑長(zhǎng)度為：1從3到3路徑為：3,3 路徑長(zhǎng)度為：0弗洛伊德算法如下：voidFloyd(intcost[][MAXV],intn){intA[MAXV][MAXV],path[MAXV][MAXV];inti,j,k;for(i=0;i<n;i++) for(j=0;j<n;j++){A[i][j]=cost[i][j]; path[i][j]=-1;}for(k=0;k<n;k++) for(i=0;i<n;i++) for(j=0;j<n;j++) if(A[i][j]>(A[i][k]+A[k][j])){A[i][j]=A[i][k]+A[k][j];path[i][j]=k;}Dispath(A,path,n);/*輸出最短路徑*/}樹(shù)的定義和基本術(shù)語(yǔ)

1、樹(shù)的定義

樹(shù)是由n（n≥0）個(gè)結(jié)點(diǎn)組成的有限集合。若n=0，稱(chēng)為空樹(shù)；若n>0，則：

（1）有且僅有一個(gè)特定的稱(chēng)為根（root）的結(jié)點(diǎn)。它只有直接后繼，但沒(méi)有直接前驅(qū)；

（2）除根結(jié)點(diǎn)以外的其它結(jié)點(diǎn)可以劃分為m（m≥0）個(gè)互不相交的有限集合T0，T1，…，Tm-1，每個(gè)集合Ti（i=0,1,…,m-1）又是一棵樹(shù)，稱(chēng)為根的子樹(shù)，每棵子樹(shù)的根結(jié)點(diǎn)有且僅有一個(gè)直接前驅(qū)，但可以有0個(gè)或多個(gè)直接后繼。

由此可知，樹(shù)的定義是一個(gè)遞歸的定義，即樹(shù)的定義中又用到了樹(shù)的概念。

樹(shù)的結(jié)構(gòu)參見(jiàn)圖6-1。

3.建模過(guò)程與方法-最小生成樹(shù)問(wèn)題

一、最小生成樹(shù)（MST）概念1.設(shè)無(wú)向連通圖G=（V，{E}），其子圖G’=（V，{T}）滿(mǎn)足：①V(G’)=V(G)n個(gè)頂點(diǎn)②G’是連通的③G’中無(wú)回路則G’是G的生成樹(shù)2.最小生成樹(shù)：一個(gè)有n個(gè)結(jié)點(diǎn)的連通圖的生成樹(shù)是原圖的極小連通子圖，且包含原圖中的所有n個(gè)結(jié)點(diǎn)，并且有保持圖聯(lián)通的最少的邊。3.建模過(guò)程與方法-最小生成樹(shù)問(wèn)題

具有n個(gè)頂點(diǎn)的無(wú)向連通圖G

其任一生成樹(shù)恰好含n-1條邊

生成樹(shù)不一定唯一，如深度優(yōu)先搜索生成樹(shù)和廣度優(yōu)先搜索生成樹(shù)。4.生成樹(shù)代價(jià):對(duì)圖中每條邊賦于一個(gè)權(quán)值（代價(jià)），則構(gòu)成一個(gè)網(wǎng)，網(wǎng)的生成樹(shù)G’=(V，{T})的代價(jià)是T中各邊的權(quán)值之和，最小生成樹(shù)就是網(wǎng)上所有可能的生成樹(shù)中，代價(jià)最小的一類(lèi)生成樹(shù)。最小生成樹(shù)也不一定唯一。5.求MST的一般算法可描述為：針對(duì)圖G，從空樹(shù)T開(kāi)始，往集合T中逐條選擇并加入n-1條安全邊(u，v)，最終生成一棵含n-1條邊的MST。當(dāng)一條邊(u，v)加入T時(shí)，必須保證T∪{(u，v)}仍是MST的子集，我們將這樣的邊稱(chēng)為T(mén)的安全邊。

3.最小生成樹(shù)性質(zhì)：設(shè)G=(V，E)是一個(gè)連通網(wǎng)絡(luò)，U是頂點(diǎn)集V的一個(gè)真子集。若(u，v)是G中一條“一個(gè)端點(diǎn)在U中(例如：u∈U)，另一個(gè)端點(diǎn)不在U中的邊(例如：v∈V-U)，且(u，v)具有最小權(quán)值，則一定存在G的一棵最小生成樹(shù)包括此邊(u，v)。許多應(yīng)用問(wèn)題都是求無(wú)向連通圖的最小生成樹(shù)問(wèn)題。例1：要在n個(gè)城市之間鋪設(shè)光纜，主要目標(biāo)是要使這n個(gè)城市的任意兩個(gè)之間都可以通信，但鋪設(shè)光纜的費(fèi)用很高，且各個(gè)城市之間鋪設(shè)光纜的費(fèi)用不同；另一個(gè)目標(biāo)是要使鋪設(shè)光纜的總費(fèi)用最低。這就需要找到帶權(quán)的最小生成樹(shù)。

例2：N臺(tái)計(jì)算機(jī)之間建立通訊網(wǎng)頂點(diǎn)表示computer邊表示通訊線權(quán)值表示通訊線的代價(jià)（通訊線長(zhǎng)度，computer間距離等）要求：①n臺(tái)計(jì)算機(jī)中的任何兩臺(tái)能通過(guò)網(wǎng)進(jìn)行通訊；②使總的代價(jià)最小。-------求最小生成樹(shù)[T]

最小生成樹(shù)的實(shí)用例子例3：郵遞員送信線路[T]頂點(diǎn)表示投遞點(diǎn)邊表示街道權(quán)值表示街道的長(zhǎng)度要求：①完成n個(gè)投遞點(diǎn)的投遞；②使總路徑長(zhǎng)度最短,即求最小生成樹(shù)[T]設(shè)N=（V，{E}）是一個(gè)連通網(wǎng)，V=[1，2，…，n}是N的頂點(diǎn)集合，輔助集合U，初值為{Uo}，用來(lái)存放當(dāng)前所得到的最小生成樹(shù)的頂點(diǎn)；輔助集合TE，初值為Ф，用來(lái)存放當(dāng)前所得到的最小生成樹(shù)的邊。1）普里姆（Prim）算法Prim算法步驟1.TE=Ф,U={u0}2.當(dāng)U≠V，重復(fù)下列步驟：(1)選?。╱0,v0)=min{cost(u,v)|u∈U,v∈V-U}，保證不形成回路(2)TE=TE+（u0,v0),邊（u0,v0)并入TE(3)U=U+{V0}，頂點(diǎn)V0并入U(xiǎn)初始化：①②①④⑤

521③3466556⑥

①1③第1步：6①1③4第2步：④6①1③42第3步：5②④6①1③42第4步：23⑤

②5④6①1③4第5步：特點(diǎn):以連通為主選代價(jià)最小的鄰接邊Prim算法的實(shí)現(xiàn)voidgraph::mintree(charu){ for(intk=0;k<vexnum;k++) if(vexs[k]==u) break; for(intj=0;j<vexnum;j++) if(j!=k) { closedge[j].index=k; closedge[j].lowcost=arcs[k][j]; }//給結(jié)構(gòu)體數(shù)組賦值 closedge[k].lowcost=0;//初始化 for(inti=1;i<vexnum;i++) {//找到與頂點(diǎn)u相鄰的權(quán)值最小的 intk=closedge[0].lowcost; for(intx=0;x<vexnum;x++)

（鄰接矩陣存儲(chǔ)）if(closedge[x].lowcost<k) k=closedge[x].lowcost; cout<<"("<<vexs[closedge[k].index]<<","<<vexs[k]<<")"; closedge[k].lowcost=0;//第k頂點(diǎn)并入U(xiǎn)集合 for(j=0;j<vexnum;j++) if(arcs[k][j]<closedge[j].lowcost) { closedge[j].index=vexs[k]; closedge[j].lowcost=arcs[k][j]; }}//新的頂點(diǎn)并入U(xiǎn)后，從新調(diào)整輔助數(shù)組}2）克魯斯卡爾（Kruskal）算法Kruskal算法是逐步給生成樹(shù)T中添加不和T中的邊構(gòu)成回路的當(dāng)前最小代價(jià)邊。特點(diǎn):以最小代價(jià)邊主。設(shè)N=（V，{E}）是個(gè)連通網(wǎng),算法步驟為：1.置生成樹(shù)T的初始狀態(tài)為T(mén)=（V，{Ф}）2.當(dāng)T中邊數(shù)<n-1時(shí),重復(fù)下列步驟:

從E中選取代價(jià)最小的邊（v,u）,并刪除之;

若（v,u）依附的頂點(diǎn)v和u落在T中不同的連同分量上，則將邊（v,u）并入到T的邊集中；否則，舍去該邊，選擇下一條代價(jià)最小的邊.步驟(v,u)ET②①④⑤

③⑥

②①④⑤

③⑥

1(1,3)0②①④⑤

52③3466556⑥

②①④⑤

5③3466556⑥

21步驟(v,u)ET5(1,4)4(3,6)②①④⑤

5③66556⑥

②①④⑤

③66556⑥

②①④⑤

③⑥

②①④⑤

③⑥

步驟(v,u)ET6(2,3)②①④⑤

③6656⑥

邊數(shù)=n-1=5代價(jià)=(1+2+3+4+5)=15②①④⑤

③⑥

123453.建模過(guò)程與方法

----圖的匹配問(wèn)題實(shí)例一：握手的次數(shù)史密斯先生和他太太邀請(qǐng)四對(duì)夫妻參加晚會(huì)。每個(gè)人到的時(shí)候，房間里的一些人都要與別的一些人握手。當(dāng)然，每個(gè)人都不會(huì)與自己的配偶握手，也不會(huì)跟同一個(gè)人握手兩次。之后，史密斯先生問(wèn)每個(gè)人和別人握了幾次手，他們的答案都不一樣。那么，史密斯太太和別人握了幾次手呢?這個(gè)問(wèn)題具有挑戰(zhàn)性的原因是因?yàn)樗鼪](méi)有一個(gè)明顯的起始點(diǎn)，但如果對(duì)此建立一個(gè)圖模型，問(wèn)題就變得很簡(jiǎn)單了。

分析：從題目我們得到了哪些信息?史密斯和太太邀請(qǐng)四對(duì)夫妻參加晚會(huì)--房間里共有10人。每個(gè)人都不會(huì)與自己的配偶握手--握手的兩個(gè)人不是配偶。每個(gè)人都不會(huì)跟同一人握手兩次--兩個(gè)人間的握手最多是一次。史密斯先生問(wèn)每個(gè)人和別人握了幾次手，他們的答案都不一樣--除史密斯先生外，每個(gè)人和別人握手的次數(shù)都不一樣。除史密斯先生外，每人握手的次數(shù)最多是8次，最少為0次。房間里除了史密斯先生外的9個(gè)人，他們與別人握手的次數(shù)分別為0，1，2，3，4，5，6，7，8次。要知道史密斯太太和別人握手的次數(shù)，只需確定除史密斯先生外的9人中哪一個(gè)是史密斯太太即可。根據(jù)以上信息，建立圖模型

0-8號(hào)分別代表握手次數(shù)為0-8次的9個(gè)人（史密斯先生除外）。

8號(hào)握手8次，則其配偶肯定是0號(hào)；以此類(lèi)推，7號(hào)的配偶是1號(hào)，6號(hào)的配偶是2號(hào)，5號(hào)的配偶是3號(hào)。所以，史密斯夫人是4號(hào)，即史密斯夫人握手次數(shù)為4次。由圖可知：8號(hào)的配偶是0號(hào)；7號(hào)的配偶是1號(hào)；6號(hào)的配偶是2號(hào)；5號(hào)的配偶是3號(hào)；史密斯太太是4號(hào)，所以史密斯太太和別人握了4次手。實(shí)例二：商人安全過(guò)河問(wèn)題

三名商人各帶一個(gè)隨從乘船渡河，現(xiàn)有一只小船只能容納兩個(gè)人，由他們自己劃行，隨從們密約，在河的任一岸，一旦隨從的人數(shù)比商人多，就殺人越貨。但如何乘船渡河由商人決定，試給出一個(gè)商人安全渡河的方案。問(wèn)題分析多步?jīng)Q策過(guò)程決策：每一步(此岸到彼岸或彼岸到此岸)船上的人員。要求：在安全的前提下(兩岸的隨從數(shù)不比商人多),經(jīng)有限步使全體人員過(guò)河。商人仆人k為奇數(shù)k為偶數(shù)此岸彼岸建模商人仆人設(shè)k次渡河前此岸的商人數(shù)為xk，隨從數(shù)為yk，則xk，yk=0，1，2，3定義狀態(tài)向量Sk=(xk,yk)定義決策：第k次渡船上的商人數(shù)為uk，隨從數(shù)為vk，則d=(uk,vk)允許決策集合：D={(u,v)|1u+v2,u,v=0,1,2}k為奇數(shù)k為偶數(shù)此岸彼岸狀態(tài)轉(zhuǎn)移規(guī)律：模型構(gòu)成xk~第k次渡河前此岸的商人數(shù)yk~第k次渡河前此岸的隨從數(shù)xk,yk=0,1,2,3;

k=1,2,sk=(xk,yk)~過(guò)程的狀態(tài)S={(x

,y)x=0,y=0,1,2,3;x=3,y=0,1,2,3;x=y=1,2}S~允許狀態(tài)集合uk~第k次渡船上的商人數(shù)vk~第k次渡船上的隨從數(shù)dk=(uk,vk)~決策uk,vk=0,1,2;k=1,2,sk+1=sk

dk+(-1)k~狀態(tài)轉(zhuǎn)移律求dkD(k=1,2,n),使skS,并按轉(zhuǎn)移律由s1=(3,3)到達(dá)sn+1=(0,0).多步?jīng)Q策問(wèn)題模型求解xy3322110窮舉法~編程上機(jī)圖解法狀態(tài)s=(x,y)~16個(gè)格點(diǎn)~10個(gè)點(diǎn)允許決策~移動(dòng)1或2格;k奇,左下移;k偶,右上移.s1sn+1d1,，d11給出安全渡河方案考慮4名商人各帶一隨從的情況d1d11允許狀態(tài)S={(x

,y)x=0,y=0,1,2,3;

x=3,y=0,1,2,3;x=y=1,2}用圖的鄰接矩陣求解：首先介紹圖論中的一個(gè)定理G是一個(gè)圖，V（G）為G的頂點(diǎn)集，E(G)為G的邊集。設(shè)G中有n個(gè)頂點(diǎn)

;為G的鄰接距陣，其中

定理1：設(shè)A（G）為圖G的鄰接距陣，則G中從頂點(diǎn)到頂點(diǎn)

，長(zhǎng)度為k

的道路的條數(shù)為

中的i行j列元素.下面分析及求解假設(shè)渡河是從南岸到北岸，（m，n）表示南岸有m個(gè)商人，n個(gè)隨從，全部的允許狀態(tài)共有10個(gè)

以

為頂點(diǎn)集，考慮到奇數(shù)次渡河及偶數(shù)次渡河的不同，我們建立兩個(gè)鄰接距陣

其中其中A表示從南岸到北岸渡河的圖的鄰接距陣，

表示從北岸到南岸渡河的圖的鄰接距陣。

由定理1、我們應(yīng)考慮最小的k，

中1行10列的元素不為0，此時(shí)

即為最少的渡河次數(shù)，而矩陣

中1行10列的元素為最佳的路徑數(shù)目。經(jīng)過(guò)計(jì)算K=5時(shí),

的第1行10列元素為2，所以需11次渡河，有兩條最佳路徑.實(shí)例三渡河問(wèn)題某人帶狗、羊、以及蔬菜渡河，一小船除需人劃外，每次只能載一物過(guò)河。而人不在場(chǎng)時(shí)，狗要吃羊，羊要吃菜，問(wèn)此人應(yīng)如何過(guò)河？模型構(gòu)成：此問(wèn)題可化為狀態(tài)轉(zhuǎn)移問(wèn)題，用四維向量（人，狗，羊，菜）來(lái)表示狀態(tài)，當(dāng)一物在此岸時(shí)相應(yīng)分量取1，而在彼岸時(shí)則取0。(1)可取狀態(tài)人在此岸：(1,1,1,1)，(1,1,1,0)，(1,1,0,1)，(1,0,1,1)，(1,0,1,0)人在彼岸：(0,0,0,0)，(0,0,0,1)，(0,0,1,0)，(0,1,0,0)，(0,1,0,1)總共有十個(gè)可取狀態(tài)。(2)現(xiàn)在用狀態(tài)運(yùn)算來(lái)完成狀態(tài)轉(zhuǎn)移。由于擺一次游戲即可改變現(xiàn)有狀態(tài)，為此再引入一個(gè)四維轉(zhuǎn)移向量，用它來(lái)反映擺渡情況用1表示過(guò)河，0表示未過(guò)河。例如(1,1,0,0)表示人帶狗過(guò)河。此狀態(tài)只有四個(gè)允許轉(zhuǎn)移向量：d1=(1,0,0,0)，d2=(1,1,0,0)，d3=(1,0,1,0)，d4=(1,0,0,1)?，F(xiàn)在規(guī)定狀態(tài)向量與轉(zhuǎn)移向量（分量）之間的運(yùn)算為0+0=0，0+1=1，1+0=1，1+1=0(3)模型求解通過(guò)上面的定義，問(wèn)題化為，由初始狀態(tài)出發(fā)(1,1,1,1)，經(jīng)過(guò)奇數(shù)次上述運(yùn)算轉(zhuǎn)移為狀態(tài)(0,0,0,0)的轉(zhuǎn)移過(guò)程?？捎脠D表示為：

練習(xí)題1.今有3個(gè)油瓶，分別能裝10kg、7kg和3kg油。已知10kg瓶中裝滿(mǎn)了油，其余兩瓶為空瓶?，F(xiàn)要將油分成兩個(gè)5kg，沒(méi)有秤，問(wèn)能找到幾種分油方案，使倒油的次數(shù)盡量的少？2.四名商人各帶一個(gè)隨從乘船渡河，一只小船只能容納二人，由他們自己劃行。隨從們密約，在河的任一岸，一旦隨從的人數(shù)比商人多，就殺人越貨。但是如何乘船渡河的大權(quán)掌握在商人們手中。商人們?cè)鯓硬拍馨踩珊幽?3.三個(gè)人和三個(gè)機(jī)器人要從左岸渡河到右岸。船只有一只，每次可以渡人或機(jī)器人共兩名，三個(gè)人都會(huì)劃船，機(jī)器人中只有一個(gè)會(huì)劃船。為防止意外，每岸有人的時(shí)候，人的數(shù)目不能比機(jī)器人的數(shù)目少，問(wèn)應(yīng)當(dāng)怎樣渡河？?jī)?nèi)容1：數(shù)學(xué)建模及其競(jìng)賽2：中國(guó)大學(xué)生數(shù)學(xué)建模競(jìng)賽歷程3：建模過(guò)程簡(jiǎn)介4：建模案例分析5：數(shù)學(xué)建模論文的撰寫(xiě)2007高教社杯全國(guó)大學(xué)生數(shù)學(xué)建模競(jìng)賽題目:B題：乘公交，看奧運(yùn)

我國(guó)人民翹首企盼的第29屆奧運(yùn)會(huì)明年8月將在北京舉行，屆時(shí)有大量觀眾到現(xiàn)場(chǎng)觀看奧運(yùn)比賽，其中大部分人將會(huì)乘坐公共交通工具（簡(jiǎn)稱(chēng)公交，包括公汽、地鐵等）出行。這些年來(lái)，城市的公交系統(tǒng)有了很大發(fā)展，北京市的公交線路已達(dá)800條以上，使得公眾的出行更加通暢、便利，但同時(shí)也面臨多條線路的選擇問(wèn)題。針對(duì)市場(chǎng)需求，某公司準(zhǔn)備研制開(kāi)發(fā)一個(gè)解決公交線路選擇問(wèn)題的自主查詢(xún)計(jì)