Posted on 2009-05-16 17:06
歲月流逝 閱讀(627)
評論(0) 編輯 收藏 引用
動態(tài)規(guī)劃
實(shí)驗(yàn)?zāi)康模豪斫鈩討B(tài)規(guī)劃的基本思想，理解動態(tài)規(guī)劃算法的兩個基本要素最優(yōu)子結(jié)構(gòu)性質(zhì)和子問題的重疊性質(zhì)。熟練掌握典型的動態(tài)規(guī)劃問題。掌握動態(tài)規(guī)劃思想分析問題的一般方法，對較簡單的問題能正確分析，設(shè)計出動態(tài)規(guī)劃算法，并能快速編程實(shí)現(xiàn)。
實(shí)驗(yàn)內(nèi)容：編程實(shí)現(xiàn)講過的例題：最長公共子序列問題、矩陣連乘問題、凸多邊形最優(yōu)三角剖分問題、電路布線問題等。本實(shí)驗(yàn)中的問題，設(shè)計出算法并編程實(shí)現(xiàn)。
習(xí)題
1． 最長公共子序列
一個給定序列的子序列是在該序列中刪去若干元素后得到的序列。確切地說，若給定序列X=，則另一序列Z=是X的子序列是指存在一個嚴(yán)格遞增的下標(biāo)序列 ，使得對于所有j=1,2,…,k有
解答如下：
a) 最長公共子序列的結(jié)構(gòu)
若用窮舉搜索法，耗時太長，算法需要指數(shù)時間。
易證最長公共子序列問題也有最優(yōu)子結(jié)構(gòu)性質(zhì)
設(shè)序列X=和Y=的一個最長公共子序列Z=，則：
i. 若xm=yn，則zk=xm=yn且Zk-1是Xm-1和Yn-1的最長公共子序列；
ii. 若xm≠yn且zk≠xm ，則Z是Xm-1和Y的最長公共子序列；
iii. 若xm≠yn且zk≠yn ，則Z是X和Yn-1的最長公共子序列。
其中Xm-1=，Yn-1=，Zk-1=。
最長公共子序列問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。
b) 子問題的遞歸結(jié)構(gòu)
由最長公共子序列問題的最優(yōu)子結(jié)構(gòu)性質(zhì)可知，要找出X=和Y=的最長公共子序列，可按以下方式遞歸地進(jìn)行：當(dāng)xm=yn時，找出Xm-1和Yn-1的最長公共子序列，然后在其尾部加上xm(=yn)即可得X和Y的一個最長公共子序列。當(dāng)xm≠yn時，必須解兩個子問題，即找出Xm-1和Y的一個最長公共子序列及X和Yn-1的一個最長公共子序列。這兩個公共子序列中較長者即為X和Y的一個最長公共子序列。
由此遞歸結(jié)構(gòu)容易看到最長公共子序列問題具有子問題重疊性質(zhì)。例如，在計算X和Y的最長公共子序列時，可能要計算出X和Yn-1及Xm-1和Y的最長公共子序列。而這兩個子問題都包含一個公共子問題，即計算Xm-1和Yn-1的最長公共子序列。
我們來建立子問題的最優(yōu)值的遞歸關(guān)系。用c[i,j]記錄序列Xi和Yj的最長公共子序列的長度。其中Xi=，Yj=。當(dāng)i=0或j=0時，空序列是Xi和Yj的最長公共子序列，故c[i,j]=0。建立遞歸關(guān)系如下：
c) 計算最優(yōu)值
由于在所考慮的子問題空間中，總共只有θ(m*n)個不同的子問題，因此，用動態(tài)規(guī)劃算法自底向上地計算最優(yōu)值能提高算法的效率。
計算最長公共子序列長度的動態(tài)規(guī)劃算法LCS_LENGTH(X,Y)以序列X=和Y=作為輸入。輸出兩個數(shù)組c[0..m ,0..n]和b[1..m ,1..n]。其中c[i,j]存儲Xi與Yj的最長公共子序列的長度，b[i,j]記錄指示c[i,j]的值是由哪一個子問題的解達(dá)到的，這在構(gòu)造最長公共子序列時要用到。最后，X和Y的最長公共子序列的長度記錄于c[m,n]中。
程序如下：
#include
#include
int lcs_length(char x[], char y[]);
int main()
{
char x[100],y[100];
int len;
while(1)
{
scanf("%s%s",x,y);
if(x[0]=='0') //約定第一個字符串以‘0’開始表示結(jié)束
break;
len=lcs_length(x,y);
printf("%d\n",len);
}
}
int lcs_length(char x[], char y[] )
{
int m,n,i,j,l[100][100];
m=strlen(x);
n=strlen(y);
for(i=0;il[i-1][j])
l[i][j]=l[i][j-1];
else
l[i][j]=l[i-1][j];
return l[m][n];
}
由于每個數(shù)組單元的計算耗費(fèi)Ο(1)時間，算法lcs_length耗時Ο(mn)。
思考：空間能節(jié)約嗎？
2． 計算矩陣連乘積
在科學(xué)計算中經(jīng)常要計算矩陣的乘積。矩陣A和B可乘的條件是矩陣A的列數(shù)等于矩陣B的行數(shù)。若A是一個p×q的矩陣，B是一個q×r的矩陣，則其乘積C=AB是一個p×r的矩陣。由該公式知計算C=AB總共需要pqr次的數(shù)乘。其標(biāo)準(zhǔn)計算公式為：
現(xiàn)在的問題是，給定n個矩陣{A1,A2,…,An}。其中Ai與Ai+1是可乘的，i=1,2,…,n-1。要求計算出這n個矩陣的連乘積A1A2…An。
遞歸公式：
程序如下：
#include
int main()
{
int p[101],i,j,k,r,t,n;
int m[101][101]; //為了跟講解時保持一致數(shù)組從1開始
int s[101][101]; //記錄從第i到第j個矩陣連乘的斷開位置
scanf("%d",&n);
for(i=0;i<=n;i++)
scanf("%d",&p[i]); //讀入p[i]的值(注意：p[0]到p[n]共n+1項(xiàng))
for(i=1;i<=n;i++) //初始化m[i][i]=0
m[i][i]=0;
for(r=1;r表示具有n條邊v0v1，v1v2，… ,vn-1vn的一個凸多邊形，其中，約定v0=vn 。
若vi與vj是多邊形上不相鄰的兩個頂點(diǎn)，則線段vivj稱為多邊形的一條弦。弦 將多邊形分割成凸的兩個子多邊形和。多邊形的三角剖分是一個將多邊形分割成互不重迭的三角形的弦的集合T。如圖是一個凸多邊形的兩個不同的三角剖分。
凸多邊形最優(yōu)三角剖分的問題是：給定一個凸多邊形P=以及定義在由多邊形的邊和弦組成的三角形上的權(quán)函數(shù)ω。要求確定該凸多邊形的一個三角剖分，使得該三角剖分對應(yīng)的權(quán)即剖分中諸三角形上的權(quán)之和為最小。
可以定義三角形上各種各樣的權(quán)函數(shù)W。例如：定義ω(△vivjvk)=|vivj|+|vivk|+|vkvj|，其中，|vivj|是點(diǎn)vi到vj的歐氏距離。相應(yīng)于此權(quán)函數(shù)的最優(yōu)三角剖分即為最小弦長三角剖分。(注意：解決此問題的算法必須適用于任意的權(quán)函數(shù))
4． 防衛(wèi)導(dǎo)彈
一種新型的防衛(wèi)導(dǎo)彈可截?fù)舳鄠€攻擊導(dǎo)彈。它可以向前飛行，也可以用很快的速度向下飛行，可以毫無損傷地截?fù)暨M(jìn)攻導(dǎo)彈，但不可以向后或向上飛行。但有一個缺點(diǎn)，盡管它發(fā)射時可以達(dá)到任意高度，但它只能截?fù)舯人洗谓負(fù)魧?dǎo)彈時所處高度低或者高度相同的導(dǎo)彈。現(xiàn)對這種新型防衛(wèi)導(dǎo)彈進(jìn)行測試，在每一次測試中，發(fā)射一系列的測試導(dǎo)彈（這些導(dǎo)彈發(fā)射的間隔時間固定，飛行速度相同），該防衛(wèi)導(dǎo)彈所能獲得的信息包括各進(jìn)攻導(dǎo)彈的高度，以及它們發(fā)射次序。現(xiàn)要求編一程序，求在每次測試中，該防衛(wèi)導(dǎo)彈最多能截?fù)舻倪M(jìn)攻導(dǎo)彈數(shù)量，一個導(dǎo)彈能被截?fù)魬?yīng)滿足下列兩個條件之一：
a)它是該次測試中第一個被防衛(wèi)導(dǎo)彈截?fù)舻膶?dǎo)彈；
b)它是在上一次被截?fù)魧?dǎo)彈的發(fā)射后發(fā)射，且高度不大于上一次被截?fù)魧?dǎo)彈的高度的導(dǎo)彈。
輸入數(shù)據(jù)：第一行是一個整數(shù)n，以后的n各有一個整數(shù)表示導(dǎo)彈的高度。
輸出數(shù)據(jù)：截?fù)魧?dǎo)彈的最大數(shù)目。
分析：定義l[i]為選擇截?fù)舻趇個導(dǎo)彈，從這個導(dǎo)彈開始最多能截?fù)舻膶?dǎo)彈數(shù)目。
由于選擇了第i枚導(dǎo)彈，所以下一個要截?fù)舻膶?dǎo)彈j的高度要小于等于它的高度，所以l[i]應(yīng)該等于從i＋1到n的每一個j，滿足h[j]<=h[i]的j中l(wèi)[j]的最大值。
程序如下：
#include
int main()
{
int i,j,n,max,h[100],l[100];
scanf("%d",&n);
for(i=0;i=0;i--)
{
max=0;
for(j=i+1;jh[j]&&max
void readdata();
void init();
int n,a[100],b[100],l[100][100];
int main()
{
int i,j;
readdata();
init();
for(i=n-2;i>=0;i--)
for(j=1;jb[j])
l[i][j]=l[i+1][j-1]-1;
else if(l[i+1][j-1]-1>l[i][j-1])
l[i][j]=l[i+1][j-1]-1;
else
l[i][j]=l[i][j-1];
printf("%d",l[0][n-1]);
}
void readdata()
{
int i;
scanf("%d",&n);
for(i=0;i