【教程】大學(xué)競(jìng)賽數(shù)學(xué)建模與數(shù)學(xué)實(shí)驗(yàn) 行遍性問(wèn)題ppt課件

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),假設(shè)從G中刪除邊 后，圖G- 不連通，那么稱邊 為圖G的割邊eeeeeevv

2、vvvvveeeeeeeee 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ó)國(guó)郵郵遞遞員員問(wèn)問(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)算法根本思想：從任一點(diǎn)出發(fā)，每當(dāng)訪問(wèn)一條邊時(shí)，先要進(jìn)展檢查假設(shè)可供訪問(wèn)的邊不只一條邊時(shí)，先要進(jìn)展檢查假設(shè)可供訪問(wèn)的邊不只一條，那么應(yīng)選一條不是未訪問(wèn)的邊集的導(dǎo)出子圖的一條，那么應(yīng)選一條不是未訪問(wèn)的邊集的導(dǎo)出子圖的割邊作為訪問(wèn)邊，直到?jīng)]有邊可選擇為止割邊作為訪問(wèn)邊，直

4、到?jīng)]有邊可選擇為止. v7e3 v1v2 v3v4e1 e2e4 e5 v5 e6e6 e 7 e8 e9e10 假設(shè)G不是歐拉圖，那么G的任何一個(gè)巡回經(jīng)過(guò)某些邊必定多于一次 處理這類問(wèn)題的普通方法是：在一些點(diǎn)對(duì)之間引入反復(fù)邊反復(fù)邊與它平行的邊具有一樣的權(quán)，使原圖成為歐拉圖，但希望一切添加的反復(fù)邊的權(quán)的總和為最小v7e3v1v2v3v4e1e2e4e5v5v6e6e7e8e9Edm onds 最最 小小 對(duì)對(duì) 集集 算算 法法 ：算算法法步步驟驟：求出G1的最小權(quán)理想匹配M，得到奇次頂點(diǎn)的最正確配對(duì)例例 求右圖所示投遞區(qū)的 一條最佳 郵遞路線 1圖中有v4、v7、v8、v9四個(gè)奇次頂點(diǎn)用 Fl

5、oyd 算法求出它們之間的最短路徑和距離：3),(,6),(,9),(,6)(,3),(,5),(,9898979787879,49848484747234989787948474vvdvvPvvdvvPvvdvvPvvdvvvPvvdvvPvvdvvvvPvvvvvvvvvvvv前往前往哈哈 密密 爾爾 頓頓 圖圖前往前往推銷員問(wèn)題推銷員問(wèn)題- -定義定義 流動(dòng)推銷員需求訪問(wèn)某地域的一切城鎮(zhèn)，最后回到出發(fā)點(diǎn)問(wèn)如何安排游覽道路使總行程最小這就是推銷員問(wèn)題 假設(shè)用頂點(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)圖定義在加權(quán)圖G=(V,E)中，中，權(quán)最小的哈密爾頓圈稱為最正確權(quán)最小的哈密爾頓圈稱為最正確H圈圈經(jīng)過(guò)每個(gè)頂點(diǎn)至少一次的權(quán)最小的閉通路稱經(jīng)過(guò)每個(gè)頂點(diǎn)至少一次的權(quán)最小的閉通路稱為最正確推銷員回路為最正確推銷員回路 普通說(shuō)來(lái)，最正確哈密爾頓圈不一定是最正確推銷員回路，同樣最正確推銷員回路也不一定是最正確哈密爾頓圈H回路，長(zhǎng)22最正確推