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