大學競賽數(shù)學建模與數(shù)學實驗 行遍性問題ppt課件

1、 行行 遍遍 性性 問問 題題數(shù)學建模與數(shù)學實驗數(shù)學建模與數(shù)學實驗行行 遍遍 性性 問問 題題一、中一、中 國國 郵郵 遞遞 員員 問問 題題二、推二、推 銷銷 員員 問問 題題三、建模案例：最正確災情巡視道路三、建模案例：最正確災情巡視道路一一 歐歐 拉拉 圖圖二二 中中 國國 郵郵 遞遞 員員 問問 題題一一 哈哈 密密 爾爾 頓頓 圖圖二二 推推 銷銷 員員 問問 題題 7 3 1 2 3 4 1 2 4 5 5 6 6 7 8 9割邊G的邊 是割邊的充要條件是 不含在G的圈中 割邊的定義：設G連通， E(G),假設從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歐拉圖 非歐拉圖前往前往中國郵遞員問題中國郵遞員問題- -定義定義 郵遞員發(fā)送郵件時，要從郵局出發(fā)，經(jīng)過他投遞范圍內(nèi)的每條街道至少一次，然后返回郵局，但郵遞員希望選擇一條行程最短的路

3、線這就是中中國國郵郵遞遞員員問問題題. 若將投遞區(qū)的街道用邊表示，街道的長度用邊權(quán)表示，郵局街道交叉口用點表示，則一個投遞區(qū)構(gòu)成一個賦權(quán)連通無向圖中國郵遞員問題轉(zhuǎn)化為：在一個非負加權(quán)連通圖中，尋求一個權(quán)最小的巡回這樣的巡回稱為最最佳佳巡巡回回中國郵遞員問題中國郵遞員問題- -算法算法 Fleury算法根本思想：從任一點出發(fā)，每當訪問算法根本思想：從任一點出發(fā)，每當訪問一條邊時，先要進展檢查假設可供訪問的邊不只一條邊時，先要進展檢查假設可供訪問的邊不只一條，那么應選一條不是未訪問的邊集的導出子圖的一條，那么應選一條不是未訪問的邊集的導出子圖的割邊作為訪問邊，直到?jīng)]有邊可選擇為止割邊作為訪問邊，直

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

5、oyd 算法求出它們之間的最短路徑和距離：3),(,6),(,9),(,6)(,3),(,5),(,9898979787879,49848484747234989787948474vvdvvPvvdvvPvvdvvPvvdvvvPvvdvvPvvdvvvvPvvvvvvvvvvvv前往前往哈哈 密密 爾爾 頓頓 圖圖前往前往推銷員問題推銷員問題- -定義定義 流動推銷員需求訪問某地域的一切城鎮(zhèn)，最后回到出發(fā)點問如何安排游覽道路使總行程最小這就是推銷員問題 假設用頂點表示城鎮(zhèn)，邊表示銜接兩城鎮(zhèn)的路，邊上的權(quán)表示間隔 或時間、或費用，于是推銷員問題就成為在加權(quán)圖中尋覓一條經(jīng)過每個頂點至少一次的最短閉通路問題定義在加權(quán)圖定義在加權(quán)圖G=(V,E)中，中，權(quán)最小的哈密爾頓圈稱為最正確權(quán)最小的哈密爾頓圈稱為最正確H圈圈經(jīng)過每個頂點至少一次的權(quán)最小的閉通路稱經(jīng)過每個頂點至少一次的權(quán)最小的閉通路稱為最正確推銷員回路為最正確推銷員回路 普通說來，最正確哈密爾頓圈不一定是最正確推銷員回路，同樣最正確推銷員回路也不一定是最正確哈密爾頓圈H回路，長22最正確推