算法實驗報告

華北電力大學(xué)實驗報告||試驗名稱算法設(shè)計與分析課程名稱算法設(shè)計與分析||11試驗一矩陣連乘一、試驗?zāi)繕?biāo)熟悉動態(tài)規(guī)劃算法設(shè)計思想和設(shè)計步驟，掌握基本程序設(shè)計方法，培養(yǎng)學(xué)生用計算機處理實二、試驗要求：用動態(tài)規(guī)劃算法解矩陣連乘問題（1）問題描述給定n個矩陣{A1,A2,…,An}，其中Ai與Ai+1是可乘，i=1,2,…,n-1。要算出這n個矩陣連乘積A1A2…An。因為矩陣乘法滿足結(jié)合律，故計算矩陣連乘積能夠有許多不一樣計算次序。這種計算次序能夠用加括號方式來確定。若一個矩陣連乘積計算次序完全確定，也就是說該連乘積已完全加括號，則能夠依此次序重復(fù)調(diào)用2個矩陣相乘標(biāo)準(zhǔn)算法計算出矩陣連乘積。完全加括號矩陣連乘積可遞歸地定義為：（1）單個矩陣是完全加括號；（2）矩陣連乘積A是完全加括號，則A可表示為2個完全加括號矩陣連乘積B和C乘積并加括號，即A=(BC)。比如，矩陣連乘積A1A2A3A4有5種不一樣完全加括號方式：（A1（A2（A3A4））），（A1（（A2A3）A4）），（（A1A2）（A3A4）），（（A1（A2A3））A4），（（（A1A2）A3）A4）。每一個完全加括號方式對應(yīng)于一個矩陣連乘積計算次序，這決定著作乘積所需要計算量。若A是一個p×q矩陣，B是一個q×r矩陣，則計算其乘積C=AB標(biāo)準(zhǔn)算法中，需要進行pqr次數(shù)乘。為了說明在計算矩陣連乘積時，加括號方式對整個計算量影響，先考查3個矩陣{A1,A2,A3}連乘情況。設(shè)這三個矩陣維數(shù)分別為10×100，100×5，5×50。加括號方式只有兩種：（（A1A2）A3），（A1（A2A3）），第一個方式需要數(shù)乘次數(shù)為10×100×5＋10×5×50＝7500，第二種方式需要數(shù)乘次數(shù)為100×5×50＋10×100×50＝75000。第二種加括號方式計算量時第一個方式計算量10倍。由此可見，在計算矩陣連乘積時，加括號方式，即計算次序?qū)τ嬎懔坑泻艽笥绊?。于是，自然提出矩陣連乘積最優(yōu)計算次序問題，即對于給定相繼n個矩陣{A1,A2,…,An}（其中矩陣Ai維數(shù)為pi-1×pi，i＝1,2,…,n），怎樣確定計算矩陣連乘積A1A2…An計算次序（完全加括號方式），使得依此次序計算矩陣連乘積需要數(shù)乘次數(shù)最少。窮舉搜索法計算量太大，它不是一個有效算法，本試驗采取動態(tài)規(guī)劃算法解矩陣連乘積最優(yōu)計算次序問題。（2）算法設(shè)計思想動態(tài)規(guī)劃算法基本思想是將待求解問題分成若干個子問題，先求解子問題，然后從這些子問題解得到原問題解。與分治法不一樣是，動態(tài)規(guī)劃法經(jīng)分解得到子問題往往不是相互獨立，前一子問題解為后一子問題解提供有用信息，能夠用一個表來統(tǒng)計全部已處理子問題答案，不論該子問題以后是否被用到，只要它被計算過，就將其結(jié)果填入表中。本試驗算法思緒是：1、計算最優(yōu)值算法MatrixChain()：建立兩張表（即程序中**m和**s，利用二維指針存放），一張表存放矩陣相乘最小運算量，主對角線上值為0，依次求2個矩陣、3個矩陣…、直到n個矩陣相乘最小運算量，其中每次矩陣相乘最小運算量都在上一次矩陣相乘最小運算量基礎(chǔ)上求得，最終一次求得值即為n個矩陣相乘最小運算量；另一張表存放最優(yōu)斷開位置。2、輸出矩陣結(jié)合方式算法Traceback()：矩陣結(jié)合即是給矩陣加括號，打印出矩陣結(jié)合方式，由遞歸過程Traceback()完成。分三種情況：（1）只有一個矩陣，則只需打印出A1；（2）有兩個矩陣，則需打印出（A1A2）；（3）對于矩陣數(shù)目大于2，則應(yīng)該調(diào)用遞歸過程Traceback()兩次，結(jié)構(gòu)出最優(yōu)加括號方式。三、試驗儀器及設(shè)備visualstudio。程序設(shè)計#include"stdafx.h"#include<iostream>usingnamespacestd;constintMAX=100;//p用來統(tǒng)計矩陣行列，main函數(shù)中有說明//m[i][j]用來統(tǒng)計第i個矩陣至第j個矩陣最優(yōu)解//s[][]用來統(tǒng)計從哪里斷開才可得到該最優(yōu)解intp[MAX+1],m[MAX][MAX],s[MAX][MAX];intn;//矩陣個數(shù)intmatrixChain(){for(inti=0;i<=n;i++)m[i][i]=0;for(intr=2;r<=n;r++)//對角線循環(huán)for(inti=0;i<=n-r;i++)//行循環(huán){ intj=r+i-1;//列控制//找m[i][j]最小值，先初始化一下，令k=im[i][j]=m[i+1][j]+p[i+1]*p[i]*p[j+1];s[i][j]=i;//k從i+1到j(luò)-1循環(huán)找m[i][j]最小值for(intk=i+1;k<j;k++) {inttemp=m[i][k]+m[k+1][j]+p[i]*p[k+1]*p[j+1];if(temp<m[i][j]) {m[i][j]=temp;//s[][]用來統(tǒng)計在子序列i-j段中，在k位置處//斷開能得到最優(yōu)解s[i][j]=k; } }}returnm[0][n-1];}//依照s[][]統(tǒng)計各個子段最優(yōu)解，將其輸出voidtraceback(inti,intj){if(i==j){cout<<'A'<<i;return;}if(i<s[i][j])cout<<'(';traceback(i,s[i][j]);if(i<s[i][j])cout<<')';if(s[i][j]+1<j)cout<<'(';traceback(s[i][j]+1,j);if(s[i][j]+1<j)cout<<')';}voidtraceback(){cout<<'(';traceback(0,n-1);cout<<')';cout<<endl;}intmain(){cout<<"請輸入矩陣個數(shù)："<<endl;cin>>n;cout<<"輸入矩陣（形如a*b,中間用空格隔開）:"<<endl;for(inti=0;i<=n;i++)cin>>p[i];//測試數(shù)據(jù)能夠設(shè)為六個矩陣分別為//A1[30*35],A2[35*15],A3[15*5],A4[5*10],A5[10*20],A6[20*25]//則p[0-6]={30,35,15,5,10,20,25}cout<<"輸出結(jié)果以下："<<endl;matrixChain();traceback(0,n-1);//最終解值為m[0][n-1];cout<<endl;return0;}數(shù)據(jù)輸入和結(jié)果輸出六、試驗總結(jié)：此次試驗基本達成了試驗?zāi)繕?biāo)，用動態(tài)規(guī)劃思想處理了矩陣連乘問題。在這次試驗過程中，剛開時編程時候疑惑了很長時間，編程需要注意算法代碼與實際語言結(jié)合。在進行代碼驗證時不但需要驗證給定數(shù)據(jù)還要自編數(shù)據(jù)驗證。試驗二0-1背包（動態(tài)規(guī)劃）試驗?zāi)繕?biāo)：1.利用動態(tài)規(guī)劃思想，設(shè)計處理上述問題算法，找出最大背包價值裝法。2.掌握動態(tài)規(guī)劃應(yīng)用二、試驗要求：問題描述:給定n種物品和一背包。物品i重量是wi，其價值為vi，背包容量為C。問應(yīng)怎樣選擇裝入背包物品，使得裝入背包中物品總價值最大?在選擇裝入背包物品時，對每種物品i只有兩種選擇，即裝入背包或不裝入背包。不能將物品裝入背包數(shù)次，也不能只裝入部分物品。0-1背包問題是一個特殊整數(shù)規(guī)劃問題三、試驗儀器：visualstudio四、試驗代碼：題目分析：0-1背包問題具備最優(yōu)子結(jié)構(gòu)性質(zhì)，能夠據(jù)此定義遞歸關(guān)系，建立遞歸方程，并以自底向上方式計算最優(yōu)值，依照計算最優(yōu)值時得到信息，結(jié)構(gòu)最優(yōu)解。#include"stdafx.h"#include"iostream";usingnamespacestd;intn=5;intw[]={0,3,2,1,4,5};intv[]={0,25,20,15,40,50};intx[5];intV[6][7];intC=6;voidmain(void){ inti,j; for(i=0;i<=n;i++) V[i][0]=0; for(j=0;j<=C;j++) V[0][j]=0; for(i=1;i<=n;i++) { for(j=1;j<=C;j++) { if(j<w[i]) V[i][j]=V[i-1][j]; else { if(V[i-1][j]>V[i-1][j-w[i]]+v[i]) V[i][j]=V[i-1][j]; else V[i][j]=V[i-1][j-w[i]]+v[i]; } } } //以上結(jié)構(gòu)動態(tài)規(guī)劃表 j=C; for(i=n;i>0;i--) { if(V[i][j]>V[i-1][j]) { x[i]=1; j=j-w[i]; } else x[i]=0; } printf("動態(tài)規(guī)劃表以下：\n"); for(i=0;i<6;i++) { for(j=0;j<7;j++) { printf("%8d",V[i][j]); } printf("\n"); } printf("裝入背包物品：\n"); for(i=0;i<6;i++) printf("%4d",x[i]); printf("\n背包取得最大值：\n"); printf("%4d\n",V[n][C]);}五、試驗結(jié)果：六、試驗總結(jié)：這次試驗用到是動態(tài)規(guī)劃法，0/1背包問題用動態(tài)規(guī)劃法首先要結(jié)構(gòu)動態(tài)規(guī)劃表，用三個for語句實現(xiàn)；依照動態(tài)規(guī)劃表每行最大值改變確定每個元素裝入是否，逐步確定出裝入背包物品，背包容量最大值也就是動態(tài)規(guī)劃表最右下角。在此次試驗中碰到了動態(tài)規(guī)劃表結(jié)構(gòu)紊亂情況，經(jīng)核查是因數(shù)組初始位置0混同成1造成。試驗三0-1背包（回溯法）一、試驗?zāi)繕?biāo)用回溯法處理0-1背包問題學(xué)會回溯法實際應(yīng)用二、試驗要求問題描述:給定n種物品和一背包。物品i重量是wi，其價值為vi，背包容量為C。問應(yīng)怎樣選擇裝入背包物品，使得裝入背包中物品總價值最大?在選擇裝入背包物品時，對每種物品i只有兩種選擇，即裝入背包或不裝入背包。不能將物品裝入背包數(shù)次，也不能只裝入部分物品，用回溯法處理該問題三、試驗儀器visualstudio四、試驗代碼#include<iostream.h>//定義min、max函數(shù)intmin(inta,intb){ if(a>=b)returnb; elsereturna;}intmax(inta,intb){ if(a>=b)returna; elsereturnb;}voidKnapsack(intv[6],intw[6],intc,intn,intm[6][6])//{ intjmax=min(w[n]-1,c); for(intj=0;j<jmax;j++) m[n][j]=0; for(intp=w[n];p<=c;p++) m[n][p]=v[n]; for(inti=n-1;i>1;i--) { jmax=min(w[i]-1,c); for(intj=0;j<=jmax;j++) m[i][j]=m[i+1][j]; for(intt=w[i];t<=c;t++) m[i][t]=max(m[i+1][t],m[i+1][t-w[i]]+v[i]); } m[1][c]=m[2][c]; if(c>=w[1]) m[1][c]=max(m[1][c],m[2][c-w[1]]+v[1]);}voidTraceback(intm[6][6],intw[6],intc,intn,intx[6]){ for(inti=1;i<n;i++) if(m[i][c]==m[i+1][c])x[i]=0; else { x[i]=1; c-=w[i]; } x[n]=(m[n][c]!=0)?1:0;}voidmain(){ intn1=5; intc1=6; intw1[6]={0,3,2,1,4,5}; intv1[6]={0,25,20,15,40,50}; intt[6][6]; intx1[6]; intm=0; //cout<<"請輸