【正文】 于 AC 交 CB 的延長(zhǎng)線于 F，求證四邊形AFBE 是平行四邊形。 什么是計(jì)算？ 1) 計(jì)算是基于規(guī)則的符號(hào)串的變換； 2) 計(jì)算是基于規(guī)則的物理信息的變換； 3) 計(jì)算是基于規(guī)則的信息的變換。 算法的特性 ？ 4) 無二義性：由于算法是由機(jī)器執(zhí)行的，所以算法的每一步都必須是確定的。 6) 有限性 （可計(jì)算性與計(jì)算復(fù)雜性） 。 算法分析的計(jì)算機(jī)模型： 1） 馮諾依曼計(jì)算機(jī)：串行執(zhí)行的計(jì)算機(jī)。 3） 基本運(yùn)算的時(shí)間為整數(shù)。 2） 頻率的計(jì)數(shù) f(n)。 continue j。 print A(in)。 2） 漢諾塔： hanoi (int n,char left,char middle,char right) { if (n==1) printf (left right) else { hanoi (n1, left, right, middle) print( left right) hanoi (n1, middle, left, right) } } 設(shè)時(shí)間為 f(n),規(guī)模為 n: f(n) = 2f(n1)+ C1=2(f(n2)+ C1)+ C1=…… = C12n 所以 g(n)=O(2n)。 計(jì)算機(jī)算法設(shè)計(jì)與分析 6 / 24 第二章 分治法 算法設(shè)計(jì)的三個(gè)基礎(chǔ)技術(shù) ： 1. 由難到易的校正技術(shù) 例， 泰勒公式： 20 0 0 0 0( ) ( ) 39。39。 2. 由粗到細(xì)的松弛技術(shù) 例，割圓術(shù)求圓的面積 ，超松弛迭代 ： 3 0 7 2 1 9 2 1 9 2 9 636 ()105S S S S? ? ? 3. 由大到小的分治技術(shù) （加權(quán)的方法） 一、 一般方法 procedure DAN(p,q) global if Small (p,q) then return G(p,q) else mDIVIDE(p,q) return (Combine(DAN(p,m),DAN(m+1,q))) endif end DAN 設(shè)算法規(guī)模為 n=qp+1， T(n)= { ??(??) ,??足夠小2T(n2)+f(??) ， n為其它 二、 二分檢索法 輸入 n 個(gè)有序數(shù)，輸出 x 把 n 個(gè)數(shù)輸入，放到二叉樹，使構(gòu)造的 二叉樹樹的高度最小。 low←1。 return endcase repeat j←0 計(jì)算機(jī)算法設(shè)計(jì)與分析 7 / 24 end BINSRCH 設(shè)樹的高度為 k， 2k+1=n， k=log(n1)，所以 k=O(logn) 三、 歸并分類 procedure MERGESORT(low, high) integer if low high then mid [(low+ high)/2] call MERGESORT(low, mid) call MERGESORT(mid+1,high) call MERGE(low, mid, high) end if end 設(shè)規(guī)模為 n，則 f(n) = { ?? ,?? = 12f(n)+???? ,?? 1 設(shè) n=2k f(n) = 2f(??2) +???? = 22f( ??22)+2???? = ? = 2????(1)+knc = an+nlogC 例：輸入 a， b， c 進(jìn)行排序輸出結(jié)果： a ba cb c b ca cNNY Na , b , cc , b , aYYa , b , c a , b , c a , b , c a , b , cYNYN輸 入 a ， b ， c 圖 31 排序樹 由于 n 個(gè)關(guān)鍵字有 n!種排列，而每種排列可以是某種特定輸入下的分類結(jié)果，因此比較樹必定至少有 n!個(gè)外結(jié)點(diǎn)，每個(gè)外結(jié)點(diǎn)表示一種可能的分類序列。 計(jì)算機(jī)算法設(shè)計(jì)與分析 8 / 24 四、 特斯拉森矩陣乘法 工程計(jì)算 Ax=B，方程個(gè)數(shù)和自變量的個(gè)數(shù)關(guān)系： 當(dāng)方程個(gè)數(shù)多于自變量個(gè)數(shù)時(shí)：超定； 當(dāng)方程個(gè)數(shù)少于自變量個(gè)數(shù)時(shí)：欠定； 當(dāng)方程個(gè)數(shù)等于自變量個(gè)數(shù)是：適定。 根據(jù)斯特拉森的設(shè)計(jì)推理： T(n)={ ?? n≤27??(??/2)+????2 ?? 2其中， a， b 是常數(shù)。 （ O(n) O(logn)， O(n2) O(nlogn)， O(n3) O()） 計(jì)算機(jī)算法設(shè)計(jì)與分析 9 / 24 第三章 貪心算法 一、 一般方法 給定 n 個(gè)輸入，找 n 個(gè)輸入的一個(gè)子集，這個(gè)子集要滿足一些約束條件，滿足約束條件的子集可能會(huì)很多，把滿足約束條件的子集都可以叫可行解。 例：給定圖（ V， E） 樹 樹的邊權(quán)值為最小 最小生成樹 根據(jù)問題的特性去找一個(gè)量度標(biāo)準(zhǔn) ，算法證明包括：證明量度標(biāo)準(zhǔn)、算法正確性證明。 問題分類 設(shè)有 N 件物品分別裝入 X1， X2， ...， Xn（代表物品裝入的比例）。 若有 ? ?0,1ix? ，此時(shí) 該問題變?yōu)椴糠直嘲鼏栴}，也就是該問題可以把物品只放入一部分到背包中，利用 W/M 進(jìn)行排序，按排序從大到小放入到背包中，直到背包容量裝滿 ，此時(shí)為 P 問題。 例： n=3， M=20，（ P1， P2， P3） =（ 25， 24， 15），（ W1， W2， W3） =（ 18， 15， 10），（ X1， 計(jì)算機(jī)算法設(shè)計(jì)與分析 10 / 24 X2， X3） =？ 量度標(biāo)準(zhǔn)： X1， X2， X3 屬在 0~1 之間。如果 G 的生成子圖 T=(V,E’)是一棵生成樹，則稱 T是 G 的一棵生成樹。 Prim 算法的基本思想是： 設(shè)圖 G 頂點(diǎn)集合為 U，首先任意選擇圖 G 中的一點(diǎn)作為起始點(diǎn) a，將該點(diǎn)加入集合 V，再從集 合 UV中找到另一點(diǎn) b 使得點(diǎn) b 到 V 中任意一點(diǎn)的權(quán)值最小，此時(shí)將 b 點(diǎn)也加入集合 V；以此類推，現(xiàn)在的集合 V={a， b}，再從集合 UV 中找到另一點(diǎn) c 使得點(diǎn) c 到 V 中任意一點(diǎn)的權(quán)值最小，此時(shí)將 c 點(diǎn)加入集合 V，直至所有頂點(diǎn)全部被加入 V，此時(shí)就構(gòu)建出了一顆 MST。 COST(n,n)是 n 結(jié)點(diǎn)圖 G 的成本鄰接矩陣 ， 矩陣元素 COST(i,j)是一個(gè)正實(shí)數(shù) ， 如果不存在邊 (i,j)， 則為 ＋∞ 。最小成本生成樹的總成本最后賦給mincost。 生成最短路徑的貪心算法： Procedure SHORTEST (V,COST,DIST,n) //G 是一個(gè)有 n 個(gè)結(jié)點(diǎn)的有向圖，它由其鄰接矩陣 COST（ n， n）表示， DIST（ n， n）表示，DIST（ j）被置以結(jié)點(diǎn) V 到結(jié)點(diǎn) j 的最短路徑的長(zhǎng)度，這里 1j≤n。 real COST(1:n,1:n),DIST(1:n) Integer u,v,n,num,i,w For i←1 to n do S(i) ←0。 DIST(v) ←0 For sum←2 to n1 do S(u) ←1 For 所有 S(w)=0 的結(jié)點(diǎn) w do DIST(w) ←min(DIST(w), DIST(w)+ COST(u,w)) Repeat Repeat End 生成最短路徑的貪心算法 的計(jì)算時(shí)間是 O（ n2）。特點(diǎn)： (1) 多階段決策 (2) 滿足最優(yōu)解原理：不論初始決策是什么樣的，后面的決策相對(duì)初始決策產(chǎn)生一個(gè)最優(yōu)的決策。 令源點(diǎn) s 編號(hào)為 1，然后依次對(duì) V V3… Vk1 中的結(jié)點(diǎn)編號(hào)，匯點(diǎn) t 編號(hào)為n。 例： 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→12 由后向前推 設(shè) P(i,j)是一條從 Vi 中的結(jié)點(diǎn) j 到匯點(diǎn) t 的最小成本路徑， COST(i,j)是這條路徑的成本。 例： 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 1( , )( , ) m in { ( , ) ( 1 , ) }ilvj l EC O S T i j c j l C O S T i l?? ?? ? ? 計(jì)算機(jī)算法設(shè)計(jì)與分析 14 / 24 四、 每對(duì)結(jié)點(diǎn)間的最短路徑 設(shè) G=(V,E)是一個(gè)有 n 個(gè)結(jié)點(diǎn)的有向圖， C 是 G 的成本鄰接矩陣， 1≤ i， j≤ n，則 C 中元素有： 則 每對(duì)結(jié)點(diǎn)之間的最短路徑問題 即是 求滿足下述條件的矩陣 A， A 中的任一元素 A(i,j)代表結(jié)點(diǎn) i 到結(jié)點(diǎn) j 的最短路徑長(zhǎng)度。 若 利用動(dòng)態(tài)規(guī)劃策略求解 ，可以 將求解 G 中每對(duì)結(jié)點(diǎn)之間的最短路徑問題轉(zhuǎn)化成一個(gè)多階段決策過程 。若該路徑經(jīng)過結(jié)點(diǎn) k，則 Ak (i,j) ＝ Ak1 (i,k) + Ak1 (k,j)， 若該路徑不經(jīng)過結(jié)點(diǎn) k，則 Ak (i,j) ＝ Ak1 (i,j)， 故可得 Ak(i,j) = min{ Ak1 (i,j)，Ak1 (i,k) + Ak1 (k,j)}。 real COST(n,n),A(n,n) for i← 1 to n do for j← 1 to n do A(i,j) ← COST(i,