版權(quán)說(shuō)明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
1、 行行 遍遍 性性 問(wèn)問(wèn) 題題數(shù)學(xué)建模與數(shù)學(xué)實(shí)驗(yàn)數(shù)學(xué)建模與數(shù)學(xué)實(shí)驗(yàn)行行 遍遍 性性 問(wèn)問(wèn) 題題一、中一、中 國(guó)國(guó) 郵郵 遞遞 員員 問(wèn)問(wèn) 題題二、推二、推 銷銷 員員 問(wèn)問(wèn) 題題三、建模案例:最佳災(zāi)情巡視路線三、建模案例:最佳災(zāi)情巡視路線(一)(一) 歐歐 拉拉 圖圖(二)(二) 中中 國(guó)國(guó) 郵郵 遞遞 員員 問(wèn)問(wèn) 題題(一)(一) 哈哈 密密 爾爾 頓頓 圖圖(二)(二) 推推 銷銷 員員 問(wèn)問(wèn) 題題 7 3 1 2 3 4 1 2 4 5 5 6 6 7 8 9割邊G的邊 是割邊的充要條件是 不含在G的圈中 割邊的定義割邊的定義:設(shè)G連通, E(G),若從G中刪除邊 后,圖G- 不連通,則
2、稱邊 為圖G的割邊eeeeeevvvvvvveeeeeeeee e3 v1 v2 v3 v4e1e2e4 e5e6歐歐 拉拉 圖圖 e3 v1 v2 v3 v4 e1e 2e4e5巡回:v1e1v2e2v3e5v1e4v4e3v3e5v1歐拉道路:v1e1v2e2v3e5v1e4v4e3v3歐拉巡回:v1e1v2e2v3e5v1e4v4e3v3e6v1e3 v1 v2 v3v4e1e2e4 e5e3 v1 v2 v3v 4 e1 e2e4 e5e6歐拉圖 非歐拉圖返回返回中國(guó)郵遞員問(wèn)題中國(guó)郵遞員問(wèn)題- -定義定義 郵遞員發(fā)送郵件時(shí),要從郵局出發(fā),經(jīng)過(guò)他投遞范圍內(nèi)的每條街道至少一次,然后返回郵局
3、,但郵遞員希望選擇一條行程最短的路線這就是中國(guó)郵遞員問(wèn)題中國(guó)郵遞員問(wèn)題. 若將投遞區(qū)的街道用邊表示,街道的長(zhǎng)度用邊權(quán)表示,郵局街道交叉口用點(diǎn)表示,則一個(gè)投遞區(qū)構(gòu)成一個(gè)賦權(quán)連通無(wú)向圖中國(guó)郵遞員問(wèn)題轉(zhuǎn)化為:在一個(gè)非負(fù)加權(quán)連通圖中,尋求一個(gè)權(quán)最小的巡回這樣的巡回稱為最最佳佳巡巡回回中國(guó)郵遞員問(wèn)題中國(guó)郵遞員問(wèn)題- -算法算法 Fleury算法基本思想算法基本思想:從任一點(diǎn)出發(fā),每當(dāng)訪問(wèn)一條邊時(shí),先要進(jìn)行檢查如果可供訪問(wèn)的邊不只一條,則應(yīng)選一條不是未訪問(wèn)的邊集的導(dǎo)出子圖的割邊割邊作為訪問(wèn)邊,直到?jīng)]有邊可選擇為止. v7e3 v1v2 v3v4e1 e2e4 e5 v5 e6e6 e 7 e8 e9e10
4、 若G不是歐拉圖,則G的任何一個(gè)巡回經(jīng)過(guò)某些邊必定多于一次 解決這類問(wèn)題的一般方法是:在一些點(diǎn)對(duì)之間引入重復(fù)邊(重復(fù)邊與它平行的邊具有相同的權(quán)),使原圖成為歐拉圖,但希望所有添加的重復(fù)邊的權(quán)的總和為最小v7e3v1v2v3v4e1e2e4e5v5v6e6e7e8e9Edmonds 最小對(duì)集算法:最小對(duì)集算法:算法步驟:算法步驟:()求出G1的最小權(quán)理想匹配M,得到奇次頂點(diǎn)的最佳配對(duì)例例求右圖所示投遞區(qū)的一條最佳郵遞路線1圖中有 v4、v7、v8、v9四個(gè)奇次頂點(diǎn)用 Floyd 算法求出它們之間的最短路徑和距離:3),(,6),(,9),(,6)(,3),(,5),(,9898979787879
5、,49848484747234989787948474vvdvvPvvdvvPvvdvvPvvdvvvPvvdvvPvvdvvvvPvvvvvvvvvvvv返回返回哈哈 密密 爾爾 頓頓 圖圖返回返回推銷員問(wèn)題推銷員問(wèn)題- -定義定義 流動(dòng)推銷員需要訪問(wèn)某地區(qū)的所有城鎮(zhèn),最后回到出發(fā)點(diǎn)問(wèn)如何安排旅行路線使總行程最小這就是推銷員問(wèn)題推銷員問(wèn)題 若用頂點(diǎn)表示城鎮(zhèn),邊表示連接兩城鎮(zhèn)的路,邊上的權(quán)表示距離(或時(shí)間、或費(fèi)用),于是推銷員問(wèn)題就成為在加權(quán)圖中尋找一條經(jīng)過(guò)每個(gè)頂點(diǎn)至少一次的最短閉通路問(wèn)題定義定義在加權(quán)圖G=(V,E)中,()權(quán)最小的哈密爾頓圈稱為最佳最佳H圈圈()經(jīng)過(guò)每個(gè)頂點(diǎn)至少一次的權(quán)最小的閉通路稱為最佳推銷員回路最佳推銷員回路 一般說(shuō)來(lái),最佳哈密爾頓圈不一定是最佳推銷員回路,同樣最佳推銷員回路也不一定是最佳哈
溫馨提示
- 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝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ù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
- 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ì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 2024年木材及木、竹、藤、棕、草制品項(xiàng)目合作計(jì)劃書
- 2024年綜合校準(zhǔn)系統(tǒng)項(xiàng)目建議書
- 2024年炊具掛盤項(xiàng)目合作計(jì)劃書
- 2024年高壓液壓柱塞泵馬達(dá)項(xiàng)目合作計(jì)劃書
- 2024年索道纜車項(xiàng)目建議書
- 2024年同位素檢測(cè)裝置項(xiàng)目建議書
- 2024年單一稀土氧化物及鹽類項(xiàng)目建議書
- 2024年超高純氣體的純化設(shè)備項(xiàng)目建議書
- 2024年惡唑禾草靈項(xiàng)目建議書
- 新學(xué)期的計(jì)劃范文集錦6篇
- 葡萄牙語(yǔ)翻譯崗位招聘筆試題及解答(某世界500強(qiáng)集團(tuán))
- 鋼結(jié)構(gòu)抗風(fēng)性能設(shè)計(jì)與規(guī)范研究
- Unit1 A New Start Starting out 教學(xué)設(shè)計(jì)-2024-2025學(xué)年高中英語(yǔ)外研版(2019)必修第一冊(cè)
- 2024-2030年中國(guó)信息安全行業(yè)市場(chǎng)發(fā)展分析及發(fā)展?jié)摿εc投資研究報(bào)告
- 2024年山東省春季高考數(shù)學(xué)試卷試題真題(含答案)
- 《物聯(lián)網(wǎng)工程導(dǎo)論》課程標(biāo)準(zhǔn)
- JT-T-1078-2016道路運(yùn)輸車輛衛(wèi)星定位系統(tǒng)視頻通信協(xié)議
- 會(huì)展策劃與管理智慧樹(shù)知到期末考試答案章節(jié)答案2024年湖南師范大學(xué)
- 2022年瀘州市市場(chǎng)檢驗(yàn)檢測(cè)中心招聘考試試題及答案
- 期末考試卷2《心理健康與職業(yè)生涯》(解析卷)高一思想政治課(高教版2023基礎(chǔ)模塊)
- 新教科版五年級(jí)上冊(cè)科學(xué)教材分析
評(píng)論
0/150
提交評(píng)論