算法分析大作業(yè).doc

算法分析大作業(yè)動態(tài)規(guī)劃方法解乘法表問題和汽車加油行駛問題目錄1.動態(tài)規(guī)劃解乘法表問題1.1問題描述-1.2算法設計思想-1.3設計方法-1.4源代碼-1.5最終結果-2.動態(tài)規(guī)劃解汽車加油行駛問題2.1問題描述-2.2算法設計思想-2.3設計方法-2.4源代碼-2.5最終結果-3.總結1.動態(tài)規(guī)劃解決乘法表問題1.1問題描述定義于字母表a,b,c)上的乘法表如表所示：依此乘法表,對任一定義于上的字符串,適當加括號表達式后得到一個表達式。例如,對于字符串x=bbbba,它的一個加括號表達式為(b(bb)(ba)。依乘法表,該表達式的值為a。試設計一個動態(tài)規(guī)劃算法,對任一定義于上的字符串x=x1x2xn，計算有多少種不同的加括號方式,使由x導出的加括號表達式的值為a。1.2算法設計思想設常量a,b,c 分別為 1, 2 ,3 。n 為字符串的長度。設字符串的第 i 到 第 j 位乘積為 a 的加括號法有resultija 種，字符串的第 i 到 第 j 位乘積為 b 的加括號法有resultijb 種,字符串的第 i 到 第 j 位乘積為 c 的加括號法有 resultijc 種。則原問題的解是：resultina 。設 k 為 i 到 j 中的某一個字符，則對于 k 從 i 到 j ：resultija += resultika * resultk + 1jc + resultikb * resultk + 1jc + resultikc * resultk + 1ja;resultijb += resultika * resultk + 1ja + resultika * resultk + 1jb + resultikb * resultk + 1jb;resultijc += resultikb * resultk + 1ja + resultikc * resultk + 1jb + resultikc * resultk + 1jc;輸入：輸入一個以a,b,c組成的任意一個字符串。輸出：計算出的加括號方式數(shù)。1.3設計方法乘法表問題直觀理解就是通過加括號使得最終運算結果為a，該問題與矩陣連乘問題類似，矩陣連乘是每一次加括號選擇運算量最小的，寫成數(shù)學表達式有：而乘法表問題則是計算所有加括號運算結果為a的情況數(shù)，并不要求輸出加括號方式。那么可以從乘法的最小單元兩個符號相乘的所有可能開始，接著在兩個符號相乘的基礎上計算三個符號相乘的所有可能。直到計算N長度的符號1-N的所有可能。可以定義一個三維數(shù)組ann3,n為輸入字符串的長度，aij0為從字符串中第i個元素到第j個元素的子串表達式值為a的加括號方式數(shù)，aij1為從字符串中第i個元素到第j個元素的子串表達式值為b的加括號方式數(shù)，aij2為從字符串中第i個元素到第j個元素的子串表達式值為c的加括號方式數(shù)。由乘法表的定義則可知啊aij0=（對k求和，k從i到j-1）aik0*aik+12+aik1*aik+12+aik2*aik+11;同理可得到aij1和aij2。同時由上面的表達式可知，要計算aij,需先計算aik和aik+1，這里k從i到j-1，故aij可采取如下的計算次序1.4源代碼#include iostream#include algorithm#include fstreamusing namespace std;/*fij0 表示在chichj之間以某種方式加括號后，結果為afij1 表示在chichj之間以某種方式加括號后，結果為bfij2 表示在chichj之間以某種方式加括號后，結果為ca = a*c | b*c | c*ab = a*a | a*b | b*bc = b*a | c*b | c*c */int f50503;char chars3 = a, b, c;int mul(int n, char ch) for(int i=0; in; i+) for(int k=0; k3; k+) fiik = (chi = charsk ? 1: 0); /* a = a*c | b*c | c*a b = a*a | a*b | b*b c = b*a | c*b | c*c */ for(int r=1; rn; r+) /規(guī)模 for(i=0; in-r; i+) /區(qū)間左端點 int j = i + r; /區(qū)間右端點 for(int k=i; kj; k+) /斷點 fij0 += fik0*fk+1j2 + fik1*fk+1j2 + fik2*fk+1j0; fij1 += fik0*fk+1j0 + fik0*fk+1j1 + fik1*fk+1j1; fij2 += fik1*fk+1j0 + fik2*fk+1j1 + fik2*fk+1j2; return f0n-10;int main() ifstream fin(mul.txt); cout ch; cout ch; int n = strlen(ch); cout n結果為a的加括號方式為： mul(n, ch) endl; fin.close(); return 0;1.5最終結果2.動態(tài)規(guī)劃解決汽車加油行駛問題2.1問題描述給定一個N*N的方形網(wǎng)絡，設其左上角為起點，坐標為(1，1)，X軸向右為正，Y軸向下為正，每個方格邊長為1。一輛汽車從起點出發(fā)駛向右下角終點， 其坐標為（M，N）。在若干網(wǎng)格交叉點處，設置了油庫，可供汽車在行駛途中，可供汽車在行駛途中加油。汽車在行駛過程中應遵守如下規(guī)則：（1）汽車只能沿網(wǎng)格邊行駛，裝滿油后能行駛K條網(wǎng)格邊。出發(fā)時汽車已裝滿油，在起點與終點處不設油庫。（2）當汽車行駛經(jīng)過一條網(wǎng)格邊時，若其X坐標或Y坐標減小，則應付費用B，否則免付費用。（3）汽車在行駛過程中遇油庫則應加滿油并付加油費用A。（4）在需要時可在網(wǎng)格點處增設油庫，并付增設油庫費用C（不含加油費A）。（5）（1）（4）中的各數(shù)N，K，A，B，C均為正整數(shù)。2.2算法設計思想這個題目,應該說是剛開始的時候被他給嚇到了，只是想著如何去把所有的條件構造起來，然后使用網(wǎng)絡流的方式來解決問題！但是，如果真的是很冷靜下來好好地思考這道題目，就會發(fā)現(xiàn)如果沒有那些限制條件，就是一個求解最長路的題目，這樣就可以直接使用來解決這個問題！關鍵就是在于這個每次最多只能走個網(wǎng)格邊，這樣就是限制了活動的范圍，使得有的邊無法擴展！因此可以考慮使用這個分層思想的最短路問題！就是通過將每一個點進行拆分，這樣，就是相當于一種分類討論的方式！而分類討論了之后，就知道哪些邊是可以擴展的，哪些邊是不能擴展的！關鍵點就是在于該如何選取變量來分層，這就是因情況而異了！像這道題目之中，就是通過油量的多少來擴展邊的！分層思想，說穿了其實就是相當于這個動態(tài)規(guī)劃之中的增加變量的方式來確定狀態(tài)一樣，他們的實質(zhì)其實都是一樣的！2.3設計方法采用的是動態(tài)規(guī)劃的思想來解題,用備忘錄的方法進行遞歸,遞歸的式子后面寫出.不能直接以汽車行駛的費用為目標來進行動態(tài)規(guī)劃,因為最優(yōu)子結構性質(zhì)得不到證明.所以必須把油量和費用一起考慮,作為動態(tài)規(guī)劃的對象,此時就有了最優(yōu)子結構性質(zhì).最優(yōu)子結構性質(zhì)的證明證明:假設路徑M是從起點到終點的一條最小費用路徑,P(x,y)是M經(jīng)過的一個點(非加油站),且油量和費用為(g,c),現(xiàn)假設有一條新路徑Q從起點到點P(x,y),使得其在P(x,y)點的油量和費用為(g,c),其中c備忘錄遞歸剛開始的時候為每個網(wǎng)格點P(x,y)建立一個記錄,初始化時,為該記錄存入一個特殊值W,表示汽車未行駛過.那么在汽車行駛過程中,對每個待求的汽車最小費用值COST,先查看其相應的記錄項C,如果存儲的是初始值W,那么表示這個點P(x,y)是第一次遇到,此時計算出該點的最小費用值,并保存在其相應的記錄項中,以備以后查看.若記錄項C中存儲的不是初始值W,那么表示該問題已經(jīng)求解過了,其相應的記錄項中存儲的就是該點的最小費用值COST,此時要取出記錄項C的值跟最新的計算出的COST進行比較,取其最小的那個數(shù)存入到C中.依此建立記錄項C的值,當程序遞歸完成時,我們也得到了汽車行駛到(n,n)的最小費用值COST.2.4源代碼#include iostream#include algorithm#include fstreamusing namespace std;#define INF 10000/*fij0表示汽車從網(wǎng)格點(1,1)行駛至網(wǎng)格點(i,j)所需的最少費用fij1表示汽車行駛至網(wǎng)格點(i,j)還能行駛的網(wǎng)格邊數(shù)si0表示x軸方向si1表示y軸方向si2表示行駛費用fij0 = minf i+sk0 j+sk1 0 + sk2fij1 = f i+sk0 j+sk1 1 - 1;f110 = 0f111 = Kfij0 = fij0 + A , fij1 = K 如果(i, j)是油庫fij0 = fij0 + C + A, fij1 = K (i, j)不是油庫，且fij1 = 0*/int N; /方形網(wǎng)絡規(guī)模int A; /汽車在行駛過程中遇到油庫應加滿油并付加油費Aint C; /在需要時可在網(wǎng)格點處增設油庫，并付增設油庫費用C（不含加油費A）int B; /當汽車行駛經(jīng)過一條網(wǎng)格邊時，如果其x坐標或y坐標減少，應付費用Bint K; /裝滿油后，還能行駛K條邊int f50502;int s43 = -1,0,0,0,-1,0,1,0,B,0,1,B;int a5050; /方形網(wǎng)絡int dyna() int i, j, k; for (i=1;i=N;i+) for (j=1;j=N;j+) fij0=INF; fij1=K; f110 = 0; f111 = K; int count = 1; int tx, ty; while(count) count = 0; for(i=1; i=N; i+) for(int j=1; j=N; j+) if(i=1 & j=1) continue; int minStep = INF; int minDstep; int step, dstep; for(k=0; k4; k+) /可走的四個方向 tx = i + sk0; ty = j + sk1; if(tx1 | tyN | tyN) /如果出界 continue; step = ftxty0 + sk2; dstep = ftxty1 - 1; if(aij = 1) /如果是油庫 step += A; dstep = K; if(aij=0 & dstep = 0 & (i!=N|j!=N) /如果不是油庫,且油已經(jīng)用完 step += A + C; dstep = K; if(step minStep) /如果有更優(yōu)解 count+; fij0 = minStep; fij1 = minDstep; return fNN0;int main() ifstream fin(car.txt); cout N; cout N; cout K; cout K; cout A; cout A; cout B; cout B; s22 = s32 = B; cout C; cout C; cout n輸入方形網(wǎng)絡：n; for(int i=1; i=N; i+) for(int j=1; j aij; cout aij ; cout endl; cout 最優(yōu)行駛路線所需的費用為： dyna() endl; fin.close(); return 0;2.5最終結果3.總結 動態(tài)規(guī)劃（Dynamic Programming， DP）思想啟發(fā)于分治