Posted on 2009-05-16 17:06
歲月流逝 閱讀(614)
評論(0) 編輯 收藏 引用
動態規劃
實驗目的：理解動態規劃的基本思想，理解動態規劃算法的兩個基本要素最優子結構性質和子問題的重疊性質。熟練掌握典型的動態規劃問題。掌握動態規劃思想分析問題的一般方法，對較簡單的問題能正確分析，設計出動態規劃算法，并能快速編程實現。
實驗內容：編程實現講過的例題：最長公共子序列問題、矩陣連乘問題、凸多邊形最優三角剖分問題、電路布線問題等。本實驗中的問題，設計出算法并編程實現。
習題
1． 最長公共子序列
一個給定序列的子序列是在該序列中刪去若干元素后得到的序列。確切地說，若給定序列X=，則另一序列Z=是X的子序列是指存在一個嚴格遞增的下標序列 ，使得對于所有j=1,2,…,k有
解答如下：
a) 最長公共子序列的結構
若用窮舉搜索法，耗時太長，算法需要指數時間。
易證最長公共子序列問題也有最優子結構性質
設序列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=。
最長公共子序列問題具有最優子結構性質。
b) 子問題的遞歸結構
由最長公共子序列問題的最優子結構性質可知，要找出X=和Y=的最長公共子序列，可按以下方式遞歸地進行：當xm=yn時，找出Xm-1和Yn-1的最長公共子序列，然后在其尾部加上xm(=yn)即可得X和Y的一個最長公共子序列。當xm≠yn時，必須解兩個子問題，即找出Xm-1和Y的一個最長公共子序列及X和Yn-1的一個最長公共子序列。這兩個公共子序列中較長者即為X和Y的一個最長公共子序列。
由此遞歸結構容易看到最長公共子序列問題具有子問題重疊性質。例如，在計算X和Y的最長公共子序列時，可能要計算出X和Yn-1及Xm-1和Y的最長公共子序列。而這兩個子問題都包含一個公共子問題，即計算Xm-1和Yn-1的最長公共子序列。
我們來建立子問題的最優值的遞歸關系。用c[i,j]記錄序列Xi和Yj的最長公共子序列的長度。其中Xi=，Yj=。當i=0或j=0時，空序列是Xi和Yj的最長公共子序列，故c[i,j]=0。建立遞歸關系如下：
c) 計算最優值
由于在所考慮的子問題空間中，總共只有θ(m*n)個不同的子問題，因此，用動態規劃算法自底向上地計算最優值能提高算法的效率。
計算最長公共子序列長度的動態規劃算法LCS_LENGTH(X,Y)以序列X=和Y=作為輸入。輸出兩個數組c[0..m ,0..n]和b[1..m ,1..n]。其中c[i,j]存儲Xi與Yj的最長公共子序列的長度，b[i,j]記錄指示c[i,j]的值是由哪一個子問題的解達到的，這在構造最長公共子序列時要用到。最后，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’開始表示結束
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];
}
由于每個數組單元的計算耗費Ο(1)時間，算法lcs_length耗時Ο(mn)。
思考：空間能節約嗎？
2． 計算矩陣連乘積
在科學計算中經常要計算矩陣的乘積。矩陣A和B可乘的條件是矩陣A的列數等于矩陣B的行數。若A是一個p×q的矩陣，B是一個q×r的矩陣，則其乘積C=AB是一個p×r的矩陣。由該公式知計算C=AB總共需要pqr次的數乘。其標準計算公式為：
現在的問題是，給定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]; //為了跟講解時保持一致數組從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項)
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是多邊形上不相鄰的兩個頂點，則線段vivj稱為多邊形的一條弦。弦 將多邊形分割成凸的兩個子多邊形和。多邊形的三角剖分是一個將多邊形分割成互不重迭的三角形的弦的集合T。如圖是一個凸多邊形的兩個不同的三角剖分。
凸多邊形最優三角剖分的問題是：給定一個凸多邊形P=以及定義在由多邊形的邊和弦組成的三角形上的權函數ω。要求確定該凸多邊形的一個三角剖分，使得該三角剖分對應的權即剖分中諸三角形上的權之和為最小。
可以定義三角形上各種各樣的權函數W。例如：定義ω(△vivjvk)=|vivj|+|vivk|+|vkvj|，其中，|vivj|是點vi到vj的歐氏距離。相應于此權函數的最優三角剖分即為最小弦長三角剖分。(注意：解決此問題的算法必須適用于任意的權函數)
4． 防衛導彈
一種新型的防衛導彈可截擊多個攻擊導彈。它可以向前飛行，也可以用很快的速度向下飛行，可以毫無損傷地截擊進攻導彈，但不可以向后或向上飛行。但有一個缺點，盡管它發射時可以達到任意高度，但它只能截擊比它上次截擊導彈時所處高度低或者高度相同的導彈。現對這種新型防衛導彈進行測試，在每一次測試中，發射一系列的測試導彈（這些導彈發射的間隔時間固定，飛行速度相同），該防衛導彈所能獲得的信息包括各進攻導彈的高度，以及它們發射次序。現要求編一程序，求在每次測試中，該防衛導彈最多能截擊的進攻導彈數量，一個導彈能被截擊應滿足下列兩個條件之一：
a)它是該次測試中第一個被防衛導彈截擊的導彈；
b)它是在上一次被截擊導彈的發射后發射，且高度不大于上一次被截擊導彈的高度的導彈。
輸入數據：第一行是一個整數n，以后的n各有一個整數表示導彈的高度。
輸出數據：截擊導彈的最大數目。
分析：定義l[i]為選擇截擊第i個導彈，從這個導彈開始最多能截擊的導彈數目。
由于選擇了第i枚導彈，所以下一個要截擊的導彈j的高度要小于等于它的高度，所以l[i]應該等于從i＋1到n的每一個j，滿足h[j]<=h[i]的j中l[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