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