《動態(tài)規(guī)劃》ppt課件

《《動態(tài)規(guī)劃》ppt課件》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、第3章動態(tài)規(guī)劃理解動態(tài)規(guī)劃算法的概念。掌握動態(tài)規(guī)劃算法的基本要素(1)最優(yōu)子結(jié)構(gòu)性質(zhì)(2)重疊子問題性質(zhì)掌握設(shè)計(jì)動態(tài)規(guī)劃算法的步驟。(1)找出最優(yōu)解的性質(zhì)，并刻劃其結(jié)構(gòu)特征。(2)遞歸地定義最優(yōu)值。(3)以自底向上的方式計(jì)算出最優(yōu)值。(4)根據(jù)計(jì)算最優(yōu)值時得到的信息，構(gòu)造最優(yōu)解。學(xué)習(xí)要點(diǎn):2(1)矩陣連乘問題；(2)最長公共子序列；(3)最大子段和;(4)凸多邊形最優(yōu)三角剖分；(5)多邊形游戲；(6)圖像壓縮；(7)電路布線；(8)流水作業(yè)調(diào)度；(9)背包問題；(10)最優(yōu)二叉搜索樹。通過應(yīng)用范例學(xué)習(xí)動態(tài)規(guī)劃算法設(shè)計(jì)策略3動態(tài)規(guī)劃基本步驟找出最優(yōu)解的性質(zhì)，并刻劃其

2、結(jié)構(gòu)特征。遞歸地定義最優(yōu)值。以自底向上的方式計(jì)算出最優(yōu)值。根據(jù)計(jì)算最優(yōu)值時得到的信息，構(gòu)造最優(yōu)解。1~3是動態(tài)規(guī)劃算法最基本的步驟,若需要最優(yōu)解,則必須執(zhí)行步驟44完全加括號的矩陣連乘積完全加括號的矩陣連乘積可遞歸地定義為：單個矩陣是完全加括號的；矩陣連乘積A是完全加括號的，則A可表示為2個完全加括號的矩陣連乘積B和C的乘積并加括號，即A=(BC)設(shè)有四個矩陣A,B,C,D，總共有五種完全加括號的方式:(A((BC)D))(A(B(CD)))((AB)(CD))(((AB)C)D)((A(BC)D))5完全加括號的矩陣連乘積設(shè)有四個矩陣A,B,C,D，它們的維數(shù)分

3、別是：A=50×10,B=10×40,C=40×30,D=30×5矩陣A和B可乘的條件是:矩陣A的列數(shù)等于矩陣B的行數(shù).設(shè)A是p×q的矩陣,B是q×r的矩陣,則乘積是p×r的矩陣;計(jì)算量是pqr.上述5種完全加括號方式的計(jì)算工作量為:(A((BC)D)),(A(B(CD))),((AB)(CD)),(((AB)C)D),((A(BC)D))16000,10500,36000,87500,34500BC:10×40×30=12000,(BC)D:10×30×5=1500,(A((BC)D)):50×10×5=25006示例7示例8矩陣連乘問題定義：給定n個矩陣{A1

4、,A2,…,An}，其中Ai與Ai+1是可乘的，i=1,2,…n-1?？疾爝@n個矩陣的連乘積A1A2…An。由于矩陣乘法滿足結(jié)合律，所以計(jì)算矩陣的連乘可以有許多不同的計(jì)算次序。這種計(jì)算次序可以用加括號的方式來確定。若一個矩陣連乘積的計(jì)算次序完全確定，也就是說該連乘積已完全加括號，則可以依此次序反復(fù)調(diào)用2個矩陣相乘的標(biāo)準(zhǔn)算法計(jì)算出矩陣連乘積9算法復(fù)雜度分析：對于n個矩陣的連乘積，設(shè)其不同的計(jì)算次序?yàn)镻(n)。由于每種加括號方式都可以分解為兩個子矩陣的加括號問題：(A1...Ak)(Ak+1…An)可以得到關(guān)于P(n)的遞推式如下：矩陣連乘問題給定n個矩陣｛A1,A2

5、,…,An｝，其中Ai與Ai+1是可乘的，i=1，2…，n-1。如何確定計(jì)算矩陣連乘積的計(jì)算次序，使得依此次序計(jì)算矩陣連乘積需要的數(shù)乘次數(shù)最少？窮舉法：列舉出所有可能的計(jì)算次序，并計(jì)算出每一種計(jì)算次序相應(yīng)需要的數(shù)乘次數(shù)，從中找出一種數(shù)乘次數(shù)最少的計(jì)算次序。10矩陣連乘問題窮舉法動態(tài)規(guī)劃將矩陣連乘積AiAi+1…Aj簡記為A[i:j],這里i≤j;考察計(jì)算A[i:n]的最優(yōu)計(jì)算次序。設(shè)這個計(jì)算次序在矩陣Ak和Ak+1之間將矩陣鏈斷開，1≤k

6、量，再加上A[1:k]和A[k+1:n]相乘的計(jì)算量11分析最優(yōu)解的結(jié)構(gòu)特征：計(jì)算A[1:n]的最優(yōu)次序所包含的計(jì)算矩陣子鏈A[1:k]和A[k+1:n]的次序也是最優(yōu)的。矩陣連乘計(jì)算次序問題的最優(yōu)解包含著其子問題的最優(yōu)解。這種性質(zhì)稱為最優(yōu)子結(jié)構(gòu)性質(zhì)。問題的最優(yōu)子結(jié)構(gòu)性質(zhì)是該問題可用動態(tài)規(guī)劃算法求解的顯著特征。12設(shè)計(jì)算A[i:j]，1≤i≤j≤n，所需要的最少數(shù)乘次數(shù)m[i,j]，則原問題的最優(yōu)值為m[1,n]當(dāng)i=j時，A[i:j]=Ai，因此，m[i,i]=0，i=1,2,…,n當(dāng)i

7、有種可能建立遞歸關(guān)系13m[i][j]給出了最優(yōu)值，最優(yōu)斷開位置為k：若將對應(yīng)于m[i,j]的斷開位置k記為s[i,j],在計(jì)算出最優(yōu)值m[i,j]后,可遞歸的由s[i,j]構(gòu)造出相應(yīng)的最優(yōu)解.建立遞歸關(guān)系14計(jì)算最優(yōu)值對于1≤i≤j≤n不同的有序?qū)?i,j)對應(yīng)于不同的子問題。因此，不同子問題的個數(shù)最多只有在遞歸計(jì)算時，許多子問題被重復(fù)計(jì)算多次。這也是該問題可用動態(tài)規(guī)劃算法求解的又一顯著特征。用動態(tài)規(guī)劃算法解此問題，可依據(jù)其遞歸式以自底向上的方式進(jìn)行計(jì)算。在計(jì)算過程中，保存已解決的子問題答案。每個子問題只計(jì)算一次，在后面需要時只要簡單查一下，從而避免大量的重復(fù)計(jì)

8、算，最終得