計(jì)算機(jī)算法概論

1、 算法設(shè)計(jì)與分析課程介紹 2）分治法及遞歸算法分析 2. 算法設(shè)計(jì) 4） 貪心法 5） 動(dòng)態(tài)規(guī)劃法 課程內(nèi)容 1.算法概述 3）圖的算法 1）窮舉法1 9）概率算法 10）近似算法 8） NP完全性 6） 回溯法 7） 分支-限界法 2學(xué)習(xí)要點(diǎn):理解算法的概念。理解什么是程序，程序與算法的區(qū)別和內(nèi)在聯(lián)系。掌握算法的計(jì)算復(fù)雜性概念。掌握算法漸近復(fù)雜性的數(shù)學(xué)表述。掌握用C/C+語言描述算法的方法。第一講 算法概述3 20世紀(jì)50年代，西方著名的詞典中還未曾收錄過算法(Algorithm)一詞，據(jù)西方數(shù)學(xué)史家考證， Algorithm取自于古代阿拉伯學(xué)者的名著復(fù)原和化簡的規(guī)則一書的作者的署名中的al

2、-Khwarizmi，而從作品名字中的al-jabr派生出了Algebra(代數(shù))一詞。隨著時(shí)間的推移， Algorithm這個(gè)詞的含義，已經(jīng)完全不同于它原來的含義了。一、什么是算法？ 4 一個(gè)算法是一個(gè)有窮規(guī)則的集合。這些規(guī)則規(guī)定了解決某一問題的一個(gè)運(yùn)算序列。同時(shí)，一個(gè)算法應(yīng)該具有五個(gè)特性：有窮性、可行性、確定性、輸入、輸出。 1. 有窮性：規(guī)則的有限性?；蛘哒f，求解問題的運(yùn)算序列，必須在有限的計(jì)算步后停止。 2. 可行性：每一計(jì)算步都是基本的、可實(shí)現(xiàn)的。 3. 確定性：每一條規(guī)則都是明確、無二義的。 算法定義： 5 5. 輸出（ 1）：算法產(chǎn)生與輸入相關(guān)的量。 4. 輸入（ 0）：算法開始

3、執(zhí)行之前指定初始值。二、算法的又一描述方式 設(shè)：四元組（Q, I, , f ). 其中：Q:狀態(tài)集合； I, ：Q的子集，分別代表輸入和輸出 f: 定義在Q之上的一個(gè)映射。 且有：若q ，則：f(q) = q。 6 1. 描述計(jì)算序列： 若對于I 的每一個(gè)輸入x,由f 定義一個(gè)計(jì)算序列： y0 , y1 , y2 , 。 其中：y0 = x; yk+1 = f( yk ) (k 0)。 若一個(gè)計(jì)算序列在第k步終止，且k是使yK 的最小整數(shù)，則稱yk是由x產(chǎn)生的輸出。 2. 描述算法： 一個(gè)算法是對于I 中所有輸入x, 都能在有窮步內(nèi)終止的一個(gè)計(jì)算序列。7f0y1Qf1y2 x Iykfk-18

4、三、程序(Program)程序是算法用某種程序設(shè)計(jì)語言的具體實(shí)現(xiàn)。程序可以不滿足算法的性質(zhì)(1)。例如操作系統(tǒng)，是一個(gè)在無限循環(huán)中執(zhí)行的程序，因而不是一個(gè)算法。操作系統(tǒng)的各種任務(wù)可看成是單獨(dú)的問題，每一個(gè)問題由操作系統(tǒng)中的一個(gè)子程序通過特定的算法來實(shí)現(xiàn)。該子程序得到輸出結(jié)果后便終止。9四、算法復(fù)雜性分析 算法復(fù)雜性 = 算法所需要的計(jì)算機(jī)資源算法的時(shí)間復(fù)雜性T(n)；算法的空間復(fù)雜性S(n)。其中n是問題的規(guī)模（輸入大?。?。10算法的時(shí)間復(fù)雜性（1）最壞情況下的時(shí)間復(fù)雜性 Tmax(n) = max T(I) | size(I)=n （2）最好情況下的時(shí)間復(fù)雜性 Tmin(n) = min T

5、(I) | size(I)=n （3）平均情況下的時(shí)間復(fù)雜性 Tavg(n) = 其中I是問題的規(guī)模為n的實(shí)例，p(I)是實(shí) 例I出現(xiàn)的概率。11假設(shè)某算法的計(jì)算時(shí)間是f(n)，其中變量n可以是輸入或輸出量，也可以是兩者之和，還可以是它們之一的某種測度(例如，數(shù)組的維數(shù)，圖的邊數(shù)等)。g(n)是在事前分析中確定的某個(gè)形式很簡單的函數(shù)，它是獨(dú)立于機(jī)器和語言的函數(shù)，而f(n)則與機(jī)器和語言有關(guān)。定義1.1 如果存在兩個(gè)正常數(shù)c和n0,對于所有的n n0，有 |f(n)|c|g(n)|記作f(n)=O(g(n)算法時(shí)間的漸近表示12當(dāng)說一個(gè)算法具有O(g(n)的計(jì)算時(shí)間時(shí)，指的是如果此算法用n值不變

6、的同一類數(shù)據(jù)在某臺(tái)機(jī)器上運(yùn)行時(shí)，所用的時(shí)間總是小于|g(n)|的一個(gè)常數(shù)倍。所以g(n)是計(jì)算時(shí)間f(n)的一個(gè)上界函數(shù)，f(n)的數(shù)量級就是g(n)。當(dāng)然，在確定f(n)的數(shù)量級時(shí)總是試圖求出最小的g(n)，使得f(n)=O(g(n)。13證明：取n0=1,當(dāng)n n0時(shí)，利用A(n)的定義和一個(gè)簡單的不等式，有|A(n)| |am|nm +|a1|n+|a0| (|am|+|am-1|/n+|a0|/nm)nm (|am|+|a0|)nm選取c= |am|+|a0|，定理立即得證。定理1.1 若A(n)=amnm+a1n+a0 是一個(gè)m次多項(xiàng)式，則A(n)=O(nm)。14 這個(gè)定理表明，變

7、量n的固定階數(shù)為m的任一多項(xiàng)式，與此多項(xiàng)式的最高階nm同階。因此計(jì)算時(shí)間為m階的多項(xiàng)式的算法，其時(shí)間都可用O(nm)來表示。事實(shí)上，只要將n0取得足夠大，可以證明只要c是比|am|大的任意一個(gè)常數(shù)，此定理都成立。15從計(jì)算時(shí)間上可以把算法分成兩類， 凡可用多項(xiàng)式來對其計(jì)算時(shí)間限界的算法，稱為多項(xiàng)式時(shí)間算法(polynomial time algorithm)；而計(jì)算時(shí)間用指數(shù)函數(shù)限界的算法稱為指數(shù)時(shí)間算法(exponential time algorithm)。16指數(shù)時(shí)間算法一般有以下幾種，它們關(guān)系為：O(2n) O(n!) O(nn)以下六種計(jì)算時(shí)間的多項(xiàng)式時(shí)間算法是最為常見的，其關(guān)系為：

8、O(1)O(longn) O(n) O(nlongn) O(n2) O(n3)因此，只要有人能將現(xiàn)在指數(shù)時(shí)間算法中的任何一個(gè)算法化簡為多項(xiàng)式時(shí)間算法，那就取得了一個(gè)偉大的成就!17算法分析中常見的復(fù)雜性函數(shù)18算法分析的基本法則非遞歸算法：（1）for / while 循環(huán)循環(huán)體內(nèi)計(jì)算時(shí)間*循環(huán)次數(shù)；（2）嵌套循環(huán)循環(huán)體內(nèi)計(jì)算時(shí)間*所有循環(huán)次數(shù)；（3）順序語句各語句計(jì)算時(shí)間相加；（4）if-else語句if語句計(jì)算時(shí)間和else語句計(jì)算時(shí)間的較大者。19問題求解(Problem Solving)證明正確性分析算法設(shè)計(jì)程序理解問題精確解或近似解選擇數(shù)據(jù)結(jié)構(gòu)算法設(shè)計(jì)策略設(shè)計(jì)算法20五、算法設(shè)計(jì)的例

9、子窮舉法例1.1 百雞問題公元5世紀(jì)末，數(shù)學(xué)家張丘建在算經(jīng)中，提出這樣一個(gè)問題：“雞翁一，值錢五；雞母一，值錢一；雞雛三，值錢一。百錢買百雞，問雞翁、母、雛各幾何”。21令a為公雞只數(shù)，b為母雞只數(shù)，c為小雞只數(shù) a+b+c=100 (1)5a+3b+c/3=100 (2)c%3=0 (3)上述百雞問題中，a、b、c的可能取值范圍為0-100，對在此范圍內(nèi)的a、b、c的所有組合進(jìn)行測試，凡是滿足上述3個(gè)約束方程的組合，都是問題的解。 22輸入：所購買的3種雞的總數(shù)目n輸出：滿足問題的解的數(shù)目k，公雞，母雞，小雞的只數(shù)g，m，s23void chicken_question(int n,int

10、&k,int g,int m,int s)int a,b,c;k=0;for(a=0;a=n;a+)for(b=0;b=n;b+)for(c=0;c=n;c+)if(a+b+c=n)&(5*a+3*b+c/3=n)&(c%3=0)gk=a;mk=b;sk=c; k+;24當(dāng)n=100時(shí)，內(nèi)循環(huán)體執(zhí)行次數(shù)大于100萬次考慮到n元錢只可以買到n/5只公雞，或n/3只母雞，有些組合可以不必考慮。而小雞的只數(shù)又與公雞及母雞的只數(shù)相關(guān)，內(nèi)循環(huán)可以省去。這樣，算法1.1中可以改為：25void chicken_problem(int n,int &k,int g,int m,int s)int i,j,a

11、,b,c;k=0;i=n/5;j=n/3;for(a=0;a=i;a+)for(b=0;b=j;b+)c=n-a-b;if(5*a+3*b+c/3=n)&(c%3=0)gk=a;mk=b;sk=c;k+26例1.2 貨郎擔(dān)問題某售貨員要到若干個(gè)城市銷售貨物，已知各城市之間的距離，要求售貨員選擇出發(fā)的城市及旅行路線，使每一個(gè)城市僅經(jīng)過一次，最后回到原出發(fā)城市，而總路程最短。如果對任意數(shù)目的n個(gè)城市，分別用1-n的數(shù)字編號，這個(gè)問題歸結(jié)為帶權(quán)有向圖中，尋找一條路徑最短 的哈密爾頓回路問題。思考：存儲(chǔ)的實(shí)現(xiàn)方法27售貨員的每一條路線，對應(yīng)于城市編號1,2, n的一個(gè)排列。用一個(gè)數(shù)組來存放這個(gè)排列中的

12、數(shù)據(jù)，數(shù)組中的元素依次存放旅行路線中的城市編號。n個(gè)城市具有n!個(gè)排列，售貨員共有n!條路線可供選擇。采用窮舉法逐一計(jì)算每一條路線的費(fèi)用，從中找出費(fèi)用最小的路線，便可求出問題的解。算法1.3 窮舉法版本的貨郎擔(dān)問題輸入：城市個(gè)數(shù)n，費(fèi)用矩陣c輸出：旅行路線t，最小費(fèi)用min28void salesman_problem(int n,float &min,int t,float c)int pn,i=1;float cost;min=MAx_FLoat_NUM;while(i=n!)產(chǎn)生n個(gè)城市的第i個(gè)排列于p;cost=路線p的費(fèi)用；if(cost0; i = 1,2,n）。判定：是否存在一種裝包方法，使裝入背包物品的總效益大于K？34 （1）計(jì)算機(jī)算法設(shè)計(jì)與分析 王曉東 電子工業(yè)出版社 2001年1月第1版 （2）算法設(shè)計(jì)與