動態(tài)規(guī)劃matlabppt課件(編輯修改稿)
2025-06-02 12:08 本頁面
【文章內容簡介】 2 動態(tài)規(guī)劃的基本原理 下面我們結合案例的最短路問題來介紹動態(tài) 規(guī)劃的基本思想與基本原理。 窮舉法的計算量將非常大，顯然不適合。 考慮最短路線的一個重要特征： 若從起點 A經過 B點和 C點而達到終點 D是一條最短路線， 則由 B點出 發(fā)經過 C點到達終點 D點的這條子路線，對于從 B點 出發(fā)達到終點 D點的所有可能選擇的不同路線來說， 必定也是最短路線。 12A B C D? ? ?12B C D??在本例中， 若找到了 是由 A到 D的最短路線， 則 也應是從 B1 出 發(fā)到 D點的所有可能選擇的不同路線中的最短路線。 如果不是這樣， 則從 B1點到 D點有另一條距離更短的 路線存在， 把它和原來的最短路線有 A點到 B1點的那 部分連接起來， 就會得到一條從 A點到 D點的新路線， 且比原來的那條最短路線的距離還要短些 ， 這就與 假設矛盾。 基于最短路線的這一特性， 我們考慮尋找 最短路線的方法， 就是從最后一段開始， 用由后向前 逆向遞推的方法， 逐步求出各點到終點的最短路線， 最后求得由起點到終點的最短路線。 以本案例為例，我們按上述思想尋找從 A到 E的最 短路線。 A B1 B2 B3 C1 C2 C3 D1 D2 E 35967752383543 3496? ? ? ? ? ?? ? ? ?3 1 1 4 1313 1 2 4 2, 34m in m in 753,d C D f DfCd C D f D??? ?????? ? ?? ? ? ??? ????第一步， 從 k=4出發(fā)， 狀態(tài)變量 4s 12,DD? ? ? ?4 1 4 24 , 3f D f D??3s1C1 2 3, , ,C C C可取狀態(tài) 它們到 E點的路長分別為 第二步， k=3， 狀態(tài)變量 可取三個值 這是經過一個中途點到達終點 E的兩級決策變量。 從 到 E有兩條路線， 需加以比較取其中最短的， 即 11CD?,E? ? ?3 1 1 .u C D?? ? ? ? ? ?? ? ? ?3 2 1 4 1323 2 2 4 2, 44m in m in 633,d C D f DfCd C D f D??? ?????? ? ?? ? ? ??? ????1C這說明由 到 E的最短距離為 7， 其路徑為 相應的決策為 同理 2C 22 ,C D E??? ?3 2 2 .u C D?? ? ? ? ? ?? ? ? ?3 3 1 4 1333 3 2 4 2, 64m in m in 1 093,d C D f DfCd C D f D??? ?????? ? ?? ? ? ??? ????即 到終點 E的最短距離為 6， 其路徑為 相應的決策為 即 3C 31CD?,E?? ? ? ?2 2 2 2 21 1 , ,f B u B C??? ? ? ?2 1 2 1 21 2 , ,f B u B C??
教學課件相關推薦
鄂ICP備17016276號-1