正文內容

計算機算法設計五大常用算法的分析及實例(編輯修改稿)

2026-07-22 05:16 本頁面

　

【文章內容簡介】任一子問題時，列出各種可能的局部解，通過決策保留那些有可能達到最優的局部解，丟棄其他局部解。依次解決各子問題，最后一個子問題就是初始問題的解。由于動態規劃解決的問題多數有重疊子問題這個特點，為減少重復計算，對每一個子問題只解一次，將其不同階段的不同狀態保存在一個二維數組中。與分治法最大的差別是：適合于用動態規劃法求解的問題，經分解后得到的子問題往往不是互相獨立的（即下一個子階段的求解是建立在上一個子階段的解的基礎上，進行進一步的求解）。能采用動態規劃求解的問題的一般要具有3個性質：① 最優化原理：如果問題的最優解所包含的子問題的解也是最優的，就稱該問題具有最優子結構，即滿足最優化原理。② 無后效性：即某階段狀態一旦確定，就不受這個狀態以后決策的影響。也就是說，某狀態以后的過程不會影響以前的狀態，只與當前狀態有關。③有重疊子問題：即子問題之間是不獨立的，一個子問題在下一階段決策中可能被多次使用到。（該性質并不是動態規劃適用的必要條件，但是如果沒有這條性質，動態規劃算法同其他算法相比就不具備優勢）動態規劃算法的基本步驟動態規劃所處理的問題是一個多階段決策問題，一般由初始狀態開始，通過對中間階段決策的選擇，達到結束狀態。這些決策形成了一個決策序列，同時確定了完成整個過程的一條活動路線(通常是求最優的活動路線)。如圖所示。動態規劃的設計都有著一定的模式，一般要經歷以下幾個步驟。初始狀態→│決策１│→│決策２│→…→│決策ｎ│→結束狀態(1)劃分階段：按照問題的時間或空間特征，把問題分為若干個階段。在劃分階段時，注意劃分后的階段一定要是有序的或者是可排序的，否則問題就無法求解。 (2)確定狀態和狀態變量：將問題發展到各個階段時所處于的各種客觀情況用不同的狀態表示出來。當然，狀態的選擇要滿足無后效性。 (3)確定決策并寫出狀態轉移方程：因為決策和狀態轉移有著天然的聯系，狀態轉移就是根據上一階段的狀態和決策來導出本階段的狀態。所以如果確定了決策，狀態轉移方程也就可寫出。但事實上常常是反過來做，根據相鄰兩個階段的狀態之間的關系來確定決策方法和狀態轉移方程。 (4)尋找邊界條件：給出的狀態轉移方程是一個遞推式，需要一個遞推的終止條件或邊界條件。一般，只要解決問題的階段、狀態和狀態轉移決策確定了，就可以寫出狀態轉移方程（包括邊界條件）。實際應用中可以按以下幾個簡化的步驟進行設計：（1）分析最優解的性質，并刻畫其結構特征。（2）遞歸的定義最優解。（3）以自底向上或自頂向下的記憶化方式（備忘錄法）計算出最優值（4）根據計算最優值時得到的信息，構造問題的最優解實例——矩陣連乘(1) 問題描述給定n個矩陣｛A1,A2,…,An｝，其中Ai與Ai+1是可乘的，i=1,2 ,…,n1。如何確定計算矩陣連乘積的計算次序，使得依此次序計算矩陣連乘積需要的數乘次數最少。給定n個矩陣｛A1,A2,…,An｝,其中Ai與Ai+1是可乘的,i=1,2,…,n 。考察這n個矩陣的連乘積A1A2…An由于矩陣乘法滿足結合律，所以計算矩陣的連乘可以有許多不同的計算次序。這種計算次序可以用加括號的方式來確定。若一個矩陣連乘積的計算次序完全確定，也就是說該連乘積已完全加括號，則可以依此次序反復調用2個矩陣相乘的標準算法計算出矩陣連乘積(2) 算法設計①.分析最優解的結構設計求解具體問題的動態規劃算法的第一步是刻畫該問題的最優解的結構特征。我們將矩陣連乘積AiAi+1....Aj簡記為A[ i : j ]。考察計算A[ 1: n]的最優計算次序。設這個計算次序在矩陣Ak和Ak+1之間將矩陣鏈斷開，1=kn，則其相應的完全加括號形式為((A1...Ak)(Ak+1...An))。以此次序，總的計算量為A[ 1 : k ]的計算量加上A[ k+1 : n ]的計算量，再加上A[ 1 : k ]和A[ k+1 : n ]相稱的計算量。這個問題的關鍵特征是：計算A[ 1 :n ]的最優次序所包含的計算矩陣子鏈a[ 1 : k ]和A[ k+1 : n ]的次序也是最優的。因此，矩陣連乘積計算次序問題的最優解包含著其子問題的最優解。這種性質稱為最優子結構性質。問題的最優子結構性質是該問題可以用動態規劃算法求解的顯著特征。②.建立遞歸關系設計動態規劃算法的第二步就是遞歸地定義最優值。對于矩陣連乘積的最有計算次序問題，設計算A[ i : j ], 1=i=j=n，所需的最少數乘次數為m[ i ][ j ]，則原問題的最優值為m[ 1 ][ n]。當i=j時，A[ i j ]=Ai，為單一矩陣，無需計算，因此m[ i ][ i ]=0。當i j時，可以利用最優子結構的性質來計算m[ i ][ j ]。事實上，若計算A[ i : j ]的最優次序在Ak和Ak+1之間斷開，i=kj，則m[ i ][ j ]=m[ i ][ k ]+m[k+1][ j ]+Pi1*Pk*Pj。其中Pi表示第i個矩陣的列數，也是第i1個矩陣的行數，P0表示第一個矩陣的行數。由于在計算時并不知道斷開點k的位置，所以k還未定。不過k的位置只有ji個可能。從而m[ i ][ j ]可以遞歸地定義為：當i=j m[ i ][ j ] = 0當ij m[ i ][ j ] = min{ m[ i ][ k ]+m[ k+1 ][ j ]+Pi1*Pk*Pj } m[ i ][ j ]給

點擊復制文檔內容

電大資料相關推薦

計算機算法設計五大常用算法的分析及實例(編輯修改稿)

計算機與算法初步-資料下載頁

[計算機]windows編程實用算法-資料下載頁

計算機常用算法與程序設計案例教程習題解答-資料下載頁

計算機算法設計與分析--第3章動態規劃-資料下載頁

詳解個性化推薦五大最常用算法-資料下載頁

[計算機]演算法簡介-資料下載頁

計算機算法設計與分析--第6章分支限界法-資料下載頁

[計算機軟件及應用]算法及其描述-資料下載頁

[計算機]水平序的graham-scan算法-資料下載頁

[計算機軟件及應用]并行計算4算法-資料下載頁

計算機算法導論_第11章-資料下載頁

[其它]lesson7計算機算法初步-資料下載頁

計算機算法基礎課后答案-資料下載頁

計算機算法--關于離散數學-資料下載頁

計算機算法導論_第9章-資料下載頁

計算機算法設計五大常用算法的分析及實例-wenkub.com

計算機算法設計五大常用算法的分析及實例(已改無錯字)

計算機算法設計五大常用算法的分析及實例-資料下載頁

計算機算法設計五大常用算法的分析及實例(參考版)

計算機算法設計五大常用算法的分析及實例-文庫吧資料