中國郵遞員問題ppt課件(編輯修改稿)
2025-06-01 22:01 本頁面
【文章內(nèi)容簡介】 送范圍內(nèi)，街道中沒有 奇點 ，那么他就可以從配送中心出發(fā)，走過每條街道一次，且僅一次，最后回到配送中心，這樣他所走的路程也就是最短的路程。 ? 對于有奇點的街道圖，該怎么辦呢？ ? 這時就必須在每條街道上重復走一次或多次。 舉例說明 ? 如圖所示。 v 1 v 2 v 3 v 4 v 5 v 6 3 2 4 4 5 2 6 4 8 1 1 11 1 1 1 V1~V2~V4~V3~V2~V4~V6~V5~V4~V6~V5~V3~V1 總權(quán)為 12 另一路徑見書 P278 路徑（ b）總權(quán)為 11. ? 如果在某條路線中，邊 [vi,vj]上重復走幾次，我們就在圖中 vi,vj之間增加幾條邊，令每條邊的權(quán)和原來的權(quán)相等，并把所增加的邊，稱為 重復邊 ，于是這條路線就是相應的新圖中的 歐拉圖 。 ? 原來的問題可以敘述為在一個有奇點的圖中，要求增加一些重復邊，使新圖不含奇點，并且重復邊的總權(quán)為最小。 ? 我們把使新圖不含奇點而增加的重復邊簡稱為 可行（重復邊）方案 ，使總權(quán)最小的可行方案為 最優(yōu)方案 。 中國郵遞員問題的實質(zhì) ? 中國郵遞員問題 — 可以敘述為在一個有奇點的圖中，要求增加一些重復邊，使新圖不含奇點，并且重復邊的總權(quán)為最小。 ? 現(xiàn)在的問題是第一個可行方案如何確定？ ? 在確定一個可行方案后，怎么判斷這個方案是否為最優(yōu)方案？ ? 若不是最優(yōu)方案，如何調(diào)整這個方案？ ? 車輛從某配送中心（ v1）出發(fā)，給街道邊上的超市（ v2,v3,v4,v5,v6,v7,v8,v9）送貨，如圖所示。 習題 v1 v3 v2 v4 v8 v7 v6
教學課件相關推薦
鄂ICP備17016276號-1