1、第第 6 章章 指派問題與旅行商問題指派問題與旅行商問題劉群鋒劉群鋒 講師講師東莞理工學院東莞理工學院1 指派問題及其匈牙利算法指派問題及其匈牙利算法p何謂指派問題何謂指派問題n指派指派n個人去完成個人去完成n項任務項任務n目標：總的效益最高或者總費用最低目標：總的效益最高或者總費用最低n信息：費用矩陣或者效益矩陣信息：費用矩陣或者效益矩陣nnn2n12n22211n1211ccccccccc1 指派問題及其匈牙利算法指派問題及其匈牙利算法p指派問題的表上作業法指派問題的表上作業法nn個收點個收點(收量為收量為1) ，n個發點個發點(發量為發量為1) 發點發點 收點收點A1A2A3發量發量B1

2、1B21B31收量收量1111 指派問題及其匈牙利算法指派問題及其匈牙利算法p指派問題的列舉法指派問題的列舉法n適用于適用于n很小的場合很小的場合 A1A2A3B1121323B2211114B31523101 指派問題及其匈牙利算法指派問題及其匈牙利算法p指派問題的匈牙利算法指派問題的匈牙利算法n理論依據理論依據l費用矩陣的一行費用矩陣的一行(列列)的各個元素減去該行的各個元素減去該行(列列)的的最小元素得到新的費用矩陣，這兩個費用矩陣對最小元素得到新的費用矩陣，這兩個費用矩陣對應的指派問題有相同的最優解！應的指派問題有相同的最優解！n思路思路l讓費用矩陣的每行和每列都出現讓費用矩陣的每行和

3、每列都出現0l找出不同行不同列的找出不同行不同列的n個個0l這些這些0對應的指派就是最優指派對應的指派就是最優指派1 指派問題及其匈牙利算法指派問題及其匈牙利算法p費用矩陣如下，求費用最小的指派費用矩陣如下，求費用最小的指派9784563211724351920312215251 指派問題及其匈牙利算法指派問題及其匈牙利算法p費用矩陣如下，求費用最小的指派費用矩陣如下，求費用最小的指派936248457713114103710365129311 指派問題及其匈牙利算法指派問題及其匈牙利算法p將將最大效益最大效益指派轉化為指派轉化為最小費用最小費用指派指派n用效益矩陣中最大元素減去效益矩陣中的每

4、用效益矩陣中最大元素減去效益矩陣中的每個元素得到費用矩陣個元素得到費用矩陣1 指派問題及其匈牙利算法指派問題及其匈牙利算法p效益矩陣如下，求效益最大的指派效益矩陣如下，求效益最大的指派9784563211724351920312215251 指派問題及其匈牙利算法指派問題及其匈牙利算法p效益矩陣如下，求效益最大的指派效益矩陣如下，求效益最大的指派936248457713114103710365129313 旅行商問題的匈牙利算法旅行商問題的匈牙利算法p何謂旅行商問題何謂旅行商問題n從一個城市出發，不重復地旅行完從一個城市出發，不重復地旅行完n個城市，個城市，最后回到出發點最后回到出發點n目標：

5、找出距離最短或費用最低的旅游路線目標：找出距離最短或費用最低的旅游路線n信息：距離表或旅費表信息：距離表或旅費表n2n12n211n12cccccc3 旅行商問題的匈牙利算法旅行商問題的匈牙利算法p費用矩陣如下，求旅行商問題的最優路徑費用矩陣如下，求旅行商問題的最優路徑8795975866583 旅行商問題的匈牙利算法旅行商問題的匈牙利算法p費用矩陣如下，求旅行商問題的最優路徑費用矩陣如下，求旅行商問題的最優路徑12302072210238697692019151434243 旅行商問題的匈牙利算法旅行商問題的匈牙利算法p費用矩陣如下，求旅行商問題的最優路徑費用矩陣如下，求旅行商問題的最優路徑

6、545764511261436234714 哥尼斯堡七橋問題與歐拉回路哥尼斯堡七橋問題與歐拉回路4 哥尼斯堡七橋問題與歐拉回路哥尼斯堡七橋問題與歐拉回路4 哥尼斯堡七橋問題與歐拉回路哥尼斯堡七橋問題與歐拉回路p歐拉歐拉“一筆畫一筆畫”條件條件n沒有奇點或者只有沒有奇點或者只有2 2個奇點個奇點p歐拉回路歐拉回路n能夠一筆畫出來的一條能夠一筆畫出來的一條回路回路n所有的點必定是偶點所有的點必定是偶點n必定可以從任何一點出發一筆畫出必定可以從任何一點出發一筆畫出p歐拉回路的應用歐拉回路的應用n中國郵遞員問題中國郵遞員問題n4 哥尼斯堡七橋問題與歐拉回路哥尼斯堡七橋問題與歐拉回路p中國郵遞員問題中國

7、郵遞員問題233332223322224 哥尼斯堡七橋問題與歐拉回路哥尼斯堡七橋問題與歐拉回路p中國郵遞員問題的解法中國郵遞員問題的解法n段道圖沒有奇點段道圖沒有奇點l最優路線為一條歐拉回路最優路線為一條歐拉回路n段道圖有奇點段道圖有奇點l不存在現成的歐拉回路不存在現成的歐拉回路l存在最短路徑嗎？存在最短路徑嗎？4 哥尼斯堡七橋問題與歐拉回路哥尼斯堡七橋問題與歐拉回路p中國郵遞員問題中國郵遞員問題233332223322233332223322224 哥尼斯堡七橋問題與歐拉回路哥尼斯堡七橋問題與歐拉回路p有奇點的段道圖怎樣尋找最短路徑？有奇點的段道圖怎樣尋找最短路徑？n添弧法添弧法n用幾條首尾相連的弧連接一對奇點用幾條首尾相連的弧連接一對奇點n添上的弧必須滿足以下條件添上的弧必須滿足以下條件l沒有重疊的添弧沒有重疊的添弧l圈上的添弧總長度不超過圈長的一半圈上的添弧總長度不超過圈長的一半4 哥尼斯堡七橋問題與歐拉回路哥尼斯堡七橋問題與歐拉回路p中國郵遞員問題中國郵遞員問題2333322233