[其它技巧]lecture_04動態(tài)規(guī)劃(參考版)
2024-10-21 22:30本頁面
【正文】 動態(tài)規(guī)劃算法正是利用了這種子問題的重疊性質(zhì)，對每一個子問題只解一次，而后將其解保存在一個表格中，在以后盡可能多地利用這些子問題的解。 基本步驟 2021/11/10 35 三、動態(tài)規(guī)劃問題的特征 動態(tài)規(guī)劃算法的有效性依賴于問題本身所具有的兩個重要性質(zhì)： 最優(yōu)子結(jié)構(gòu)：當(dāng)問題的最優(yōu)解包含了其子問題的最優(yōu)解時，稱該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。若需要求出問題的一個最優(yōu)解，則必須執(zhí)行步驟（ 4）。 其中（ 1）－（ 3）步是動態(tài)規(guī)劃算法的基本步驟。 （ 3）以 自底向上 的方式計(jì)算出最優(yōu)值。設(shè)計(jì)一個動態(tài)規(guī)劃算法，通?？梢园匆韵聨讉€步驟進(jìn)行： 2021/11/10 34 （ 1）找出最優(yōu)解的性質(zhì)，并刻畫其結(jié)構(gòu)特征。在這類問題中，可能會有許多可行解。由此而來的 基本思路是，用一個表記錄所有已解決的子問題的答案 ，不管該問題以后是否被用到，只要它被計(jì)算過，就將其結(jié)果填入表中。考慮某一個f[i]，則有： ? f[i] = max(f[i], f[j]+1) (1=ji，且 Mice[i].W Mice[j].W， Mice[i].S Mice[j].S) ? 其中，初始條件為 f[i]=1 (i=1, 2, ..., n)。我們先對 Mice進(jìn)行排序，以 W為第一關(guān)鍵字，從小到大， S為第二關(guān)鍵字，從大到小。 考慮一下： 2021/11/10 18 二、思考題：最長有序子序列 I 0 1 2 3 4 5 6 7 8 Num[I] 1 4 7 2 5 8 3 6 9 2021/11/10 19 解決方案： I 0 1 2 3 4 5 6 7 8 Num[I] 1 4 7 2 5 8 3 6 9 F[I] 1 2 3 2 3 4 3 4 5 2021/11/10 20 三、 1160 FatMouse39。所以實(shí)際求解時，可從底層開始，層層遞進(jìn)，最后得到最大值。這樣一層一層推下去，直到倒數(shù)第二層時就非常明了。
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1