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