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

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