圖論旅行商ppt課件-資料下載頁(yè)
2025-05-06 23:19本頁(yè)面
【正文】 Dijkstra算法的過(guò)程。（求 min 改為求 max） 26 中國(guó)郵路問(wèn)題 例 某郵遞員負(fù)責(zé)在若干街道投遞郵件?，F(xiàn)從郵局出發(fā)，經(jīng)過(guò)每一條街道最后返郵局，問(wèn)如何行走，使得投遞線路最短。這就是“中國(guó)郵路”問(wèn)題。 中國(guó)郵路問(wèn)題 : 設(shè) G是一個(gè)連通的正權(quán)簡(jiǎn)單 圖，問(wèn)如何在 G中添加重復(fù)邊，使 G有歐拉回路，且重復(fù)邊的總長(zhǎng)最小。 27 2. 算法 定理 設(shè) G是無(wú)向連通圖，適當(dāng)加邊使 G存在最佳郵路的充要條件是 : (1) G中每條邊最多加重復(fù)邊一條 。 (2) 在 G的任意一個(gè)回路上 ,重復(fù)邊的長(zhǎng)度之和不超過(guò)該回路長(zhǎng)度的一半 . 證： 必要性 . 若某邊的重復(fù)邊至少有兩條，則去掉其中兩條后各結(jié)點(diǎn)仍然為偶點(diǎn)，故仍然存在 Euler回路 。 28 若 G的某回路 C上所加重復(fù)邊的長(zhǎng)度之和超過(guò)了該回路長(zhǎng)度的一半，則重新刪增重復(fù)邊： 將 C中原有重復(fù)邊全部刪除，而對(duì) C中原來(lái)沒(méi)有重復(fù)邊的邊，每邊增加一條重復(fù)邊 。 這樣，各點(diǎn)度數(shù)為偶的性質(zhì)不變，故仍含 Euler回路，且總路長(zhǎng)下降，矛盾。 充分性 . (略 ) 29 算法 (1) 適當(dāng)加邊，使所有結(jié)點(diǎn)成為偶點(diǎn) (度數(shù)為偶數(shù)的點(diǎn) )，并且每邊的重復(fù)邊不超過(guò)一條。 (2) 檢查每個(gè)回路，若回路中重復(fù)邊長(zhǎng)之和大于整個(gè)回路長(zhǎng)的一半，則在該回路上作邊的刪增：使重復(fù)邊不重復(fù)，使不重復(fù)邊重復(fù)。 若所有回路都滿足要求 (重復(fù)邊長(zhǎng)之和不大于整個(gè)回路長(zhǎng)的一半 ), 則終止迭代。 例 () 30 3. 有向圖的中國(guó)郵路問(wèn)題 對(duì)于有向圖來(lái)說(shuō) , 中國(guó)郵路問(wèn)題可能無(wú)解。其原因是 G中可能含有出度 (正度 )或入度 (負(fù)度 )為 0的結(jié)點(diǎn)，可能進(jìn)得去出不來(lái)或出得去回不來(lái)。 如果各結(jié)點(diǎn)的正、負(fù)度相等，則 G中存在有向 Euler回路。它經(jīng)過(guò)每邊一次且僅一次，因此任一條 Euler回路都是中國(guó)郵路。 以下通過(guò)一個(gè)例，介紹它的求解方法。 31 v1 v2 v3 v4 v5 8 5 1 2 3 2 5 7 (1)添加總發(fā)點(diǎn)vs總收點(diǎn) vt，求 vs到 vt的 2條有向最短路，將它們添加到原圖中去。 例 求有向圖的中國(guó)郵路問(wèn)題。 vs vt v1 v2 v3 v4 v5 8 5 1 2 3 2 5 7 0 0 0 0 32 (2)求 vs到 vt的一條有向最短路，將它們添加到原圖中去 , 去掉首尾的邊。 vs 0 vt v1 v2 v3 v4 v5 8 5 1 2 3 2 5 7 0 5 (3)求 vs到 vt的最后一條有向最短路，將它們添加到原圖中去 , 去掉首尾的邊。 v1 v2 v3 v4 v5 8 5 1 2 3 2 5 7 5
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1