ascal動態(tài)規(guī)劃ppt課件(編輯修改稿)
2025-06-01 08:07 本頁面
【文章內(nèi)容簡介】 在規(guī)定時間內(nèi)得到正確結(jié)果，唯一的方法就是“動態(tài)規(guī)劃”。 下面以示意圖表示動態(tài)規(guī)劃的過程：所選路徑為： 912101810 注意分析時，有以下幾個特點： （ 1）將問題劃分成了 4個階段； （ 2）每個階段均得到了“部分”的最優(yōu)解，得到最優(yōu)解時，需要進(jìn)行條件判斷； （ 3）從最下面一層往頂層推導(dǎo)。 [題 3] 棋盤路徑問題 【 題目簡介 】 有一個 n*m的棋盤，左下角為（ 1,1），右上角為（ n,m），如下圖： 有一顆棋子，初始位置在（ 1,1），該棋子只能向右走或者向上走，問該棋子從（ 1,1）到（ n,m）一共有幾條路徑？ 輸入：兩個整數(shù) n和 m 輸出：一個數(shù)，路徑總數(shù) [題 3] 棋盤路徑問題 【 題目簡介 】 如果使用枚舉的方法，必定有很多路徑被重復(fù)走過，這樣，勢必造成程序運行時間的浪費，當(dāng) n和 m的值比較大的時候，程序很可能超時。為了避免程序的重復(fù)運行，我們可以通過記錄點（ 1,1）到任意一個點（ I,j）的路徑總數(shù)來解決這個問題。假設(shè) F[I,j]是點 (1,1)到點 (I,j)(1≤i≤n, 1≤j≤m)的路徑總數(shù)，因為棋子在棋盤中只能向右或者向上走，所以棋盤中只能 2個點的棋子可以走到點（ I,j），即點 (I,j1)和 (i1,j)，這樣，我們就可以知道， F[I,j]必定是 F[I,j1]和 F[i1,j]的和，即 F[i,j]=F[i1,j]+F[i,j1] 【 例 4】 街道問題 ? 在下圖中找出從左下角到右上角的最短路徑，每步只能向右方或上方走 。 【 例 4】 街道問題 在一般情況下，如果我們用二維數(shù)組 H(i， j)和 V(i， j)分別表示水平方向和豎直方向的各路段長度，如 H(1， 2)表示水平方向上路口 (1， 1)到路口 (1， 2)的路段長度， V(1， 2)表示豎值方向上路口 (0， 2)到路口 (1， 2)的路段長度，則有公式：如 dpl(i， j)=min{dpl(i1， j)+v(i， j)， dpl(i， j1)+h(i， j)} [題 5] 機器分配 【 問題
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1