圖論模型在實(shí)際中的應(yīng)用課件_第1頁(yè)
圖論模型在實(shí)際中的應(yīng)用課件_第2頁(yè)
圖論模型在實(shí)際中的應(yīng)用課件_第3頁(yè)
圖論模型在實(shí)際中的應(yīng)用課件_第4頁(yè)
圖論模型在實(shí)際中的應(yīng)用課件_第5頁(yè)
已閱讀5頁(yè),還剩56頁(yè)未讀, 繼續(xù)免費(fèi)閱讀

VIP免費(fèi)下載

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡(jiǎn)介

1、數(shù)學(xué)建模,雷濤 羅睿辭 王堯 汪瑜婧,圖論模型在實(shí)際中的應(yīng)用,數(shù)學(xué)建模的定義,目前還沒有統(tǒng)一的定義 數(shù)學(xué)模型是為一種特殊目的而建立的一個(gè)抽象的、簡(jiǎn)化的結(jié)構(gòu)。 描述現(xiàn)實(shí)世界的一部分特征 表現(xiàn)事物之間的一部分客觀聯(lián)系,圖論模型在實(shí)際中的應(yīng)用,數(shù)學(xué)模型的分類,微分方程模型 差分方程模型 層次分析模型 線性規(guī)劃模型 動(dòng)態(tài)規(guī)劃模型 圖論模型 其它模型,圖論模型在實(shí)際中的應(yīng)用,主要內(nèi)容,建模的方法和步驟 汪瑜婧 圖論模型的建立 羅睿辭 圖論模型的選擇和關(guān)系的簡(jiǎn)化 雷濤 其它數(shù)學(xué)模型舉例 王堯,圖論模型在實(shí)際中的應(yīng)用,建模的方法和步驟,模型準(zhǔn)備 模型假設(shè) 模型的建立 模型求解與分析 模型檢驗(yàn) 模型應(yīng)用,圖論

2、模型在實(shí)際中的應(yīng)用,問題的提出,2007CUMCM B題 乘公交,看奧運(yùn) 給定若干條公交線路,以及在每條公交線路中任意相鄰的兩站之間所花費(fèi)的時(shí)間。 并且給定乘客在任意站點(diǎn)換乘的耗時(shí) 要求給出任意兩公汽站點(diǎn)之間線路選擇問題的一般數(shù)學(xué)模型與算法,求出最佳的公交線路,圖論模型在實(shí)際中的應(yīng)用,模型的假設(shè),對(duì)”最優(yōu)”的理解有三個(gè)具有代表性的指標(biāo): 時(shí)間最短 花費(fèi)最少 最方便(換乘次數(shù)最少) 不同的人群對(duì)最優(yōu)的理解不同,需要根據(jù)實(shí)際定義.可以根據(jù)需要定義代價(jià)函數(shù),三個(gè)指標(biāo)的權(quán)重不同,代價(jià)值也不同。 以時(shí)間最短為例,圖論模型在實(shí)際中的應(yīng)用,模型的建立,G=(V,E) 每個(gè)車站:G的頂點(diǎn) 每條公交線路相鄰兩點(diǎn)

3、的連線:G的邊 邊的權(quán)重:耗費(fèi)時(shí)間 點(diǎn)的權(quán)重:換乘時(shí)間 并不是一個(gè)簡(jiǎn)單圖,兩點(diǎn)間可能有多條邊,5,9,3,7,a,c,b(8,圖論模型在實(shí)際中的應(yīng)用,考慮a經(jīng)過b到c的最短路徑 由于有換乘的情況,只記錄任意兩點(diǎn)間的最短路徑是不夠的。 并非一個(gè)標(biāo)準(zhǔn)的圖論模型,與經(jīng)典最短路徑問題比較,5,6,7,a,c,b(8,Min(a,b)=5 Min(b,c)=3 Min(a,c)=5+6=11,3,圖論模型在實(shí)際中的應(yīng)用,轉(zhuǎn)化成標(biāo)準(zhǔn)的圖論模型,每條公交線路抽象為一層 層與層之間相連的頂點(diǎn)均代表同一個(gè)車站 它們之間的邊(虛線)的權(quán)值為換乘花費(fèi)的時(shí)間,調(diào)用M*M次Dijkstra算法才能得到最優(yōu)解 M為公交線

4、路的總數(shù),圖論模型在實(shí)際中的應(yīng)用,回顧上圖 導(dǎo)致無法使用標(biāo)準(zhǔn)算法原因: Min(a,b)和Min(b,c)之間需要計(jì)算附加耗時(shí) 不用換車的線路成為最佳路徑 改進(jìn)的想法:一次性地處理不用換車的情況,5,6,7,a,c,Min(a,b)=5 Min(b,c)=3 Min(a,c)=5+6=11,3,b(8,圖論模型在實(shí)際中的應(yīng)用,模型的求解,標(biāo)準(zhǔn)算法: 每次選擇一個(gè)新頂點(diǎn)進(jìn)行擴(kuò)展 所有頂點(diǎn)擴(kuò)展完畢即為最優(yōu)解 修改后的算法 每次對(duì)一個(gè)頂點(diǎn)所能選擇的所有公交線路擴(kuò)展 所有不用換乘就能到達(dá)的頂點(diǎn)均在一次中處理 所有頂點(diǎn)擴(kuò)展完畢即為最優(yōu)解,圖論模型在實(shí)際中的應(yīng)用,算法描述,一次將擴(kuò)展出多個(gè)頂點(diǎn),用最小值堆

5、保存 初始: 起點(diǎn)對(duì)應(yīng)的節(jié)點(diǎn)S入堆;并賦予標(biāo)志信息Time(S)=0 取堆頂,對(duì)此定點(diǎn),逐一枚舉所有不用換乘就能到達(dá)的頂點(diǎn),更新堆中對(duì)應(yīng)點(diǎn)的標(biāo)志信息. 不斷重復(fù)取堆頂?shù)倪^程,直到取出的頂點(diǎn)為最終目標(biāo)T Time(T)即為所求,圖論模型在實(shí)際中的應(yīng)用,舉例說明算法步驟,3,2,4,5,1,3,2,a,b,c,d,e,f,g,12,9,8,15,9,20,6,11,9,22,5,考慮頂點(diǎn)b到頂點(diǎn)g的路徑,圖論模型在實(shí)際中的應(yīng)用,問題重述,加入步行的因素,即任意兩個(gè)車站之間人都可能通過步行到達(dá),并給出步行的時(shí)間代價(jià),圖論模型在實(shí)際中的應(yīng)用,由于每?jī)牲c(diǎn)之間均有步行路徑,每次擴(kuò)展都將涉及到所有頂點(diǎn),復(fù)雜

6、度增加不少 改進(jìn)的辦法 預(yù)處理 找到兩個(gè)相鄰頂點(diǎn)之間路徑的最小值,如果它加上兩個(gè)頂點(diǎn)的權(quán)值之后后,仍然小于一些其它的路徑,就可以將其它路徑刪除.這樣至少可以刪除不少步行路徑 考慮實(shí)際情況,可設(shè)定步行時(shí)間的上限,5,6,7,a,c,加入步行的路徑 并給定權(quán)值,20,圖論模型在實(shí)際中的應(yīng)用,算法的總結(jié),關(guān)鍵在于如何解決換乘的耗時(shí) 擴(kuò)展節(jié)點(diǎn)的策略與經(jīng)典算法不同 算法實(shí)際用到了分支界限法的思想 類似于回溯法,但是求解的目標(biāo)不同。 目標(biāo):找到使目標(biāo)函數(shù)取極值的解,圖論模型在實(shí)際中的應(yīng)用,分支界限法思想,以廣度優(yōu)先或以最小耗費(fèi)(最大效益)優(yōu)先的方式搜索問題的解空間樹 從一個(gè)點(diǎn)開始,每次以一定的策略擴(kuò)展一些

7、結(jié)點(diǎn)。每一個(gè)活結(jié)點(diǎn)一旦成為擴(kuò)展結(jié)點(diǎn),就一次性產(chǎn)生其所有子結(jié)點(diǎn),并從活節(jié)點(diǎn)中移除。在產(chǎn)生 的子結(jié)點(diǎn)中,導(dǎo)致不可行解或?qū)е路亲顑?yōu)解的子結(jié)點(diǎn)被舍棄,其余的加入活結(jié)點(diǎn)表中,圖論模型在實(shí)際中的應(yīng)用,選擇擴(kuò)展的節(jié)點(diǎn),從活結(jié)點(diǎn)表中選擇下一擴(kuò)展結(jié)點(diǎn)可能有不同的方式 隊(duì)列式分支限界法:先入先出的原則 優(yōu)先隊(duì)列式分支限界法:選擇優(yōu)先級(jí)最高的節(jié)點(diǎn)進(jìn)行擴(kuò)展 最大效益問題:最大值堆 最小耗費(fèi)問題:最小值堆,圖論模型在實(shí)際中的應(yīng)用,一個(gè)簡(jiǎn)單的例子,印刷電路板將布線區(qū)域劃分為nm個(gè)方格陣列 精確的電路板布線問題要求確定連接方格a的中點(diǎn)到方格b的中點(diǎn)的最短布線方案。 布線時(shí)電路只能沿直線或直角布線。 為避免線路相交,已布線方

8、格做上封閉標(biāo)記,其他線路布線不允許穿過封閉區(qū)域,圖論模型在實(shí)際中的應(yīng)用,圖論模型在實(shí)際中的應(yīng)用,圖論模型在實(shí)際中的應(yīng)用,圖論模型在實(shí)際中的應(yīng)用,圖論模型在實(shí)際中的應(yīng)用,圖論模型在實(shí)際中的應(yīng)用,圖論模型在實(shí)際中的應(yīng)用,圖論模型在實(shí)際中的應(yīng)用,圖論模型在實(shí)際中的應(yīng)用,圖論模型在實(shí)際中的應(yīng)用,建模步驟的總結(jié),模型的準(zhǔn)備 提出問題,搜集數(shù)據(jù)。 模型的假設(shè) 根據(jù)實(shí)際情況,提出合理的假設(shè)簡(jiǎn)化問題。 模型的建立 根據(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í)際中的應(yīng)用,建模步驟的總結(jié),模型的分析與求解 已建立的模型是否有標(biāo)準(zhǔn)解法 轉(zhuǎn)化

9、成標(biāo)準(zhǔn)模型 對(duì)已有的標(biāo)準(zhǔn)解法修改,以適應(yīng)模型的求解 模型的檢驗(yàn) 靈敏性,魯棒性 模型的應(yīng)用,圖論模型在實(shí)際中的應(yīng)用,圖論模型的引入,引例 現(xiàn)有6個(gè)人,任意兩人之間或者相互認(rèn)識(shí),或者相互不認(rèn)識(shí),證明這6個(gè)人中,或者有3個(gè)人彼此都認(rèn)識(shí),或者有3個(gè)人彼此不認(rèn)識(shí),圖論模型在實(shí)際中的應(yīng)用,思路一,只有6個(gè)人,人數(shù)非常少,可以枚舉任意兩人之間的關(guān)系,然后判斷每一種情況是否符合題意。如果所有情況都滿足,則命題成立。 雖然只有6個(gè)人,但是這樣做的時(shí)間復(fù)雜度可不低,枚舉次數(shù)為215 只能借助計(jì)算機(jī)了,有沒有人可以直接證明的辦法呢,圖論模型在實(shí)際中的應(yīng)用,思路二,有了圖論這個(gè)強(qiáng)大的工具 我們還是像往常一樣,以人為

10、頂點(diǎn),關(guān)系為邊,建圖 但是為了以后的直觀,這里圖的建立有一點(diǎn)小小的不同: 如果兩個(gè)人之間相互認(rèn)識(shí),則在這兩個(gè)人(頂點(diǎn))間連一條紅色邊,如果兩個(gè)人不認(rèn)識(shí),則在這兩個(gè)人(頂點(diǎn))間連一條藍(lán)色邊(下面會(huì)看到這樣做的好處) 那么這樣我們就得到了一個(gè)由紅邊和藍(lán)邊組成的6階完全圖 我們實(shí)際上要證明的就是這個(gè)圖中或者存在一個(gè)紅三角形(認(rèn)識(shí)),或者存在一個(gè)藍(lán)三角形(不認(rèn)識(shí),圖論模型在實(shí)際中的應(yīng)用,任取一個(gè)頂點(diǎn)v0,由它連出5條邊到其它的頂點(diǎn),這五條邊只有紅色和藍(lán)色兩種 根據(jù)抽屜原理,肯定有一種顏色的邊有3條或3條以上,不妨設(shè)為紅色,vi,v0,vj,vk,如果vi,vj,vk之間的邊都是藍(lán)邊,則圖中存在一個(gè)藍(lán)三

11、角形 如果至少有1條為紅邊,那么它總會(huì)與v0發(fā)出的兩條紅邊組成一個(gè)紅三角形。 這樣就證明了這個(gè)命題,圖論模型在實(shí)際中的應(yīng)用,現(xiàn)有n根長(zhǎng)度不同的小木棍,每根木棍數(shù)量無限,取出一些小木棍可以拼出一根長(zhǎng)度為這些小木棍長(zhǎng)度之和的木棍?,F(xiàn)在要求最小的整數(shù)k,使得長(zhǎng)度大于等于k的木棍都能夠被給出的n根小木棍拼出,例如,現(xiàn)在有3根小木棍,長(zhǎng)度分別3,5,7 它們可以拼出長(zhǎng)度為3,5,6,7,8,9,10,11,12,13的木棍,看上去5就是答案,怎么證明呢? 可以考慮把能夠拼出來的木棍長(zhǎng)度x根據(jù)模3的結(jié)果分成3類(0,1,2) 對(duì)于x mod 3=0,3能夠拼出來,那么6,9,12等等模3為0的數(shù)都可以被拼

12、出來 對(duì)于x mod 3=1,7能被拼出來,那么7,10,13等等都能被拼出來 對(duì)于x mod 3=2,5能被拼出來,那么8,11,14等等都能被拼出來 也就是說,5確實(shí)是我們要求的答案,這個(gè)題看上去似乎毫無頭緒,那就先看看簡(jiǎn)單的情況吧,圖論模型在實(shí)際中的應(yīng)用,根據(jù)上面的證明,可以發(fā)現(xiàn)一種思路,不妨把上述結(jié)果推廣一下: 設(shè)n根木棍的長(zhǎng)度為L(zhǎng)1,L2,Ln,不妨設(shè)L1為所有木棍中最短的 現(xiàn)在把能夠拼出的木棍長(zhǎng)度根據(jù)模L1的結(jié)果分為L(zhǎng)1類(0,1L1-1),若某一類中的數(shù)模L1的結(jié)果為i,則它們組成的集合為Si 顯然,如果存在一個(gè)集合Si為空,則問題無解 現(xiàn)在考慮所有集合都不為空的情況: 設(shè)每個(gè)集

13、合的最小元為b0,b1bl1-1 (集合不為空,肯定存在最小元) 那么如何去求題目要求的k呢,圖論模型在實(shí)際中的應(yīng)用,考慮這樣一個(gè)值:k=max bn - L1,10. k不屬于任何Si集合,否則與k是某個(gè)S中最小元。即k不能被小木棍拼出。 對(duì)任意Lk,設(shè)L Sp,L+L1maxbn=bp 故Lbp-L1 而L bp (mod p) 所以 L=bp,所以L一定能夠被拼出 由以上兩點(diǎn)可知,k一定是不能被拼出的木棍長(zhǎng)度中的最大值 那么k+1就是我們要求的答案,圖論模型在實(shí)際中的應(yīng)用,還剩下最后一步:求b0,b1,b2bl1-1,也就是每個(gè)集合中的最小元 事實(shí)上,每一個(gè)能被拼出來的木棍長(zhǎng)度x,都是從

14、0開始,用已有的小木棍拼出來的。那么就可以把集合的編號(hào)看做頂點(diǎn),小木棍的長(zhǎng)度看邊的長(zhǎng)度,建立一個(gè)圖。對(duì)于每個(gè)點(diǎn)i(集合i),都連出n條邊,長(zhǎng)度為L(zhǎng)1,L2Ln。對(duì)于長(zhǎng)度為L(zhǎng)k的邊,連向編號(hào)為(i+Lk) mod L1的頂點(diǎn)。 對(duì)于從頂點(diǎn)i到j(luò)的一條長(zhǎng)度為L(zhǎng)的路徑,表示集合i中的一個(gè)數(shù)加上L后得到的數(shù)屬于集合j。 對(duì)于任意一個(gè)能拼出來的數(shù)x(設(shè)x mod L1=p),根據(jù)上面的建圖規(guī)則,x一定是點(diǎn)0到p的一條路徑的長(zhǎng)度。 反過來,0到p的所有路徑長(zhǎng)度都屬于Sp。 所以,可以得出結(jié)論:Sp中的最小元其實(shí)就是頂點(diǎn)0到頂點(diǎn)p的最短路徑長(zhǎng)度。 有了這個(gè)結(jié)論,我們就可以很容易的求出序列bn了 至此,這個(gè)問

15、題也就被完美的解決,圖論模型在實(shí)際中的應(yīng)用,數(shù)學(xué)建模模型的選擇、關(guān)系的簡(jiǎn)化,很多問題都是通過建立圖論模型解決的 圖論中常見的模型有序列、樹、各種圖 如何有效選擇數(shù)學(xué)模型,簡(jiǎn)化原問題中元素之間的關(guān)系是數(shù)學(xué)建模的關(guān)鍵,圖論模型在實(shí)際中的應(yīng)用,題目,坐船問題(改編自湖南省信息學(xué)省隊(duì)選拔賽試題) 北大有n個(gè)學(xué)生去公園劃船: 一只船最多坐2個(gè)人; 出于娛樂目的,大家決定同船的2個(gè)人要么同姓要么同名; 每個(gè)人都必須上船,且不能有腳踏多只船的情況 問最少需要幾只船,圖論模型在實(shí)際中的應(yīng)用,例子,6個(gè)同學(xué):姚金宇,李金宇,姚峰宏,陳峰宏,姚金宇 李金宇,陳峰宏 姚峰宏,圖論模型在實(shí)際中的應(yīng)用,例子,4個(gè)同學(xué):

16、陳峰宏,囧峰宏,羅睿辭,廖葉子 羅睿辭同學(xué)想和廖葉子同學(xué)坐同一船是不行的,因?yàn)樗麄儾煌膊煌?圖論模型在實(shí)際中的應(yīng)用,將每一同學(xué)視為一元素,元素之間的關(guān)系為同名或者同姓 構(gòu)圖是很自然的思路:2名同學(xué)同名或者同姓就連一條邊 一條邊就代表了一種坐船的搭配方式 用最少的邊覆蓋圖中的點(diǎn)一般圖的最小邊覆蓋問題 一般圖最大匹配問題,算法復(fù)雜,實(shí)現(xiàn)麻煩,建模,圖論模型在實(shí)際中的應(yīng)用,建模,圖是本題信息最充分、最自然的模型,但其中數(shù)據(jù)關(guān)系存在很多冗余,沒有充分利用原題的條件 單獨(dú)看同名、同姓這2種關(guān)系,它們都是等價(jià)關(guān)系,具有傳遞性 那么換一種模型構(gòu)造如何? 把圖轉(zhuǎn)換成樹來考慮,圖論模型在實(shí)際中的應(yīng)用,建模

17、,對(duì)于原圖中的每一個(gè)連通分量,一定可以轉(zhuǎn)換成一棵二叉樹 樹中一個(gè)結(jié)點(diǎn)的左孩子跟其同姓; 一個(gè)結(jié)點(diǎn)的右孩子跟其同名。 證明用反證法,圖論模型在實(shí)際中的應(yīng)用,問題的解決,含有n個(gè)點(diǎn)的連通分量,至少需要(n+1) div 2只船 使用貪心法,一定可以構(gòu)造出一個(gè)只需(n+1) div 2只船的解,羅納爾多是羅貫中的獨(dú)生子,去掉他們2個(gè),樹依然連通,廖睿辭依然是羅睿辭的獨(dú)生子,將它們分成一組,得到了一個(gè)最優(yōu)解,圖論模型在實(shí)際中的應(yīng)用,貪心構(gòu)造,1、若葉子結(jié)點(diǎn)是父親的獨(dú)生子,則刪去它們2個(gè),樹依然保持性質(zhì) 2、若父親結(jié)點(diǎn)有2個(gè)孩子 重復(fù)以上步驟直至樹為空或者只剩一個(gè)結(jié)點(diǎn)為止,圖論模型在實(shí)際中的應(yīng)用,貪心舉

18、例,圖論模型在實(shí)際中的應(yīng)用,貪心舉例,圖論模型在實(shí)際中的應(yīng)用,貪心舉例,圖論模型在實(shí)際中的應(yīng)用,貪心舉例,圖論模型在實(shí)際中的應(yīng)用,貪心舉例,圖論模型在實(shí)際中的應(yīng)用,貪心舉例,圖論模型在實(shí)際中的應(yīng)用,小結(jié),通過無向圖到二叉樹的轉(zhuǎn)化,將一個(gè)復(fù)雜的匹配問題用簡(jiǎn)單貪心解決了 建模是一個(gè)去粗取精的過程,要盡可能利用對(duì)我們有利的信息,而忽略那些與我們目標(biāo)無關(guān)的信息 LCA與RMQ問題之間相互轉(zhuǎn)化,就是樹形模型與序列模型相互輔助的經(jīng)典例子 希望本例會(huì)對(duì)同學(xué)們今后的解題有所幫助,圖論模型在實(shí)際中的應(yīng)用,其它數(shù)學(xué)模型舉例,圖論模型在實(shí)際中的應(yīng)用,圖論模型在實(shí)際中的應(yīng)用,棋 盤 多 項(xiàng) 式,圖論模型在實(shí)際中的應(yīng)用,At,圖論模型在實(shí)際中的應(yīng)用,另外,我們回到剛才的問題 我們可以注意到白格主教和黑格主教是不會(huì)互相攻擊的 所以問題可以化簡(jiǎn)為白格放i(i=k)

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

最新文檔

評(píng)論

0/150

提交評(píng)論