1、成 績(jī) 評(píng) 定 表學(xué)生姓名班級(jí)學(xué)號(hào)專 業(yè)課程設(shè)計(jì)題目編輯距離問(wèn)題分支限界法0-1背包評(píng)語(yǔ)組長(zhǎng)簽字：成績(jī)?nèi)掌?20 年 月 日課程設(shè)計(jì)任務(wù)書學(xué) 院專 業(yè)學(xué)生姓名班級(jí)學(xué)號(hào)課程設(shè)計(jì)題目編輯距離問(wèn)題 分支限界法0-1背包實(shí)踐教學(xué)要求與任務(wù):要求：1鞏固和加深對(duì)基本算法的理解和運(yùn)用，提高綜合運(yùn)用課程知識(shí)進(jìn)行算法設(shè)計(jì)與分析的能力。2培養(yǎng)學(xué)生自學(xué)參考書籍，查閱手冊(cè)、和文獻(xiàn)資料的能力。3通過(guò)實(shí)際課程設(shè)計(jì)，掌握利用動(dòng)態(tài)規(guī)劃算法、回溯法、分支限界法等算法的基本思想，并能運(yùn)用這些方法設(shè)計(jì)算法并編寫程序解決實(shí)際問(wèn)題。4了解與課程有關(guān)的知識(shí)，能正確解釋和分析實(shí)驗(yàn)結(jié)果。任務(wù)：按照算法設(shè)計(jì)方法和原理，設(shè)計(jì)算法，編寫程序并分

2、析結(jié)果，完成如下內(nèi)容：1. 運(yùn)用動(dòng)態(tài)規(guī)劃算法求解編輯距離問(wèn)題。2. 運(yùn)用分支限界算法求解0-1背包問(wèn)題。工作計(jì)劃與進(jìn)度安排:第11周：查閱資料。掌握算法設(shè)計(jì)思想，進(jìn)行算法設(shè)計(jì)。第12周：算法實(shí)現(xiàn)，調(diào)試程序并進(jìn)行結(jié)果分析。撰寫課程設(shè)計(jì)報(bào)告，驗(yàn)收與答辯。指導(dǎo)教師： 201 年 月 日專業(yè)負(fù)責(zé)人：201 年 月 日學(xué)院教學(xué)副院長(zhǎng)：201 年 月 日摘要算法設(shè)計(jì)與分析，其實(shí)可以解釋為一類優(yōu)化問(wèn)題，一般針對(duì)可以利用計(jì)算機(jī)解決的離散型問(wèn)題的優(yōu)化。主要目的就是為了解決某一問(wèn)題而提出各種不同的解決方案，并且要針對(duì)具體的問(wèn)題做細(xì)致的空間和時(shí)間復(fù)雜度分析。所有的算法中，應(yīng)該盡量選取“好”的算法，這里所說(shuō)的“好”，

3、首先是正確的，其次是所選算法解決問(wèn)題的效率要盡可能的高。計(jì)算機(jī)計(jì)算時(shí)間的長(zhǎng)短以及所用空間的大小，跟算法有直接關(guān)系，用來(lái)衡量算法好壞的兩個(gè)重要標(biāo)準(zhǔn)就是就是時(shí)間和空間復(fù)雜度，所以提出好的解決方案，其算法是重中之重。動(dòng)態(tài)規(guī)劃算法是將待求解的問(wèn)題分解成若干個(gè)子問(wèn)題，先求解子問(wèn)題，然后從這些子問(wèn)題的解得到原問(wèn)題的解。首先找出最優(yōu)解的性質(zhì)，并刻其結(jié)構(gòu)特征，然后遞歸的定義最優(yōu)值（寫出動(dòng)態(tài)規(guī)劃方程）并且以自底向上的方式計(jì)算出最優(yōu)值，最后根據(jù)計(jì)算最優(yōu)值時(shí)得到的信息，構(gòu)造一個(gè)最優(yōu)解。分支限界法類似于回溯法，也是在問(wèn)題的解空間上搜索問(wèn)題解的算法。一般情況下，分支限界法與回溯法的求解目標(biāo)不同?；厮莘ǖ那蠼饽繕?biāo)是找出解

4、空間中滿足約束條件的所有解，而分支限界法的求解目標(biāo)則是找出滿足約束條件的一個(gè)解，或是在滿足約束條件的解中找出使某一目標(biāo)函數(shù)值達(dá)到極大或極小的解，即在某種意義下的最優(yōu)解。分支限界法的搜索策略是，在擴(kuò)展結(jié)點(diǎn)處，先生成其所有的兒子結(jié)點(diǎn)(分支)，然后再?gòu)漠?dāng)前的活結(jié)點(diǎn)表中選擇下一擴(kuò)展結(jié)點(diǎn)。為了有效地選擇下一擴(kuò)展結(jié)點(diǎn)，加速搜索的進(jìn)程，在每一個(gè)活結(jié)點(diǎn)處，計(jì)算一個(gè)函數(shù)值(限界)，并根據(jù)函數(shù)值，從當(dāng)前活結(jié)點(diǎn)表中選擇一個(gè)最有利的結(jié)點(diǎn)作為擴(kuò)展結(jié)點(diǎn)，使搜索朝著解空間上有最優(yōu)解的分支推進(jìn)，以便盡快地找出一個(gè)最優(yōu)解。這種方式稱為分支限界法。人們已經(jīng)用分支限界法解決了大量離散最優(yōu)化的問(wèn)題。關(guān)鍵詞：動(dòng)態(tài)規(guī)劃 分支限界法 編輯

5、距離問(wèn)題 0-1背包問(wèn)題目錄1.動(dòng)態(tài)規(guī)劃法解決編輯距離問(wèn)題11.1問(wèn)題描述11.2問(wèn)題分仔11.3算法設(shè)計(jì)21.4算法實(shí)現(xiàn)31.5結(jié)果分析51.6復(fù)雜度分析52.分支限界法解決0-1背包問(wèn)題62.1問(wèn)題描述62.2問(wèn)題分析62.3算法設(shè)計(jì)72.4算法實(shí)現(xiàn)72.5結(jié)果分析122.6 復(fù)雜度分析123.參考文獻(xiàn)131.動(dòng)態(tài)規(guī)劃法解決編輯距離問(wèn)題1.1問(wèn)題描述 設(shè)A和B是2個(gè)字符串。要用最少的字符操作將A轉(zhuǎn)換為字符串B。這里所說(shuō)的字符操作包括：（1）刪除一個(gè)字符；（2）插入一個(gè)字符：（3）將一個(gè)字符改為另一個(gè)字符。 將字符串A變換為字符串B所用的最少字符操作數(shù)稱為字符串A到B的編輯距離，記為d(A,

6、B)。試設(shè)計(jì)一個(gè)有效算法，對(duì)任給的2個(gè)字符串A和B，計(jì)算其編輯距離d（A,B）。1.2問(wèn)題分仔設(shè)所給的兩個(gè)字符串為A1:m和B1:n，定義一個(gè)二維數(shù)組dpij表示狀態(tài)，dpij= (A1:i,B1:j)表示字符串A1:m的子串A1:i變換到B1:n的子串B1:j的編輯距離，即子串A1:i至少要經(jīng)過(guò)多少次操作（插入、刪除、修改）可以變?yōu)锽1:j。單字符a,b間的編輯距離定義為 例如，字符串A:AGTAAGTAGGC轉(zhuǎn)換為 字符串B:AGTCTGACGC 。 操作一：A串：A G T A A G T * A G G C B串：A G T * C * T G A C G C 需要5步操作（2次刪除，

7、2次修改，1次刪除） 操作二：A串：A G T A A G T A G G C B串：A G T C T G * A C G C 需要4次操作（3次修改，1次刪除）我們計(jì)算的編輯距離是變換的最小步數(shù)，所以要取其中的最小值?？疾鞆淖址瓵1:i到字符串B1:j的轉(zhuǎn)換，有三種情況可以導(dǎo)致上面設(shè)計(jì)的狀態(tài)發(fā)生轉(zhuǎn)移：（1）可以刪除字符Ai需要1次操作。只將字符Ai從A串中刪除，對(duì)序列B1:j沒(méi)有任何影響，此時(shí)問(wèn)題的最優(yōu)子結(jié)構(gòu)形式為將A1:i-1 變?yōu)锽1:j ，再加一步刪除操作，可得dpij = dpi-1j + 1。（2）可以在Ai后面插入一個(gè)字符ch（ch=Bj）需要1次操作。在進(jìn)行插入操作時(shí)，串A

8、1:i 無(wú)任何變化，在A串i+1位置上插入字符Bj,問(wèn)題的最優(yōu)子結(jié)構(gòu)形式為將A1:i變?yōu)锽1:j-1,再加一步插入操作，可得dpij = dpi j-1 + 1。（3）可以修改字符Ai，使它變?yōu)锽j，若Ai=Bj，修改其實(shí)相當(dāng)于用了0步；若Ai != Bj，修改相當(dāng)于用了1步。所以dpij = dpi - 1j - 1 + （Ai = Bj ? 0：1）。 最后的dpij就是選擇上述3種狀態(tài)轉(zhuǎn)移中的最小值。綜上所述，狀態(tài)轉(zhuǎn)移方程dpij可歸結(jié)為如下情況： (1)當(dāng)兩個(gè)字符相同，即Ai=Bj時(shí)， dpij = mindpij-1+1, dpi-1j+1, dpi-1j-1 (2)當(dāng)兩個(gè)字符不同，

9、即Ai != Bj時(shí)， dpij = mindpij-1+1, dpi-1j+1, dpi-1j-1+1需要注意的是，要對(duì)dp00:m，dp0:n0進(jìn)行初始化。*dp0i,就是說(shuō)A串是一個(gè)空串，而B串是個(gè)長(zhǎng)度為i的串，很顯然A串變?yōu)锽串就是插入i個(gè)字符，即dp0i=i。*dpi0 ，就是說(shuō)A串是個(gè)長(zhǎng)度為i的串，而B串是一個(gè)空串，很顯然A串變?yōu)锽串就是刪除i個(gè)字符，即dpi0=i。1.3算法設(shè)計(jì)數(shù)據(jù)輸入：輸入數(shù)據(jù)的第一行是一個(gè)正整數(shù)，表示一共有幾組數(shù)據(jù)。每組數(shù)據(jù)兩行，每行一個(gè)字符串。*每個(gè)字符串長(zhǎng)度不超過(guò)1000結(jié)果輸出：輸出編輯距離。對(duì)于每組數(shù)據(jù)，請(qǐng)輸出一個(gè)整數(shù)表示兩個(gè)字符串的編輯距離。每個(gè)答

10、案占一行。1.4算法實(shí)現(xiàn)#include #include #include #define min(a,b) (a)(b)?(b):(a) #define N 1005 using namespace std; int dpNN; /dpij表示串s1的前i位變換到串s2的前j位的最小步數(shù)int DP(char *s1,char *s2) int i,j,m=strlen(s1),n=strlen(s2),tem;/初始化 for(i=0;i=n;i+) dp0i=i; /從0個(gè)字符轉(zhuǎn)換為i個(gè)字符，需要插入i次 for(i=0;i=m;i+) dpi0=i; /從i個(gè)字符轉(zhuǎn)換為0個(gè)字符，需要

11、刪除i次 /用動(dòng)態(tài)規(guī)劃方法計(jì)算編輯距離 for(i=1;i=m;i+) for(j=1;j0,Wi0,Vi0，1in，要求找出一個(gè)n元0-1向量（x1，x2，xn），Xi0,1,1in，使得，而且達(dá)到最大。因此0-1背包問(wèn)題是一個(gè)特殊的整數(shù)規(guī)劃問(wèn)題：2.2問(wèn)題分析0-1背包問(wèn)題是一類典型的離散型優(yōu)化問(wèn)題，問(wèn)題的約束條件和要求都很簡(jiǎn)單。求解方案也比較多，本論文就幾種典型的求解方案做簡(jiǎn)單的分析，但是主要實(shí)現(xiàn)的是利用分支限界法解決的方案。下面是幾種典型算法的簡(jiǎn)單分析：分支限界法：分支限界法常以廣度優(yōu)先或以最小耗費(fèi)（最大效益）優(yōu)先的方式搜索問(wèn)題的解空間樹。在分支限界法中，每一個(gè)活結(jié)點(diǎn)只有一次機(jī)會(huì)成為擴(kuò)

12、展結(jié)點(diǎn)。活結(jié)點(diǎn)一旦成為擴(kuò)展結(jié)點(diǎn)，就一次性產(chǎn)生其所有兒子結(jié)點(diǎn)。在這些兒子結(jié)點(diǎn)中，導(dǎo)致不可行解或?qū)е路亲顑?yōu)解的兒子結(jié)點(diǎn)被舍棄，其余兒子結(jié)點(diǎn)被加入活結(jié)點(diǎn)表中。 此后，從活結(jié)點(diǎn)表中取下一結(jié)點(diǎn)成為當(dāng)前擴(kuò)展結(jié)點(diǎn)，并重復(fù)上述結(jié)點(diǎn)擴(kuò)展過(guò)程。這個(gè)過(guò)程一直持續(xù)到找到所需的解或活結(jié)點(diǎn)表為空時(shí)為止。 從活結(jié)點(diǎn)表中選擇下一擴(kuò)展結(jié)點(diǎn)的不同方式導(dǎo)致不同的分支限界法： 隊(duì)列式(FIFO)分支限界法：按照隊(duì)列先進(jìn)先出（FIFO）原則選取下一個(gè)節(jié)點(diǎn)為擴(kuò)展節(jié)點(diǎn)。 優(yōu)先隊(duì)列式分支限界法：按照優(yōu)先隊(duì)列中規(guī)定的優(yōu)先級(jí)選取優(yōu)先級(jí)最高的節(jié)點(diǎn)成為當(dāng)前擴(kuò)展節(jié)點(diǎn)。 最大優(yōu)先隊(duì)列：使用最大堆，體現(xiàn)最大效益優(yōu)先 最小優(yōu)先隊(duì)列：使用最小堆，體現(xiàn)最小費(fèi)用

13、優(yōu)先 2.3算法設(shè)計(jì)分支限界法的分析：已知有N個(gè)物品和一個(gè)可以容納M重量的背包，每種物品I的重量為WEIGHT，一個(gè)只能全放入或者不放入，求解如何放入物品，可以使背包里的物品的總效益最大。對(duì)物品的選取與否構(gòu)成一棵解樹，左子樹表示不裝入，右表示裝入，通過(guò)檢索問(wèn)題的解樹得出最優(yōu)解，并用結(jié)點(diǎn)上界殺死不符合要求的結(jié)點(diǎn)。分支限界法的描述：首先，要對(duì)輸入數(shù)據(jù)進(jìn)行預(yù)處理，將各物品依其單位重量?jī)r(jià)值從大到小進(jìn)行排列。在下面描述的優(yōu)先隊(duì)列分支限界法中，節(jié)點(diǎn)的優(yōu)先級(jí)由已裝袋的物品價(jià)值加上剩下的最大單位重量?jī)r(jià)值的物品裝滿剩余容量的價(jià)值和。算法首先檢查當(dāng)前擴(kuò)展結(jié)點(diǎn)的左兒子結(jié)點(diǎn)的可行性。如果該左兒子結(jié)點(diǎn)是可行結(jié)點(diǎn)，則將它

14、加入到子集樹和活結(jié)點(diǎn)優(yōu)先隊(duì)列中。當(dāng)前擴(kuò)展結(jié)點(diǎn)的右兒子結(jié)點(diǎn)一定是可行結(jié)點(diǎn)，僅當(dāng)右兒子結(jié)點(diǎn)滿足上界約束時(shí)才將它加入子集樹和活結(jié)點(diǎn)優(yōu)先隊(duì)列。當(dāng)擴(kuò)展到葉節(jié)點(diǎn)時(shí)為問(wèn)題的最優(yōu)值。2.4算法實(shí)現(xiàn)#include #include #include #define MaxSize 100 /初始化隊(duì)列長(zhǎng)度為100typedef struct QNodefloat weight; float value; intceng; struct QNode *parent; bool leftChild;QNode,*qnode; /定義隊(duì)列類型typedef structqnode QMaxSize; int fro

15、nt,rear;SqQueue; /定義隊(duì)列SqQueue sq;float bestv=0; /最優(yōu)解int n=0; /實(shí)際物品數(shù)float wMaxSize; /物品的重量float vMaxSize; /物品的價(jià)值int bestxMaxSize; / 存放最優(yōu)解qnode bestE;void InitQueue(SqQueue &sq ) /隊(duì)列初始化sq.front=1;sq.rear=1;bool QueueEmpty(SqQueue sq) /隊(duì)列判空if(sq.front=sq.rear)return true;elsereturn false;void EnQueue(S

16、qQueue &sq,qnode b)/結(jié)點(diǎn)入隊(duì)函數(shù)if(sq.front=(sq.rear+1)%MaxSize)cout隊(duì)滿，請(qǐng)修改隊(duì)列初始大小!weight=wt;b-value=vt;b-ceng=i;b-parent=parent;b-leftChild=leftchild;EnQueue(sq,b);void maxLoading(float w,float v,int c)float wt=0;float vt=0;int i=1; /當(dāng)前的擴(kuò)展結(jié)點(diǎn)所在的層float ew=0; /擴(kuò)展節(jié)點(diǎn)所相應(yīng)的當(dāng)前載重量float ev=0; /擴(kuò)展結(jié)點(diǎn)所相應(yīng)的價(jià)值qnode e=NULL;

17、qnode t=NULL;InitQueue(sq);EnQueue(sq,t); /空標(biāo)志進(jìn)隊(duì)列while (!QueueEmpty(sq)wt=ew+wi;vt=ev+vi;if (wt bestv)bestv=vt;EnQueue1(wt,vt,i,e,true); / 左兒子結(jié)點(diǎn)進(jìn)隊(duì)列EnQueue1(ew,ev,i,e,false); /右兒子總是可行；e=DeQueue(sq); / 取下一擴(kuò)展結(jié)點(diǎn)if (e = NULL)if (QueueEmpty(sq) break;EnQueue(sq,NULL); / 同層結(jié)點(diǎn)尾部標(biāo)志e=DeQueue(sq); / 取下一擴(kuò)展結(jié)點(diǎn)i+;ew=e-weight; /更新當(dāng)前擴(kuò)展結(jié)點(diǎn)的值ev=e-value;cout最優(yōu)價(jià)值為：bestvendlendl;cout最優(yōu)取值法：0;j-) /構(gòu)造最優(yōu)解bestxj=(bestE-leftChild?1:0);bestE=bestE-parent;for(int k=1;k=n;k+)if(bestxk=1)cout物品k：重量：wk 價(jià)值：vkendl;coutendl;void main()int c;float ewvMaxSize;cout-分支限界法求解0-1背包問(wèn)題-endl;cout