[學(xué)習(xí)]算法設(shè)計(jì)與分析ch10on-line算法

1、第十章 On-line Algorithms,10.1 Introduction to On-line Algorithms,前九章介紹的算法設(shè)計(jì)的條件在算法執(zhí)行之前整個(gè)輸入數(shù)據(jù)的細(xì)節(jié)都很清楚問題是在完全了解輸入數(shù)據(jù)信息條件下解決的實(shí)際應(yīng)用存在不滿足上述條件的情況磁盤調(diào)度問題操作系統(tǒng)的頁面調(diào)度問題 Data streams,On-line算法在算法設(shè)計(jì)階段或執(zhí)行之前無完全信息可用,輸入數(shù)據(jù)往往是實(shí)時(shí)到達(dá)的.算法時(shí)

2、而正確時(shí)而錯(cuò)誤.實(shí)時(shí)算法難以給出正確解, 一般是近似算法.實(shí)時(shí)最小生成樹問題難以給出優(yōu)化解, “最小”需要放棄或改為“小”.On-line算法可能如下工作:當(dāng)每次一個(gè)數(shù)據(jù)到達(dá)時(shí), 將其連接到最近的鄰居節(jié)點(diǎn).下邊是一個(gè)六個(gè)實(shí)時(shí)到達(dá)節(jié)點(diǎn)的例子.,,,,,1,3,5,,2,6,4,算法工作過程,優(yōu)化解,On-line算法的性能令Con表示On-line算法解的代價(jià)令Coff表示Off-line算法解的代價(jià)若Con?f(n)C

3、off+c, c是常數(shù), 則稱On-line算法的近似比為 f(n). 這個(gè)算法稱為f(n)-competitive,10.2 On-line Euclidean Spanning Tree Problem,問題的定義實(shí)時(shí)算法設(shè)計(jì)算法性能分析,問題的定義,輸入: S={v1, v2, …, vn}是平面上的n個(gè)點(diǎn)的集合 這n個(gè)點(diǎn)并非一次給定, 是逐個(gè)出現(xiàn)的 輸出 一個(gè)”最小”生成樹,,求解最小生成樹問題的On-li

4、ne算法只能是近似算法,Greedy-On-line-ST(S)1. n=|S|;2. T=0;3. While n?0 Do4. Input(v);5. 把v與V(T)之間最短邊加入T; /*V(T)是T節(jié)點(diǎn)集合 */6. Endwhile,On-Line算法,算法的時(shí)間復(fù)雜性3-6步需要的比較次數(shù)=1+2+…+(n-1)T(n)=O(n2)解的精確度Greedy-On-line-ST

5、算法的近似比是O(logn)設(shè)Tonl是算法產(chǎn)生的生成樹, l是優(yōu)化生成樹的代價(jià)或長度, 下邊我們來證明這個(gè)結(jié)論,算法的性能分析,,,,,引理1. Tonl中第k最長邊的長度最多為2l/k, 1?k?n-1. 證. 令Sk={v | v加入Tonl后, Tonl中出現(xiàn)長度大于2l/k的邊}. 如果|Sk|<k, 則Tonl中至多k-1條邊的長度大于2l

6、/k, 即Tonl中第k最長邊的長度最多為2l/k. 往證|Sk|<k. 由算法的Greedy方法可知, Sk中每個(gè)點(diǎn)對之間的距離必大于2l/k. 若不然, 設(shè)u和v之間距離小于2l/k, 則加入u(或v)以后, 再加入v(或u)時(shí), 不會產(chǎn)生大于2l/k的邊.,,,,于是, Sk上TSP的優(yōu)化解的長度大于 |Sk|2l/k . 由于任意點(diǎn)集上的TSP優(yōu)化解的長度是其最小生成樹

7、長度的2倍, Sk的最小生成樹的長度大于|Sk|l/k . 因?yàn)镾k上最小生成樹長度l’不小于S上最小生成樹長度, 我們有, |Sk|l/k < l’ ? l , 即|Sk|l/k < l, 或 |Sk| < k . 于是, Tonl中第k最長邊的長度最多為2l/k. 定理1. Greedy-On-line-ST算法的近似比是O(logn). 證. 由

8、引理1, Tonl的長度L ? ?1?k?n-12l/k =2l ?1?k?n-11/k =2l?H(n-1)=O(logn). 于是, 算法的近似比為L/l?O(logn).

9、,10.3 On-line Algorithm for Convex hull problems,問題的定義 On-line算法的基本思想 On-line算法算法的性能分析,,問題定義,輸入平面上的n個(gè)點(diǎn)的集合Q n個(gè)點(diǎn)逐個(gè)到達(dá), 并非同時(shí)出現(xiàn)輸出CH(Q): Q的convex hull Q的convex hull是一個(gè)凸多邊形P， Q的點(diǎn)或者在P上或者在P內(nèi),凸多邊形P是具有如下性質(zhì)多邊形

10、:連接P內(nèi)任意兩點(diǎn)的邊都在P內(nèi),基本思想當(dāng)k個(gè)節(jié)點(diǎn)已經(jīng)到達(dá)后, 我們得到一個(gè)部分CH,On-line算法的思想,當(dāng)?shù)趉+1個(gè)節(jié)點(diǎn)v到達(dá)時(shí)如果v落在CH內(nèi)部, 不需做任何事如果v落在CH外部, 需要調(diào)整CH的邊界關(guān)鍵是: 記住和調(diào)整部分CH邊界,,,平行線近似法 用一組并行線記錄、調(diào)整、近似CH,,,,,,,,,,,,,,,,,,,,需要平行移動(dòng)這條線, 不改變其斜率,,,,,,,近似解,,,平行線的一般形式取m對平行線

11、, 其斜率分別為: 0, tan(?/m), tan(2?/m), …, tan((m-1)?/m).這m對平行線必須滿足:每個(gè)輸入節(jié)點(diǎn)必須在所有平行線對內(nèi);每對平行線必須盡可能的靠近,輸入節(jié)點(diǎn)序列 p1, p2, …滿足前面條件的m對平行線輸出 近似convex hull序列 a1, a2, … ai是覆蓋p1, p2, …, pi的近似convex hull,On-line算法,算法A初始化: 構(gòu)造

12、m對平行線, 斜率為0, tan(?/m), …, tan((m-1)?/m); 搜索平行線相交在第一個(gè)點(diǎn)p1.第一步: 對于任意一個(gè)新到達(dá)點(diǎn)pi, 如果pi落在所有平行線對 之間, 不執(zhí)行任何操作; 否則, 平移最接近pi的線到pi, 不改變其斜率, 使pi成為該線的標(biāo)記.第二步: 沿逆時(shí)針方向連接每條平行線上的輸入點(diǎn), 形成近似

13、 convex hull ai.第三步: 如果不再有點(diǎn)輸入 , 則停止; 否則令i=i+1, 接受下一 個(gè)點(diǎn)pi, goto 第一步.,時(shí)間復(fù)雜性O(shè)(mn)=O(n) (因?yàn)閙是常數(shù))近似解精度三種相關(guān)的多邊形E: 由2m個(gè)平行線形成的多邊形.C: 輸入點(diǎn)集合的Convex hull, 即準(zhǔn)確解.A: 算法A給出的近似Convex hull. L(P)表示

14、多邊形P的總邊長, 則L(E)?L(C)?L(A). 近似解A的誤差定義為 ERR(A)=(L(C)-L(A))/L(C),算法的性能分析,,,定理1. ERR(A)?sec(?/2m)-1. *定理1說明m越大(即平行線對越多), 錯(cuò)誤越小. 證. 考慮下圖:,于是, AB+AC? BC sec(?/2).,,考慮下圖,,由AB+AC? BC sec(?/2)，我

15、們有 L(E)= P2mA1+A1P1+P1A2+…+A2mP2m ? sec(? /2m)(P2mP1+P1P2+…+P2m-1P2m) = sec(? /2m)L(A). 于是, Err(A)= (L(C)-L(A))/L(C)

16、 ? (L(E)-L(A))/L(A) ? sec(? /2m)-1,10.4 Randomized On-line Algorithm for MST,問題的定義 隨機(jī)On-line算法 算法的性能分析,問題的定義,輸入 Euclidean空間上的n個(gè)點(diǎn): v1, v2, …, vn n個(gè)逐個(gè)出現(xiàn) 輸出 由v1, v2, …, vn構(gòu)成的最小生成樹,,Al

17、goritm R(m)T=0; input(m); input(v1); input(v2);把邊(v1, v2)添加到T;For k=3 To n Do input(vk); If k?m+1 Then 從(vk, v1), …,(vk, vk-1)中選擇最小邊加入T; Else 從(vk, v1)

18、, …,(vk, vk-1)中隨機(jī)地選擇m條邊, 把這m條邊中最小邊加入T;Return T.,隨機(jī)On-line算法,R(n-1)是一個(gè)確定的貪心算法,算法的時(shí)間復(fù)雜性,時(shí)間復(fù)雜性 每次考察需要O(m)時(shí)間 需要O(n)次考察 T(n)=O(nm),,近似解的精確度,定義1. 隨機(jī)On-line算法A稱為c-competitive, 如果存 在一個(gè)常數(shù)b

19、, 使得 E(CA(?)) ? c?Copt(?)+b 其中, E(CA(?))是算法A在問題實(shí)例?上產(chǎn)生的 近似解的代價(jià), Copt(?)是?的優(yōu)化解的代價(jià).定理1. 如果m是固定常數(shù), 算法R(m)的competitive, 則比是?(n). 證.,,我們首先定義一組記號: ?

20、={1, 2, …, n} 輸入點(diǎn)集合, 輸入順序?yàn)?、2、…、n. D(a, b) = 點(diǎn)a和b之間的距離. N(a, k) = 在已經(jīng)出現(xiàn)的點(diǎn)中點(diǎn)a的第k最近點(diǎn). E(LR(m)(? )) = 算法R(m)產(chǎn)生的樹的期望長度. 假定算法收到第i個(gè)輸入點(diǎn)i. 如果2?i?m+1, 則i與前i-1個(gè)點(diǎn)中最近點(diǎn)連接, 加入樹中. 如果m+1?i?n, 則i與

21、前i-1個(gè)點(diǎn)中第j最近點(diǎn)連接的概率為,于是, 我們有,,我們來計(jì)算E(LR(m)(?))/L(?)的下界. L(?)是輸入點(diǎn)集合為?時(shí)的最小生成樹的長度.構(gòu)造一個(gè)特殊輸入序列?*, 使得 E(LR(m)(?*))/L(?*)=?(n)于是, E(LR(m)(?))/L(?)=?(n)我們來計(jì)算E(LR(m)(?))/L(?)的上界.令D是n個(gè)輸入點(diǎn)的直徑. 最小生成樹的長度?D.因每條