《算法優(yōu)化策略》ppt課件-文庫吧
2025-04-14 02:45 本頁面
【正文】 ? ?? ??2121]][[)2,1,2,1(iiijjjjiajjiis)2,1,2,1(m a x211 211jjiisnjj mii ??? ???)2,1(m a x)}2,1,2,1(m a x{m a x)2,1,2,1(m a x 211211211211 211iitjjiisjjiis miinjjmiinjj mii ???????????? ?????? ?? ??????? ?? 2 1 2 1211211 ]][[m a x)2,1,2,1(m a x)2,1( j jj i iinjjnjj jiajjiisiit??? 21 ]][[][ i ii jiajb ?????? 2 1211 ][m a x)2,1( j jjnjj jbiit由于解最大子段和問題的動態(tài)規(guī)劃算法需要時間 O(n)，故算法的雙重 for循環(huán)需要計算時間 O(m2n)。 8 最大 m子段和問題 給定由 n個整數(shù) (可能為負整數(shù) )組成的序列 a1,a2,… ,an,以及一個正整數(shù) m，要求確定序列的 m個不相交子段，使這 m個子段的總和達到最大。 設(shè) b(i， j)表示數(shù)組 a的前 j項中 i個子段和的最大值，且第 i個子段含 a[j](1? i ?m， i? j ?n)。則所求的最優(yōu)值顯然為 與最大子段和問題類似地，計算 b(i， j)的遞歸式為 初始時， b(0， j)=0， (1? j ?n)。b(i， 0)=0， (1? i ?m)。 ),(m a x jmbnjm ??),1(]}[),1(m a x],[)1,(m a x {),( 1 njimijatibjajibjib jti ????????? ???優(yōu)化：注意到在上述算法中，計算 b[i][j]時只用到數(shù)組 b的第 i1行和第 i行的值。因而算法中只要存儲數(shù)組 b的當前行，不必存儲整個數(shù)組。另一方面， b(i1， t)的值可以在計算第 i1行時預(yù)先計算并保存起來。計算第 i行的值時不必重新計算，節(jié)省了計算時間和空間。 9 動態(tài)規(guī)劃加速原理 四邊形不等式 10 貨物儲運問題 在一個鐵路沿線順序存放著 n堆裝滿貨物的集裝箱。貨物儲運公司要將集裝箱有次序地集中成一堆。規(guī)定每次只能選相鄰的2堆集裝箱合并成新的一堆，所需的運輸費用與新的一堆中集裝箱數(shù)成正比。 給定各堆的集裝箱數(shù)，試制定一個運輸方案，使總運輸費用最少。 設(shè)合并 a[i:j]， 1≤i≤j≤n，所需的最少費用為 m[i,j]，則原問題的最優(yōu)值為 m[1， n]。由最優(yōu)子結(jié)構(gòu)性質(zhì)可知， jijitajkmkimjimjitjki??????????? ????]}[],[]1,[{m i n0],[根據(jù)遞歸式，按通常方法可設(shè)計計算 m(i,j)的 O(n3)動態(tài)規(guī)劃算法 11 四邊形不等式 jijijkmkimjiwjim jki ??????????? ?? ]},[]1,[{m i n),(0],[貨物儲運問題的動態(tài)規(guī)劃遞歸式是下面更一般的遞歸計算式的特殊情形。 對于 ,當函數(shù) w(i,j)滿足 時稱 w滿足 四邊形不等式 。 當函數(shù) w(i,j)滿足 時稱 W關(guān)于區(qū)間包含關(guān)系單調(diào) 對于滿足四邊形不等式的單調(diào)函數(shù) w，可推知由遞歸式定義的函數(shù) m(i,j)也滿足四邊形不等式，即 )39。,(),39。()39。,39。(),( jiwjiwjiwjiw ???39。39。 jjii ???)39。,(),39。( jiwjiw ?)39。,(),39。()39。,39。(),( jimjimjimjim ???12 四邊形不等式 定義 由函數(shù) m(i,j)的四邊形不等式性質(zhì)可推出函數(shù) s(i,j)的單調(diào)性，即 根據(jù)前面的討論，當 w是滿足四邊形不等式的單調(diào)函數(shù)時，函數(shù) s(i,j)單調(diào)，從而 )},(),()1,(),(|m a x {),( jiwjkmkimjimkjis ?????s(i,j) ? s(i,j+1) ? s(i+1,j+1)， i ? j )},()1,({m i n)},()1,({m i n ),1()1,( jkmkimjkmkim jiskjisjki ????? ??????改進后算法 speedDynamicProg
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1