算法合集之“約制、放寬”方法在解題中的應用(編輯修改稿)
2024-11-12 20:29 本頁面
【文章內容簡介】 ④ (W:1。D:1) 1 1 1 ⑤ (W:100。D:3) 2)4()2(5,1 ??? WWF 1 求 F1,5 “ 放寬”方法 ?這樣定義的好處是， “最近的消防站” 在定義中消失了。 ?這種自由為轉移方程提供了很大方便。 進一步分析 ?然而，此時要定下轉移方程還是遇到了一點點困難，總覺得結點間相對獨立。 ?原因：策略選取的任意性導致 “ 約制”方法 ?動態(tài)規(guī)劃講求拓撲順序和無后效性。 ?于是不妨對策略增添限制 —— 令 P1到負責站 Pm的路徑為 P1 P2 P3……Pm ，則任意 Pi的負責站都為 Pm。 “ 約制”方法 ? P1—— P2—— P3—— P4……Pm “ 約制”方法 ?下面通過 構造 證明至少存在一個最優(yōu)解滿足該性質 —— P1到負責站Pm的路徑 P1 P2……Pm 中任意 Pi的負責站都為 Pm。 “ 約制”方法 證明 ：假設某最優(yōu)解不滿足這性質。 Ⅰ 構造 ：⑴ 增加結點 s，在 s和有消防 站的結點間連一條權為 0的邊。 ⑵ 以 s為源點做 Dijkstra，記 錄下前驅結點。 ⑶ 如果結點上有消防站則選 擇它為負責站，否則選擇前 驅結點的負責站為負責站。 “ 約制”方法 最小費用 =2 ② (W:1。D:2) 1 ③ (W:1。D:1) 1 ① (W:1。D:2) ④ (W:1。D:1) 1 s 0 0 “ 約制”方法 Ⅱ 此方案滿足上述性質和必要限制： 設任意一個結點到源點的最短路為 P1 P2 P3……Pm s ； 即任意 Pi的負責站都為 Pm。 P1……Pm 2—— Pm1—— Pm—— s “ 約制”方法 結點都選擇最近消防站，所以到負責站的距離不超過 D(這結點 )； 構造選取的消防站與最優(yōu)解一樣，所以總費用最少。 Ⅲ 綜上所述，總存在一個最優(yōu)解 (構造出來的方案 )滿足上述的性質。 ? 如今這限制可以安全地增添上了。 轉移方程 ?首先確定下 Best的轉移方程 ?下面對
教學課件相關推薦
鄂ICP備17016276號-1