算法設(shè)計(jì)期末總結(jié)

1、第一部分：算法基礎(chǔ)1、算法五個(gè)特征：零個(gè)或多個(gè)輸入、至少一個(gè)輸出、確定性、能行性、有窮性。2、算法意義：算法就是求解一類問題的任意一種特殊的方法。3、算法與程序的聯(lián)系與區(qū)別：聯(lián)系：算法+數(shù)據(jù)結(jié)構(gòu)=程序，算法是程序設(shè)計(jì)的核心，算法的好壞程度上決定了一個(gè)程序的效率。一個(gè)好的算法可以降低一個(gè)程序運(yùn)行的時(shí)間復(fù)雜度和空間復(fù)雜度。區(qū)別：算法是解決問題的步驟，程序是算法的代碼實(shí)現(xiàn)依靠程序來完成功能，程序作為算法的靈魂。程序是結(jié)果算法是手段，編寫一個(gè)同樣功能的程序，使用不同的算法，可以讓程序的體積和效率有很大的該變。4、好算法的特性：正確性、簡(jiǎn)明性、效率、最優(yōu)性（健壯性、可靠性）。5、影響程序運(yùn)行的時(shí)間因素：

2、程序所依賴的算法、問題規(guī)模和輸入數(shù)據(jù)、計(jì)算機(jī)系統(tǒng)性能6、時(shí)間復(fù)雜性分為3種情況，最好情況、平均情況、最壞情況，可操作性最好，最具有實(shí)際價(jià)值的是最壞情況下的時(shí)間復(fù)雜性。7、漸進(jìn)表示法：大O幾號(hào)（漸進(jìn)上界）：定義：設(shè)函數(shù)f(n)和g(n)是定義在非負(fù)整數(shù)集合上的正函數(shù)，如果存在兩個(gè)正常數(shù)c和n0,使得當(dāng)n>=n0時(shí)，有f(n)<=cg(n)，則記做法法f(n)=O(g(n),成為大O記號(hào)（big Oh notation）【算法設(shè)計(jì)與分析c+描述第二版陳惠南p19面例題】。記號(hào)（漸進(jìn)緊界）：定義：設(shè)有函數(shù)f(n)和g(n)是定義在非負(fù)整數(shù)集合上的正函數(shù)，如果存在兩個(gè)正常數(shù)c和n0，使得當(dāng)

3、n>= n0時(shí)，有f(n)>=cg(n),則記做f(n)= (g(n),稱為記號(hào)（omega notation）【算法設(shè)計(jì)與分析c+描述第二版陳惠南p20面例題】。記號(hào)（漸進(jìn)下界）：定義：設(shè)有函數(shù)f(n)和g(n)是定義在非負(fù)整數(shù)集合上的正整數(shù)，如果存在正常數(shù)c1,c2和n0,使得當(dāng)n>=n0時(shí)，有c1g(n)<=f（n）<=c2g(n),則記做f(n)= (g(n),稱為記號(hào)（Theta natation）。小o記號(hào)定義：f(n)=o(g(n)當(dāng)且僅當(dāng)f(n)=o(g(n)且f(n)!= (g(n)。*漸進(jìn)表示法*設(shè)有f(n)和g(n),分析。1】f(n)=20

4、n+logn,g(n)=n+nlog3n;當(dāng)時(shí)，所以，?？蛇x ，。對(duì)于，即。注意：是f(n)和g(n)的關(guān)系。2】f（n）=n2/logn,g(n)=nlog2n;當(dāng) 時(shí)，所以 ，?？蛇x ，。對(duì)于 ，即 。3】f(n)=(logn)logn,g(n)=n/logn;因?yàn)?，。當(dāng) 時(shí)，。所以，可選 ，對(duì)于，即 第二部分：分治法第三部分：貪心法背包問題：n=5,m=11,(p0p4)=(8,6,15,6,3) (w0w5)=(2,3,5,2,3),最優(yōu)量度標(biāo)準(zhǔn)：優(yōu)先選擇單位重量收益最大的物品放入背包。(p0/w0, p1/w1, p2/w2, p3/w3,p4/w4)=(4,2,3,3,1)最優(yōu)解

5、為：(x0,x1,x2,x3,x4,x5,x6) =(1,2/3,1,1,0)最大收益為:8+6*2/3+15+6)=33分析所有最優(yōu)解。1、簡(jiǎn)述貪心算法的思想策略、算法特點(diǎn)，以及它所具有的兩種性質(zhì)各是什么？思想策略: 貪心法是一種求解最優(yōu)化問題的算法設(shè)計(jì)策略。 算法特點(diǎn): 貪心法是通過分步?jīng)Q策的方法來求解問題的, 貪心法在求解問題的每一步上做出某種決策, 產(chǎn)生N 元組解的一個(gè)分量。性質(zhì): 貪心選擇性質(zhì)和最優(yōu)子結(jié)構(gòu)性質(zhì)。2、簡(jiǎn)要說明貪心算法的兩個(gè)基本要素。貪心選擇性質(zhì): 貪心法要求根據(jù)題意, 選定一種最優(yōu)量度標(biāo)準(zhǔn), 作為選擇當(dāng)前分量值的依據(jù), 這種在貪心法每一步上用做決策依據(jù)的選擇準(zhǔn)則被稱為最

6、優(yōu)量度標(biāo)準(zhǔn)或貪心準(zhǔn)則, 也稱貪心選擇性質(zhì)。最優(yōu)子結(jié)構(gòu)性質(zhì): 當(dāng)一個(gè)問題的最優(yōu)解中包含了子問題的最優(yōu)解時(shí), 則稱問題具有最優(yōu)子結(jié)構(gòu)特性。3、在解決最優(yōu)化問題的求解過程中，采用一種局部最優(yōu)策略，把問題范圍和規(guī)模縮小，最后把每一步的結(jié)果合并起來得到一個(gè)全局最優(yōu)解，這種算法稱為 貪心法 法。4、生成最小代價(jià)生成樹：第四部分：動(dòng)態(tài)規(guī)劃法1、利用最優(yōu)子結(jié)構(gòu)，自底向上從子問題的最優(yōu)解逐步構(gòu)造出整個(gè)問題的最優(yōu)解，這種算法稱為 動(dòng)態(tài)規(guī)劃法 法。2、動(dòng)態(tài)規(guī)劃算法的兩個(gè)基本要素是 最優(yōu)子結(jié)構(gòu)特性 和 重疊子問題 。3、矩陣連乘：*詳解sij*以此題為例，A0,A1，A2，A3,A4，A5.看b圖0到3，從2處斷開，

7、就得出（A0，A1，A2）（A3，A4，A5）再觀察b圖0到2，從0處斷開，于是就得出（A0（A1，A2）(A3，A4，A5) 3->4，從3處斷開，于是就得出（A0（A1，A2）(A3（A4，A5）)例題：1】p0=20, p1=10, p2=8, p3=5, p4=40, mii=0，sii=i，i=0,1,2,3; m01=minm00+ m11+20*10*8=1600，s01=0； m12=minm11+ m22+10*8*5=400，s12=1； m23=minm22+ m33+8*5*40=1600， s23=2； 計(jì)算過程： m02=minm00+ m12+20*10*5

8、, m01+ m22+20*8*5, =min400+1000,1600+800=1400，s02=0 ； m13=minm11+ m23+10*8*40, m12+ m33+10*5*40, =min1600+3200,400+2000=2400，s13=2 ； m03=minm00+ m13+20*10*40, m01+ m23+20*8*40, m02+ m33+20*5*40 =min2400+8000,1600+1600+6400,1400+4000=5400，s03=2*完全加括號(hào)的形式：（A0 （A1 A2 ）A3 ）第五部分：回溯法1、 回溯法 法在問題的解空間樹中，按深度優(yōu)先

9、策略，從根結(jié)點(diǎn)出發(fā)搜索解空間樹。第六部分：分枝界限法1、分枝限界法 法在問題的解空間樹中，按廣度優(yōu)先策略，從根結(jié)點(diǎn)出發(fā)搜索解空間。*附加*回溯法和分支限界法的不同之處。通過搜索狀態(tài)空間樹的方法求問題答案的方法可分為兩類: 深度優(yōu)先搜索和廣度優(yōu)先搜索. 如果在運(yùn)用搜索算法是使用剪枝函數(shù), 便成為回溯法和分枝限界法. 一般而言, 回溯法的求解目標(biāo)是在狀態(tài)空間樹上找出滿足約束條件的所有解, 而分枝限界法的求解目標(biāo)則是找出滿足約束條件的一個(gè)解, 或是在滿足約束條件的解中找出最優(yōu)解.遞推關(guān)系式#include <iostream> #include<queue>using nam

10、espace std; #define MAX 99 /定義無窮大 struct Nodeint length; /權(quán)值（源點(diǎn)到該結(jié)點(diǎn)的路徑長(zhǎng)度）int i; /結(jié)點(diǎn)編號(hào)friend bool operator <(Node a,Node b) /運(yùn)算符重載（作用：權(quán)值小的結(jié)點(diǎn)優(yōu)先級(jí)高）return a.length>b.length;class Graph public: void ShorestPaths(int); void ShowDist(); Graph(); Graph();private: int n; /圖的節(jié)點(diǎn)個(gè)數(shù) int *prev; /存放頂點(diǎn)的前驅(qū)節(jié)點(diǎn) i

11、nt *c; /存放圖的鄰接矩陣 int *dist; /存放源點(diǎn)到各個(gè)頂點(diǎn)的距離 ; Graph:Graph() int wi = 0; int yi = 0; int s;int i,j,m; cout<<"請(qǐng)輸入圖的節(jié)點(diǎn)個(gè)數(shù)：" cin>>n; cout<<"請(qǐng)輸入圖的邊的條數(shù)：" cin>>s; c = new int*n; for (wi = 0; wi < n; wi+) cwi = new intn; dist = new intn; prev = new intn; for (wi =

12、 0; wi <n; wi+) /初始化鄰接矩陣 for (yi = 0; yi < n; yi+) cwiyi = MAX; cout<<"請(qǐng)輸入圖的邊( i，j，ci,j ) "<< endl;/ 以鄰接矩陣存儲(chǔ)，(無窮大（99）代表節(jié)點(diǎn)間無邊 for (wi = 1; wi <=s; wi+) cin >>i>>j>>m;cij = m; for (wi = 0; wi < n; wi+) /初始化數(shù)組 distwi = MAX; prevwi = -1; Graph:Graph()

13、for(int i=0;i<n;i+) delete ci; delete c;delete dist;delete prev;void Graph:ShowDist() cout <<endl<< "從源點(diǎn)到各節(jié)點(diǎn)的最短路徑:" << endl; int i = 0; int temp = 0; for (i = 0; i < n; i+) cout << "dist" << i << " = " << disti << en

14、dl; cout << "從源點(diǎn)到終點(diǎn)的最短路徑長(zhǎng)度為:" << distn-1 << endl; cout << "其路徑為：" temp = n-1; while(temp >=0 ) cout << temp; if(temp) cout << "<-" temp = prevtemp; cout << endl; void Graph:ShorestPaths(int v) priority_queue<Node> H;

15、 /定義優(yōu)先隊(duì)列（最小堆） Node E; /擴(kuò)展節(jié)點(diǎn) E.i = v; E.length = 0; distv = 0; cout<<"當(dāng)前擴(kuò)展節(jié)點(diǎn)："<<E.i<<"，權(quán)重："<<E.length<<endl; while (true) int j; for (j = 0; j < n; j+) /查找該結(jié)點(diǎn)的所有鄰接點(diǎn) if (cE.ij != MAX) && (E.length + cE.ij < distj) ) /鄰接點(diǎn) distj = E.length + cE.ij; prevj = E.i; /記錄前驅(qū)結(jié)點(diǎn)/加入活結(jié)點(diǎn)優(yōu)先隊(duì)列 ,若節(jié)點(diǎn)為終點(diǎn)，則不加入活結(jié)點(diǎn)隊(duì)列 if (j != n-1) Node N; N.i = j; N.length = distj; H.push(N); /N結(jié)點(diǎn)入隊(duì) cout<<"入隊(duì)結(jié)點(diǎn)："<<N.i<<",權(quán)重："<<N.length<<endl; /forif(!H.empty() E=H.top();/出隊(duì) cout<<&quo