計算機(jī)算法設(shè)計與分析畢業(yè)論文

計算機(jī)算法設(shè)計與分析25/25中國地質(zhì)大學(xué)研究生課程論文課程名稱:算法設(shè)計與分析教師姓名:戴光明研究生姓名:研究生學(xué)號:120161****研究生專業(yè):***********所在院系:計算機(jī)學(xué)院類別:A.博士B.碩士√C.進(jìn)修生日期:2017.01.13評語對課程論文的評語：平時成績：課程論文成績：總成績：評閱人簽名：注：1、無評閱人簽名成績無效；2、必須用鋼筆或圓珠筆批閱，用鉛筆閱卷無效；如有平時成績，必須在上面評分表中標(biāo)出，并計算入總成績。

目錄第一章 算法導(dǎo)引 4一、 算法及其特性 4二、 算法分析 4第二章 分治法 6一、 一般方法 6二、 二分檢索法 6三、 歸并分類 7四、 特斯拉森矩陣乘法 8五、 總結(jié) 8第三章 貪心算法 9一、 一般方法 9二、 背包問題 9三、 最小生成樹 10四、 單源點最短路徑 11第四章 動態(tài)規(guī)劃 12一、 優(yōu)化問題 12二、 一般原理 12三、 多段圖 12四、 每對結(jié)點間的最短路徑 14五、 最優(yōu)二分檢索樹 14六、 0-1背包問題 16七、 調(diào)度問題 16八、 TSP問題 17第五章 基本檢索與周游算法 18一、 一般方法 18二、 雙連通圖和深度優(yōu)先檢索 19三、 決策樹（博弈樹） 21第六章 回溯法 22第七章 分支限界法 22一、 一般方法 22二、 回溯法解0-1背包問題 22三、 分支限界法解0-1背包問題 23第八章 總結(jié) 24

算法導(dǎo)引課前題目：編寫程序：編寫兩個矩陣相乘的程序；如圖，菱形ABCD中，E是AD的中點，EF垂直于AC交CB的延長線于F，求證四邊形AFBE是平行四邊形。AAEDFBNMC圖1-1平行四邊形算法及其特性1、算法是什么？算法是計算的方法。2、什么是計算？計算是基于規(guī)則的符號串的變換；計算是基于規(guī)則的物理信息的變換；計算是基于規(guī)則的信息的變換。為了使計算機(jī)械化，圖靈提出了圖靈模型，在此基礎(chǔ)上將理論進(jìn)行技術(shù)實現(xiàn)，1946年誕生了第一臺計算機(jī)（讀寫頭、紙帶、四元組），在內(nèi)存條上進(jìn)行輸入輸出。算法的特性？無二義性：由于算法是由機(jī)器執(zhí)行的，所以算法的每一步都必須是確定的。能行性（可計算性與不可計算性）：算法的每一步機(jī)器都能夠執(zhí)行（計算機(jī)能夠解決的問題是有限的）。有限性（可計算性與計算復(fù)雜性）。算法分析算法分析就是分析算法的復(fù)雜性。算法分析的計算機(jī)模型：馮諾依曼計算機(jī)：串行執(zhí)行的計算機(jī)。均勻存儲：假設(shè)存儲量是夠的?；具\算的時間為整數(shù)。兩個重要的量：問題的規(guī)模n。頻率的計數(shù)f(n)。3、求時間復(fù)雜度：冒泡排序：BubblesortA(1->n)doi->1tondoj->i+1tonifA[j]<A[j]thenexchangeA[j]andA[j];continuej;continueI;printA(i->n);計算過程：f(n)=nC1+n(n+1)C2/2+nC3f(n)=n(C1+C2/2+C3)+n2C2/2對以上公式進(jìn)行簡化，表示如下：f(n)=n2C4+nC5（其中C4=C1+C2/2+C3，C5=C2/2）進(jìn)行分析后可知，運算的上界為：g(n)=O(n2)當(dāng)n>=n0時，若n足夠大，f(n)<=Cn2。2）漢諾塔：hanoi(intn,charleft,charmiddle,charright){if(n==1)printf(left->right)else{ hanoi(n-1,left,right,middle)print(left->right)hanoi(n-1,middle,left,right)}}設(shè)時間為f(n),規(guī)模為n:f(n)=2f(n-1)+C1=2(f(n-2)+C1)+C1=……=C12n所以g(n)=O(2n)。根據(jù)算法的時間界g(n)對算法進(jìn)行分類：兩類：多項式時間復(fù)雜度算法P（理論可行實際也可行）：O(c)<O(logn)<O(n)<O(nlogn)<O(n2)<O(n3)指數(shù)時間復(fù)雜度算法NP（理論可行實際不可行，需要限制規(guī)?；蛴媒平猓篛(2n)<O(n!)<O(nn)P->NP方法：智能算法(GA)、隨機(jī)過程。

分治法算法設(shè)計的三個基礎(chǔ)技術(shù)：由難到易的校正技術(shù)例，泰勒公式： 求2的值，每次取兩項，經(jīng)過多次泰勒公式展開可以得到方程中無線趨近合理的解。由粗到細(xì)的松弛技術(shù)例，割圓術(shù)求圓的面積，超松弛迭代：由大到小的分治技術(shù)（加權(quán)的方法）一般方法procedureDAN(p,q)globalifSmall(p,q) thenreturnG(p,q) elsem<-DIVIDE(p,q) return(Combine(DAN(p,m),DAN(m+1,q))) endifendDAN設(shè)算法規(guī)模為n=q-p+1，二分檢索法輸入n個有序數(shù)，輸出x把n個數(shù)輸入，放到二叉樹，使構(gòu)造的二叉樹樹的高度最小。ProcedureBINSRCH(A,n,x,j)integerlow,high,mid,j,n;low←1;high←n.whilelow≤highdomid←[low+high]/2case:x<A(mid):high←mid-1:x>A(mid):high←mid+1:else:j←mid;returnendcaserepeatj←0endBINSRCH設(shè)樹的高度為k，2k+1>=n，k=log(n-1)，所以k=O(logn)歸并分類procedureMERGESORT(low,high) integer iflow<high thenmid<-[(low+high)/2] callMERGESORT(low,mid) callMERGESORT(mid+1,high) callMERGE(low,mid,high) endifend設(shè)規(guī)模為n，則f設(shè)n=2kf例：輸入a，b，c進(jìn)行排序輸出結(jié)果：圖3-1排序樹 由于n個關(guān)鍵字有n!種排列，而每種排列可以是某種特定輸入下的分類結(jié)果，因此比較樹必定至少有n!個外結(jié)點，每個外結(jié)點表示一種可能的分類序列。 設(shè)樹的高度為h，則2h>=n! 設(shè)比較樹的最小高度為T(n)，則：n! 而當(dāng)n>1時有：n! 因此，對于n>=4有：T(n) 故以比較為基礎(chǔ)的分類算法的最壞情況的時間下界為O(nlogn)。特斯拉森矩陣乘法工程計算Ax=B，方程個數(shù)和自變量的個數(shù)關(guān)系： 當(dāng)方程個數(shù)多于自變量個數(shù)時：超定； 當(dāng)方程個數(shù)少于自變量個數(shù)時：欠定； 當(dāng)方程個數(shù)等于自變量個數(shù)是：適定。矩陣相乘：Cnl=AnmBml CT(n)=bn比較小7Tn/2+a根據(jù)斯特拉森的設(shè)計推理：T(n)=bn≤27Tn/2+dn求解此遞推關(guān)系式，得：Tn=a≤cn2總結(jié)分治法作用：由大化小求解（并行算法，空間換時間）；能有效的降低算法的時間復(fù)雜度。（O(n)->O(logn)，O(n2)->O(nlogn)，O(n3)->O(n2.81)）

貪心算法一般方法給定n個輸入，找n個輸入的一個子集，這個子集要滿足一些約束條件，滿足約束條件的子集可能會很多，把滿足約束條件的子集都可以叫可行解。我們根據(jù)要求去定義一個目標(biāo)函數(shù)，根據(jù)目標(biāo)函數(shù)，使目標(biāo)函數(shù)取得的極值的可行解叫最優(yōu)解。例：給定圖（V，E）->樹->樹的邊權(quán)值為最小->最小生成樹根據(jù)問題的特性去找一個量度標(biāo)準(zhǔn)，算法證明包括：證明量度標(biāo)準(zhǔn)、算法正確性證明。一般方法：ProcedureGREEDY(A,n)solution←?fori←1tondox←SELECT(A)ifFEASIBLE(solution,x)thensolution←UNION(solution,x)endifrepeatreturn(solution)end背包問題有一個背包，容量為M，現(xiàn)有物品N件，物品的質(zhì)量為W1，W2，，Wn，權(quán)值分別為P1，P2，...，Pn。1、問題分類設(shè)有N件物品分別裝入X1，X2，...，Xn（代表物品裝入的比例）。其中有，此時問題變?yōu)?、1背包問題，也就是該物品要么全部放入到背包中，要么不放入到背包中，此時為NP問題。若有，此時該問題變?yōu)椴糠直嘲鼏栴}，也就是該問題可以把物品只放入一部分到背包中，利用W/M進(jìn)行排序，按排序從大到小放入到背包中，直到背包容量裝滿，此時為P問題。2、函數(shù)表示 約束條件： 目標(biāo)函數(shù)： 利用上述的兩個表達(dá)函數(shù)，在滿足約束函數(shù)條件的前提下，求取目標(biāo)函數(shù)的最大值，實現(xiàn)背包問題的求解。例：n=3，M=20，（P1，P2，P3）=（25，24，15），（W1，W2，W3）=（18，15，10），（X1，X2，X3）=？量度標(biāo)準(zhǔn)：X1，X2，X3屬在0~1之間?？赡艿目尚薪馊缦拢?x1,x2,x3)①(1/2,1/3,1/4)16.524.25//沒有放滿背包//②(1,2/15,0)2028.2//效益由大到小順序裝包③(0,2/3,1)2031//質(zhì)量由大到小順序裝包④(0,1,1/2)2031.5單位質(zhì)量的效益值從大到小順序裝包（最優(yōu)）最小生成樹定義：設(shè)G(V,E)是一個無向連通圖。如果G的生成子圖T=(V,E’)是一棵生成樹，則稱T是G的一棵生成樹。當(dāng)樹的各邊權(quán)重之和達(dá)到最小時，則稱之為最小生成樹。Prim算法的基本思想是：設(shè)圖G頂點集合為U，首先任意選擇圖G中的一點作為起始點a，將該點加入集合V，再從集合U-V中找到另一點b使得點b到V中任意一點的權(quán)值最小，此時將b點也加入集合V；以此類推，現(xiàn)在的集合V={a，b}，再從集合U-V中找到另一點c使得點c到V中任意一點的權(quán)值最小，此時將c點加入集合V，直至所有頂點全部被加入V，此時就構(gòu)建出了一顆MST。普里姆算法：procedurePRIM(E,COST,n,T,mincost)//E是G的邊集。COST(n,n)是n結(jié)點圖G的成本鄰接矩陣，矩陣元素COST(i,j)是一個正實數(shù)，如果不存在邊(i,j)，則為＋∞。計算一棵最小生成樹并把它作為一個集合存放到數(shù)組T(1:n-1,2)中(T(i,1),T(i,2))是最小成本生成樹的一條邊。最小成本生成樹的總成本最后賦給mincost。NEAR(j)是樹中使得COST(j,NEAR(j))是對NEAR(j)所有選擇中的最小值//realCOST(n,n),mincostintegerNEAR(n),n,i,j,k,l,T(1:n-1,2)(k,l)←具有最小成本的邊mincost←COST(k,l)(T(l,1),T(l,2))←(k,l)fori←1tondo//將NEAR置初值//ifCOST(i,l)＜COST(i,k)thenNEAR(i)←lelseNEAR(i)←kendifrepeatNEAR(k)←NEAR(l)←0fori←2ton-1do//找T的其余n-2條邊//設(shè)j是NEAR(j)≠0且COST(j,NEAR(j))最小的下標(biāo)(T(i,1),T(i,2))←(j,NEAR(j))mincost←mincost+COST(j,NEAR(j))NEAR(j)←0fork←1tondo//修改NEAR//ifNEAR(k)≠0andCOST(k,NEAR(k))＞COST(k,j)thenNEAR(k)←jendifrepeatrepeatifmincost≥∞thenprint(‘nospanningtree’)endifendPRIM計算復(fù)雜性：O(n2)單源點最短路徑即一直的一個n結(jié)點有向圖G=（V,E）和邊的權(quán)函數(shù)C(e)，求由G中某指定結(jié)點V0到其他各個點的最短路徑。生成最短路徑的貪心算法：ProcedureSHORTEST(V,COST,DIST,n)//G是一個有n個結(jié)點的有向圖，它由其鄰接矩陣COST（n，n）表示，DIST（n，n）表示，DIST（j）被置以結(jié)點V到結(jié)點j的最短路徑的長度，這里1<j≤n;DIST(v)被置為0//BooleanS(1:n);realCOST(1:n,1:n),DIST(1:n)Integeru,v,n,num,i,wFori←1tondoS(i)←0;DIST(i)←COST(v,i)RepeatS(v)←1;DIST(v)←0Forsum←2ton-1doS(u)←1For所有S(w)=0的結(jié)點wdoDIST(w)←min(DIST(w),DIST(w)+COST(u,w))RepeatRepeatEnd生成最短路徑的貪心算法的計算時間是O（n2）。

動態(tài)規(guī)劃優(yōu)化問題1、分類線性優(yōu)化與非線性優(yōu)化約束優(yōu)化和無約束優(yōu)化確定性優(yōu)化和隨意性優(yōu)化動態(tài)優(yōu)化和靜態(tài)優(yōu)化單目標(biāo)優(yōu)化與多目標(biāo)優(yōu)化（最值與平衡解）2、優(yōu)化問題求解難度上可分為函數(shù)優(yōu)化：目標(biāo)函數(shù)參數(shù)優(yōu)化模型優(yōu)化：模型是什么樣的，建立模型一般原理用來求解優(yōu)化問題。特點：多階段決策滿足最優(yōu)解原理：不論初始決策是什么樣的，后面的決策相對初始決策產(chǎn)生一個最優(yōu)的決策。多段圖最優(yōu)性原理對多段圖問題成立，在多段圖中求從s到t的一條最小成本的路徑，可以看作是在k-2個段作出某種決策的結(jié)果，其中第i（1≤i≤k-2）次決策決定Vi+1中的哪個結(jié)點在這條路徑上。令源點s編號為1，然后依次對V2、V3…Vk-1中的結(jié)點編號，匯點t編號為n。如下圖所示：圖4-1一個5段圖1、由前向后推設(shè)BP(i,j)是一條從源點s到Vi中的結(jié)點j的最小成本路徑，BCOST(I,j)是這條路徑的成本則向后遞推式為對圖中所示的多段圖采用向后策略遞推：第2段BCOST(2,2)=9BCOST(2,3)=7BCOST(2,4)=3BCOST(2,5)=2第3段BCOST(3,6)=min{BCOST(2,2)+4,BCOST(2,3)+2}=9BCOST(3,7)=min{BCOST(2,2)+2,BCOST(2,3)+7,BCOST(2,5)+11}=11BCOST(3,8)=min{BCOST(2,4)+11,BCOST(2,5)+8}=10第4段BCOST(4,9)=min{BCOST(3,6)+6,BCOST(3,7)+4}=15BCOST(4,10)=min{BCOST(3,6)+5,BCOST(3,7)+3,BCOST(3,8)+5}=14BCOST(4,11)=min{BCOST(3,8)+6}=16第5段BCOST(5,12)=min{BCOST(4,9)+4,BCOST(4,10)+2,BCOST(4,11)+5}=16S到t的最小成本路徑的成本＝16最小路徑的求取：記BD(i,j)＝每一COST(i,j)的決策，即使COST(i-1,l)+c(l,j)取得最小值的l值。例：BD(3,6)=3，BD(3,7)=2，BD(3,8)=5，BD(4,9)=6，BD(4,10)=7，BD(4,11)=8，BD(5,12)=10根據(jù)D(5,12)的決策值向前遞推求取最小成本路徑：v4=BD(5,12)=10，v3=BD(4,BD(5,12))=7，v2=BD(3,BD(4,BD(5,12)))=BD(3,7)=2，故由s到t的最小成本路徑是：1→2→7→10→122、由后向前推設(shè)P(i,j)是一條從Vi中的結(jié)點j到匯點t的最小成本路徑，COST(i,j)是這條路徑的成本。設(shè)i表示Vi，j表示Vi中的結(jié)點號向前遞推式為對圖中所示的多段圖采用向前策略遞推：第4段COST(4,9)=c(9,12)=4COST(4,10)=c(10,12)=2COST(4,11)=c(11,12)=5第3段COST(3,6)=min{6+COST(4,9),5+COST(4,10)}=7COST(3,7)=min{4+COST(4,9),3+COST(4,10)}=5COST(3,8)=min{5+COST(4,10),6+COST(4,11)}=7第2段COST(2,2)=min{4+COST(3,6),2+COST(3,7),1+COST(3,8)}=7COST(2,3)=9COST(2,4)=18COST(2,5)=15第1段COST(1,1)=min{9+COST(2,2),7+COST(2,3),3+COST(2,4),2+COST(2,5)}=16S到t的最小成本路徑的成本＝16最小路徑的求?。河汥(i,j)＝每一COST(i,j)的決策即，使c(j,l)+COST(i+1,l)取得最小值的l值。例：D(3,6)=10,D(3,7)=10，D(3,8)=10，D(2,2)=7，D(2,3)=6，D(2,4)=8，D(2,5)=8，D(1,1)=2，根據(jù)D(1,1)的決策值向后遞推求取最小成本路徑：v2=D(1,1)=2，v3=D(2,D(1,1))=7，v4=D(3,D(2,D(1,1)))=D(3,7)=10，故由s到t的最小成本路徑是：1→2→7→10→12每對結(jié)點間的最短路徑設(shè)G=(V,E)是一個有n個結(jié)點的有向圖，C是G的成本鄰接矩陣，1≤i，j≤n，則C中元素有：則每對結(jié)點之間的最短路徑問題即是求滿足下述條件的矩陣A，A中的任一元素A(i,j)代表結(jié)點i到結(jié)點j的最短路徑長度。若利用單源最短路徑算法求解，那么計算n個結(jié)點的單源最短路徑的時間復(fù)雜度為O（n3）。若利用動態(tài)規(guī)劃策略求解，可以將求解G中每對結(jié)點之間的最短路徑問題轉(zhuǎn)化成一個多階段決策過程。設(shè)Ak(i,j)表示從i到j(luò)并且不經(jīng)過比k還大的結(jié)點的最短路徑長度，則A(i,j)=Ak(i,j)，即由i到j(luò)的最短路徑不通過比編號k還大的結(jié)點。若該路徑經(jīng)過結(jié)點k，則Ak(i,j)＝Ak-1(i,k)+Ak-1(k,j)，若該路徑不經(jīng)過結(jié)點k，則Ak(i,j)＝Ak-1(i,j)，故可得Ak(i,j)=min{Ak-1(i,j)，Ak-1(i,k)+Ak-1(k,j)}。每對結(jié)點間的最短路徑長度算法描述如下：procedureALL-PATHS(COST,A,n)//COST(n,n)是n結(jié)點圖的成本鄰接矩陣；A(i,j)是結(jié)點vi到vj的最短路徑的成本；COST(i,i)=0,1≤i≤n//integerI,j,k,n;realCOST(n,n),A(n,n)fori←1tondoforj←1tondoA(i,j)←COST(i,j)//用COST(i,j)對A0賦初值//repeatrepeatfork←1tondofori←1tondoforj←1tondoA(i,j)←min{A(i,j)，A(i,k)+A(k,j)}repeatrepeatrepeatendALL-PATHS計算時間為O（n3）。最優(yōu)二分檢索樹設(shè)給定的標(biāo)識符集合是{a1,a2,…,an}，并假定a1＜a2＜…＜an。設(shè)P(i)是對ai檢索的概率，Q(i)是正被檢索的標(biāo)識符X恰好滿足ai＜X＜ai+1，0≤i≤n（設(shè)a0=-∞,an+1=+∞)時的概率，即一種不成功檢索情況下的概率，則所有成功檢索的概率為，所有不成功檢索的概率為，考慮所有可能的成功和不成功檢索共2n+1種可能的情況，則有。設(shè)Ei為不成功檢索的等價類，則預(yù)期總的成本表示如下：其中左子樹、右子樹成本分別為：記則原二分檢索樹的預(yù)期成本可表示為：COST(T)=P(k)+COST(L)+COST(R)+W(0,k-1)+W(k,n)若T最優(yōu)二分檢索樹，則COST(L)和COST(R)將分別是包含a1,a2,…,ak-1和E0,E1,…,Ek-1及ak＋1,ak+2,…,an和Ek,Ek+1,…,En的最優(yōu)二分檢索(子)樹。如圖：aakLR

圖4-1二分檢索樹記由ai+1,ai+2,…,aj和Ei,Ei+1,…,Ej構(gòu)成的二分檢索樹的成本為C(i,j)，則對于最優(yōu)二分檢索樹T有，COST(L)=C(0,k-1)，COST(R)=C(k,n)，則對任何C(i,j)有當(dāng)j-i=m時，有n-m+1個C(i,j)要計算，C(i,j)的計算O(m)，每個C(i,j)要求找出m個量中的最小值，則n-m+1個C(i,j)的計算時間為O(nm-m2)，對所有可能的m，總計算時間為例：設(shè)P(4)=(3,3,1,1)，Q(4)=(2,3,1,1,1),w(i,i)=Q(i)，c(i,i)=0，R(i,i)=0。 w(0,1)=P(1)+Q(0)+Q(1)+w(0,0)=8c(0,1)=min{c(0,1)+c(1,1)}+w(0,1)=8 R(0,1)=1 w(1,2)=P(2)+Q(1)+Q(2)+w(1,1)=7 c(1,2)=min{c(1,1)+c(2,2)}+w(1,2)=7 R(1,2)=2 w(2,3)=P(3)+Q(4)+w(2,2)=3 c(2,3)=min{c(2,2)+c(3,3)}+w(2,3)=3 R(2,3)=3w(3,4)=P(4)+Q(5)+w(3,3)=3 c(3,4)=min{c(3,3)+c(4,4)}+w(3,4)=3 R(3,4)=4最后計算可以得出w(0,4)，c(0,4)，R(0,4)。計算所有的c(i,i)=0，R(i,i)的總時間：1≤m≤n0-1背包問題n件物品，背包容量為M，P1，P2，...，Pn為價值，W1，W2，，Wn為容量。裝包方法：目標(biāo)函數(shù)：約束條件：解答方法1：真值表方法（窮舉法）。解答方法2：設(shè)fn-1(x)代表包容量為x，裝W1，W2，，Wn-1后的最大效益值。當(dāng)將Wn裝入背包時：fn(X)=fn-1(X-wn)+pnfn(X)=max{fn-1(X),fn-1(X-wn)+pn} j代表1到n之間的數(shù)：fi(X)=max{fj-1(X),fj-1(X-wj)+pj}。例：n=3,(w1,w2,w3)=(2,3,4),(p1,p2,p3)=(1,2,3)，M=6，其遞推計算過程：由fi=fi-1(x-wi)+pi可得：f1(x)=max{f0(x),f0(x-2)+1}f2=max{f1(x),f1(x-3)+2}調(diào)度問題相同處理機(jī)調(diào)度PVM：n個作業(yè)，每個作業(yè)需時（t1，t2，…，tn），設(shè)有兩個相同的處理機(jī)，給出最優(yōu)調(diào)度方案，最優(yōu)調(diào)度方案所需時間為（t1+t2+…+tn）/2。其實是子集和數(shù)的問題，是一個NPhard問題。流水線調(diào)度：例：n+2個作業(yè)，m=3，t1,i=ai，t2,i=0，t3,i=ai，1≤i≤n；t1,n+1=T/2，t2,n+1=T，t3,i=0;t1,n+2=0，t2,n+2=T，t3,n+2=T/2。其中，T=i=1nai。t1,i表示第iP1t1,i,T/2t1,n+1t1,i,T/2P2t2,n+2t2,n+1P3tn,T/2t3,n+1t1,i,T/2第一臺機(jī)器所需時間:i=1第一臺機(jī)器所需時間:T+T第一臺機(jī)器所需時間:i=1例：有n=4個作業(yè)，每個作業(yè)兩個任務(wù)：（a1，a2，a3，a4）=（3，4，8，10）（b1，b2，b3，b4）=（6，2，9，15）→（b2a1a2b1a3b3a4TSP問題這是一個NPhard問題，時間復(fù)雜度為O（n!）。令g（i，S）為從i出發(fā)，經(jīng)過S（S圖中點集的子集），g（i，S）表示從i點出發(fā)，經(jīng)過S中所有的結(jié)點一次且僅一次，回到出發(fā)點i的最短路徑。g（i，{1,2,3，……，n}）=min{cik+g（k，S-{k}）}。例如對于矩陣：Cg（2，）=C21=5；g（3，）=C31=6；g（4，）=C41=8；g（2，{3}）=min{C23+g（3，）}=15；g（2，{4}）=min{C24+g（4，）}=18；g（3，{2}）=min{C32+g（2，）}=18；g（3，{4}）=min{C34+g（4，）}=20；g（4，{2}）=min{C42+g（2，）}=13；g（4，{3}）=min{C43+g（3，）}=15；g（2，{3，4}）=min{C23+g（3，{4}），C24+g（4，{3}）}=25；g（3，{2，4}）=min{C32+g（2，{4}），C34+g（4，{2}）}=25；g（4，{2，3}）=min{C42+g（2，{3}），C43+g（4，{2}）}=23；g（1，{2，3，4}）=min{C12+g（2，{3，4}），C13+g（3，{2，4}），C14+g（4，{2，3}）}=35；所以路徑為12431，時間復(fù)雜度O（2nn2）。基本檢索與周游算法一般方法樹的三種遍歷方式IAIABCDEGHF圖5-1給定二叉樹中根：FDHGIBEAC先根：ABDFGHIEC后根：FHIGDEBCA2、圖的生成樹112345678圖5-2給定連通圖112345678圖5-3寬度優(yōu)先生成樹112345678圖5-4深度優(yōu)先生成樹：雙連通圖和深度優(yōu)先檢索圖5-5雙連通分圖雙連通分圖深度優(yōu)先檢索樹：圖5-6雙連通分圖深度優(yōu)先檢索樹深度優(yōu)先生成樹中的虛線條代表逆邊，實線條代表樹邊，結(jié)點旁的數(shù)代表深度優(yōu)先樹用DFN表示。最低深度優(yōu)先數(shù)L（u）=min{DFN（u），min（L(w)|w是u的兒子）}，min{DFN（w）|（u,w）是一條逆邊}}，而且當(dāng)且僅當(dāng)u有一個使得L（w）>=DFN(u)的兒子w時，u是一個關(guān)節(jié)點。按后根的次序去各結(jié)點的最低深度優(yōu)先數(shù)DFN(u)是：L(10)=4L(9)=5L(6)=8L(8)=6L(7)=6L(5)=6L(2)=1L(3)=1L(4)=1L(1)=1對于關(guān)節(jié)點：除根結(jié)點以外的其它結(jié)點，L（w）≥DFN（u）且w是u的兒子的結(jié)點是關(guān)節(jié)點，當(dāng)然葉子結(jié)點不用考慮。結(jié)點3：兒子結(jié)點10有L(10)＝4而DFN(3)=3。結(jié)點2：兒子結(jié)點5有L(5)=6而DFN(2)＝6結(jié)點5：兒子結(jié)點6有L(6)＝8而DFN(5)＝7由連通圖的分類可知分為單連通分圖、雙連通分圖兩種類型，每一個圖上都有一定的關(guān)節(jié)點，要識別出圖上所有的關(guān)節(jié)點，根據(jù)各個關(guān)節(jié)點的連通性，找到符合條件的通路。對于寬度優(yōu)先搜索和深度優(yōu)先搜索，在這里，首先要對各個關(guān)節(jié)點之間的連接是單連通還是雙連通的關(guān)系進(jìn)行確定，再找到在一個連通圖中關(guān)結(jié)點之間是有實邊連接時，還有沒有逆邊連接，實邊用實線來表示，逆邊用虛線來表示，再根據(jù)DFS算法和BFS算法進(jìn)行實現(xiàn)，找出符合條件的最優(yōu)路徑。決策樹（博弈樹）對策樹類問題的本質(zhì)思想，是起源于博弈類游戲，比如，在一盤棋賽中，對弈各方都要根據(jù)當(dāng)前的局勢，分析和預(yù)見以后可能出現(xiàn)的局面，決定自己要采取的各種對策，以爭取更好的結(jié)果，博弈類問題是一種競爭，終局是表示為勝局、負(fù)局或者和局的情況的棋局，其它的都是非終止棋局。博弈過程在計算機(jī)里表示為對策樹，對棋局進(jìn)行判斷的評價函數(shù)E（X）是maxmin的過程，該過程可采用剪枝策略，如-截斷。截斷：如果一個求最小值位置的值判斷為小于或等于它父親的值，那么可以停止生成這個求最小值位置其余兒子的值，在這種規(guī)則下終止生成結(jié)點值的行動稱為截斷。截斷：如果一個求最大值位置的值判斷為大于或等于它父親的值，那么可以停止生成這個求最大值位置其余兒子的值，在這種規(guī)則下終止生成結(jié)點值的行動稱為截斷。

回溯法分支限界法回溯法：深度優(yōu)先搜索+限界函數(shù)分支限界法：寬度優(yōu)先搜索+限界函數(shù)+LC（最小成本）一般方法回溯法其實是求n元組的問題。所要求的解必須能表示成一個n-元組（x1，x2，…，xn），其中x1是取自某個有窮集Si。||Si||=mi，，m1*m2…mn。例：8-皇后問題8-皇后問題實際上是一個8元組問題。計算本質(zhì)上是基于規(guī)劃的一組符號的變換過程，是物理狀態(tài)的變遷，而其中的狀態(tài)及狀態(tài)的轉(zhuǎn)移（深度優(yōu)化和寬度優(yōu)化）本質(zhì)上就是離散狀態(tài)的變遷，對于離散問題，可以用迭代法來進(jìn)行解決，利用迭代法，公式有收斂和發(fā)散兩種情況，針對不同的情況，對問題進(jìn)行求解，再就是得用寬度優(yōu)先和限界函數(shù)兩者進(jìn)行求解，對于不同類型的問題采取不同的方法實現(xiàn)對問題的求解?；厮莘ń?-1背包問題設(shè)有0/1背包問題：n=8,M=110,p=[11,21,31,33,43,53,55,65]，w=[1,11,21,23,33,43,45,55]。即（x1，x2，…，x8）為28個元組，要從中找到能使價值最大的元組，xi∈{0，1}。 計算效益值使用的是0-1背包問題的效益不會超過部分背包問題的效益值，計算部分背包問題的效益值。圖7-1回溯法生成的樹很容易看出最優(yōu)解是(1，1，1，0，1，1，0，0)，得到的效益值是159。算法分析效率：狀態(tài)空間樹共有29-1=151個結(jié)點，而算法僅生成了35個結(jié)點，占總結(jié)點的6.85%。分支限界法解0-1背包問題例：已知背包問題n=4,M=15(p1,p2,p3,p4)=(10,10,12,18)(w1,w2,w3,w4)=(2,4,6,9)下面的數(shù)字：背包的下界u，上面的數(shù)字：背包的上界c’。 首先將根，即結(jié)點1作為E-結(jié)點，c’(1)=-38，u(1)=-32。由于它不是答案結(jié)點，因此過程LCBB置ans=0和U=-32+ε。擴(kuò)展此E-結(jié)點，生成它的兩個兒子結(jié)點2和3，放入活結(jié)點表中，結(jié)點2變成下一個E-結(jié)點，生成結(jié)點4和5。這樣一步一步向下擴(kuò)展，在找到結(jié)點8的情況下終止檢索，此時打印出值-38和路徑8，7，4，2，1，算法結(jié)束。圖7-2LC分支限界樹

總結(jié)經(jīng)過這段時間的學(xué)習(xí)，我不僅僅了解到了書本上的算法知識，還學(xué)到了很多算法的思想和設(shè)計思路。感謝戴老師這段時間的精彩講述，戴老師堅持親自板書的認(rèn)真態(tài)度打動了我。老師不僅僅是講述課本的內(nèi)容，同時還進(jìn)行擴(kuò)展，講圖靈的故事、阿爾法狗2的事情，還有老師探索多邊形的最小外切矩形的故事。學(xué)習(xí)這門課，我最大的收獲是學(xué)習(xí)理工科的人同時還要對社會科學(xué)的東西多了解，這樣自己才會有機(jī)會成為大師，而不僅僅是一個技術(shù)人員。在8節(jié)算法課里，我對算法的設(shè)計與分析有了更為深入的理解，并主要掌握了分治法、貪心算法、動態(tài)規(guī)劃法、回溯法和分枝限界算法等。其中分治法主要包括二分檢索、歸并分類、快速分類等，貪心算法則可以較好的解決背包問題、最小生成樹問題以及單源點最短路徑問題，而動態(tài)規(guī)劃法則可以較好的解決多段圖問題，每對結(jié)點之間的最短路徑問題，最優(yōu)二分檢索樹問題，0/1背包問題，矩陣連乘問題，TSP問題以及調(diào)度問題等，動態(tài)規(guī)劃將問題實例分解為相似的更小的子問題，并通過求解子問題產(chǎn)生全局最優(yōu)解。它與分治法和貪心法類似，但不同的是，貪心法的當(dāng)前選擇依賴于已經(jīng)做出的所有選擇，分治法中的各個子問題是獨立的子問題，因而一旦遞歸地求出各個子問題的解后，即可將子問題的解合并成問題的解?？傊煌乃惴ǜ饔刑攸c，各有優(yōu)劣，并在解決不同的實際問題中也帶給了我很多啟示。 最后，再次慶幸自己選擇了這門課，讓我在學(xué)習(xí)算法知識的同時，還學(xué)到了戴老師認(rèn)真的科研精神，向班上了學(xué)霸們學(xué)到了上課時認(rèn)真努力的態(tài)度。同時認(rèn)識到了自己的不足，在以后一定要見賢思齊，寫好程序，做好項目，學(xué)以致用?；贑8051F單片機(jī)直流電動機(jī)反饋控制系統(tǒng)的設(shè)計與研究基于單片機(jī)的嵌入式Web服務(wù)器的研究MOTOROLA單片機(jī)MC68HC（8）05PV8/A內(nèi)嵌EEPROM的工藝和制程方法及對良率的影響研究基于模糊控制的電阻釬焊單片機(jī)溫度控制系統(tǒng)的研制基于MCS-51系列單片機(jī)的通用控制模塊的研究基于單片機(jī)實現(xiàn)的供暖系統(tǒng)最佳啟停自校正（STR）調(diào)節(jié)器單片機(jī)控制的二級倒立擺系統(tǒng)的研究基于增強(qiáng)型51系列單片機(jī)的TCP/IP協(xié)議棧的實現(xiàn)基于單片機(jī)的蓄電池自動監(jiān)測系統(tǒng)基于32位嵌入式單片機(jī)系統(tǒng)的圖像采集與處理技術(shù)的研究基于單片機(jī)的作物營養(yǎng)診斷專家系統(tǒng)的研究基于單片機(jī)的交流伺服電機(jī)運動控制系統(tǒng)研究與開發(fā)基于單片機(jī)的泵管內(nèi)壁硬度測試儀的研制基于單片機(jī)的自動找平控制系統(tǒng)研究基于C8051F040單片機(jī)的嵌入式系統(tǒng)開發(fā)基于單片機(jī)的液壓動力系統(tǒng)狀態(tài)監(jiān)測儀開發(fā)模糊Smith智能控制方法的研究及其單片機(jī)實現(xiàn)一種基于單片機(jī)的軸快流CO〈,2〉激光器的手持控制面板的研制基于雙單片機(jī)沖床數(shù)控系統(tǒng)的研究基于CYGNAL單片機(jī)的在線間歇式濁度儀的研制基于單片機(jī)的噴油泵試驗臺控制器的研制基于單片機(jī)的軟起動器的研究和設(shè)計基于單片機(jī)控制的高速快走絲電火花線切割機(jī)床短循環(huán)走絲方式研究基于單片機(jī)的機(jī)電產(chǎn)品控制系統(tǒng)開發(fā)基于PIC單片機(jī)的智能手機(jī)充電器基于單片機(jī)的實時內(nèi)核設(shè)計及其應(yīng)用研究基于單片機(jī)的遠(yuǎn)程抄表系統(tǒng)的設(shè)計與研究基于單片機(jī)的煙氣二氧化硫濃度檢測儀的研制基于微型光譜儀的單片機(jī)系統(tǒng)單片機(jī)系統(tǒng)軟件構(gòu)件開發(fā)的技術(shù)研究基于單片機(jī)的液體點滴速度自動檢測儀的研制基于單片機(jī)系統(tǒng)的多功能溫度測量儀的研制基于PIC單片機(jī)的電能采集終端的設(shè)計和應(yīng)用基于單片機(jī)的光纖光柵解調(diào)儀的研制氣壓式線性摩擦焊機(jī)單片機(jī)控制系統(tǒng)的研制基于單片機(jī)的數(shù)字磁通門傳感器基于單片機(jī)的旋轉(zhuǎn)變壓器-數(shù)字轉(zhuǎn)換器的研究基于單片機(jī)的光纖Bragg光柵解調(diào)系統(tǒng)的研究單片機(jī)控制的便攜式多功能乳腺治療儀的研制基于C8051F020單片機(jī)的多生理信號檢測儀基于單片機(jī)的電機(jī)運動控制系統(tǒng)設(shè)計Pico專用單片機(jī)核的可測性設(shè)計研究基于MCS-51單片機(jī)的熱量計基于雙單片機(jī)的智能遙測微型氣象站MCS-51單片機(jī)構(gòu)建機(jī)器人的實踐研究基于單片機(jī)的輪軌力檢測基于單片機(jī)的GPS定位儀的研究與實現(xiàn)基于單片機(jī)的電液伺服控制系統(tǒng)用于單片機(jī)系統(tǒng)的MMC卡文件系統(tǒng)研制基于單片機(jī)的時控和計數(shù)系統(tǒng)性能優(yōu)化的研究基于單片機(jī)和CPLD的粗光柵位移測量系統(tǒng)研究單片機(jī)控制的后備式方波UPS提升高職學(xué)生單片機(jī)應(yīng)用能力的探究基于單片機(jī)控制的自動低頻減載裝置研究基于單片機(jī)控制的水下焊接電源的研究基于單片機(jī)的多通道數(shù)據(jù)采集系統(tǒng)基于uPSD3234單片機(jī)的氚表面污染測量儀的研制基于單片機(jī)的紅外測油儀的研究96系列單片機(jī)仿真器研究與設(shè)計基于單片機(jī)的單晶金剛石刀具刃磨設(shè)備的數(shù)控改造基于單片機(jī)的溫度智能控制系統(tǒng)的設(shè)計與實現(xiàn)基于MSP430單片機(jī)的電梯門機(jī)控制器的研制基于單片機(jī)的氣體測漏儀的研究基于三菱M16C/6N系列單片機(jī)的CAN/USB協(xié)議轉(zhuǎn)換器基于單片機(jī)和DSP的變壓器油色譜在線監(jiān)測技術(shù)研究基于單片機(jī)的膛壁溫度報警系統(tǒng)設(shè)計基于AVR單片機(jī)的低壓無功補(bǔ)償控制器的設(shè)計基于單片機(jī)船舶電力推進(jìn)電機(jī)監(jiān)測系統(tǒng)基于單片機(jī)網(wǎng)絡(luò)的振動信號的采集系統(tǒng)基于單片機(jī)的大容量數(shù)據(jù)存儲技術(shù)的應(yīng)用研究基于單片機(jī)的疊圖機(jī)研究與教學(xué)方法實踐基于單片機(jī)嵌入式Web服務(wù)器技術(shù)的研究及實現(xiàn)基于AT89S52單片機(jī)的通用數(shù)據(jù)采集系統(tǒng)基于單片機(jī)的多道脈沖幅度分析儀研究機(jī)器人旋轉(zhuǎn)電弧傳感角焊縫跟蹤單片機(jī)控制系統(tǒng)基于單片機(jī)的控制系統(tǒng)在PLC虛擬教學(xué)實驗中的應(yīng)用研究基于單片機(jī)系統(tǒng)的網(wǎng)絡(luò)通信研究與應(yīng)用基于PIC16F877單片機(jī)的莫爾斯碼自動譯碼系統(tǒng)設(shè)計與研究基于單片機(jī)的模糊控制器在工業(yè)電阻爐上的應(yīng)用研究基于雙單片機(jī)沖床數(shù)控系統(tǒng)的研究與開發(fā)基于Cygnal單片機(jī)的μC/OS-Ⅱ的研究HYPERLINK"/detail.htm?