圖論模型在實際中的應用課件

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

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

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

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

5、保存 初始: 起點對應的節(jié)點S入堆；并賦予標志信息Time(S)=0 取堆頂,對此定點,逐一枚舉所有不用換乘就能到達的頂點,更新堆中對應點的標志信息. 不斷重復取堆頂的過程,直到取出的頂點為最終目標T Time(T)即為所求,圖論模型在實際中的應用,舉例說明算法步驟,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,考慮頂點b到頂點g的路徑,圖論模型在實際中的應用,問題重述,加入步行的因素,即任意兩個車站之間人都可能通過步行到達,并給出步行的時間代價,圖論模型在實際中的應用,由于每兩點之間均有步行路徑,每次擴展都將涉及到所有頂點,復雜

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

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

8、格做上封閉標記，其他線路布線不允許穿過封閉區(qū)域,圖論模型在實際中的應用,圖論模型在實際中的應用,圖論模型在實際中的應用,圖論模型在實際中的應用,圖論模型在實際中的應用,圖論模型在實際中的應用,圖論模型在實際中的應用,圖論模型在實際中的應用,圖論模型在實際中的應用,圖論模型在實際中的應用,建模步驟的總結,模型的準備 提出問題，搜集數據。 模型的假設 根據實際情況，提出合理的假設簡化問題。 模型的建立 根據所作的假設分析對象的因果關系，利用對象的內在規(guī)律和適當的數學工具，構造各個量間的等式關系或其它數學結構,圖論模型在實際中的應用,建模步驟的總結,模型的分析與求解 已建立的模型是否有標準解法 轉化

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

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

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

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

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

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

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

16、陳峰宏，囧峰宏，羅睿辭，廖葉子 羅睿辭同學想和廖葉子同學坐同一船是不行的，因為他們不同名也不同姓,圖論模型在實際中的應用,將每一同學視為一元素，元素之間的關系為同名或者同姓 構圖是很自然的思路：2名同學同名或者同姓就連一條邊 一條邊就代表了一種坐船的搭配方式 用最少的邊覆蓋圖中的點一般圖的最小邊覆蓋問題 一般圖最大匹配問題，算法復雜，實現麻煩,建模,圖論模型在實際中的應用,建模,圖是本題信息最充分、最自然的模型，但其中數據關系存在很多冗余，沒有充分利用原題的條件 單獨看同名、同姓這2種關系，它們都是等價關系，具有傳遞性 那么換一種模型構造如何？ 把圖轉換成樹來考慮,圖論模型在實際中的應用,建模

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

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