第九章approximationalgorithm-資料下載頁
2024-10-17 12:39本頁面
【導(dǎo)讀】近似算法的性能分析。近似算法的基本思想。如果問題的輸入很小,可以使用指數(shù)級算法圓滿地。近似算法主要解決優(yōu)化問題。近似算法的時間復(fù)雜性。近似算法解的近似度。問題的優(yōu)化解可能具有最大或最小代價。如果問題是最大化問題,max{C/C*,C*/C}=C*/C. 由于C/C*<1當(dāng)且僅當(dāng)C*/C>1,RatioBound不會小于1. 和p獨(dú)立于n,用p和?某些NP-完全問題的近似算法滿足:當(dāng)運(yùn)行時間增。加時，RatioBound和相對誤差將減少.結(jié)論1表示,只要求出了RatioBound就求出了?)稱為一個多項(xiàng)式時間。近似模式,如果對于任意?例大小n的多項(xiàng)式.證.令A(yù)={(u,v)|(u,v)是算法第4步選中的邊}.A,則與(u,v)鄰接的邊皆從E’中刪除.于是,A中無相鄰接邊.第5步的每次運(yùn)行增加兩個結(jié)點(diǎn)到C,?有限集X,X的所有子集族F,X=∪S?*最小集合覆蓋問題是很多實(shí)際問題的抽象.X;/*U是X中尚未被覆蓋的元素集*/. ;/*構(gòu)造X的覆蓋*/
【正文】 ). 從 L中刪除盡可能多的元素 , (2). 如果 L‘是 L修剪后的結(jié)果 , 則對每個從 L中刪除的元 素 y, L‘中存在一個元素 z?y, 使得 (1δ)y?z?y – 如果 y被修剪掉 , 則存在一個代表 y的 z在 L中 , 而且 z相對于 y的相對誤差小于 δ. 完全多項(xiàng)式時間近似模式 HIT CSamp。E ? 修剪算法 Trim(L=?y1, y2, ..., ym?,δ) /* yi?yi+1, 0δ1, 輸出縮小的表 L?. */ m??L?。 L??y1。 last?y1。 For i?2 To m Do If last(1δ)yi /*即 yi1(1δ)yi, 由 L和 L’有序 , 對 ?y?L‘, 不滿足 (1δ)yi?y?yi */ Then yi加入到 L?末尾 。 /* 因 L39。中目前沒有能夠表示 yi的元素 */ last?yi。 Return L? . ? 復(fù)雜性 : O(?L?)=O(m) HIT CSamp。E ? 完全多項(xiàng)式近似模式 輸入 : S=?x1, x2, ..., xn?, t ?0, 0? 1 輸出 : 近似解 z ApproxSubsetSum(S, t, ?) 1. n??S?。 2. L0?0 3. For i?1 To n Do 4. Li?MergeList(Li1, Li1+xi)。 5. Li?Trim(Li, ? /n) /* 修剪參數(shù) δ=? /n */ 6. 從 Li中刪除大于 t的元素 。 7. 令 z是 Ln中最大值 。 8. Return z . HIT CSamp。E ? 性能分析 定理 1. ApproxSubsetSum是子集求和問題的一個完 全多項(xiàng)式時間近似模式 . 證 .令 P0={0}, Pi=?x ? x=?y?A y, A??x1, x2, ..., xi??. 例如 , 令 S={1, 4, 5}, 則 P1={0, 1}, P2={0, 1, 4, 5}, P3={0, 1, 4, 5, 6, 9, 10}. 使用數(shù)學(xué)歸納法可以證明 : Pi=Pi1∪ (Pi1+xi). 使用數(shù)學(xué)歸納法可以證明 Li是 Pi中所有不大于 t的元素 的有序表 . HIT CSamp。E Li經(jīng)第 5步修剪以及第 6步的大于 t元素的刪除 , 仍然有 Li?Pi. 于是 , 第 8步返回的 z是 S的某個子集的和 . 我們需證明 (1). C*(1?)?z, 即 (C*z)/C*??, C*是優(yōu)化解 , z是近似解 . 注意 , 由于子集合求和問題是最大化問題 , (C*z)/C*是算法 的相對誤差 . (2). 算法是關(guān)于 ?S?和 1/?的多項(xiàng)式時間算法 . HIT CSamp。E (1). 往證 C*(1?)?z 對 i作歸納法證明 : ?y?Pi, y?t, 存在一個 z39。?Li使 (1?/n)iy?z39。?y. 當(dāng) i=0時 Pi={0}, Li={0}, 命題成立 . 設(shè)當(dāng) i?k時命題成立 . Pk+1= Pk∪ {Pk+xk+1}. 由歸納假設(shè) , ?y?Pk+1∩Pk, y?t, 存在 z‘?Lk?Lk+1使 (1?/n)ky?z39。?y. 于是 , (1?/n)k+1y?z39。 ?y. 對于 ?y39。?Pk+1Pk, y39。=y+xk+1 ?t, y?Pk. 由歸納假設(shè) , 存在 z39。?Lk?Lk+1使 (1?/n)ky?z39。?y. 于是 , (1?/n)ky+xk+1?z39。+xk+1?y+xk+1. 由于 z39。?Lk, z39。+xk+1?Lk+1, 而且 ((1?/n)ky+xk+1)((1?/n)k+1(y+xk+1)) =(1?/n)k(y(1?/n)y)+(xk+1(1?/n)k+1xk+1)0, 即 (1?/n)k+1(y+xk+1)?(1?/n)ky+xk+1?z39。+xk+1?y+xk+1. HIT CSamp。E 最后 , 若 C*?Pn是子集合求和問題的優(yōu)化解 , 則存在一個 z‘?Ln, 使 (1?/n)nC*?z’?C*. 因算法解 z=max(Ln), (1?/n)nC* ? z’?z?C*. 由于 (1?/n)n的一階導(dǎo)數(shù)大于 0, (1?/n)n是關(guān)于 n遞增的函數(shù) . 因?yàn)?n1, (1?)(1?/n)n. 于是 , (1?)C*?z, 即近似解 z與優(yōu)化解的相對誤差不大于 ?. (2). 往證算法的時間復(fù)雜性是 n與 1/?的多項(xiàng)式 先計(jì)算 ?Li?的上界 . 修剪后 , Li中的相鄰元素 z和 z39。滿足 : z’(1?/n)z, 即 z/z?1/(1?/n). 如果 Li中具有 k+2個元素 , 則必有 y0=0, y1=z0, y2z0?1/(1?/n), y3z0?1/(1?/n)2,…, y k+1z0?1/(1?/n)k, 而且 z0?1/(1?/n)k?t. 由 z0?1/(1?/n)k?t, k?log1/(1?/n)t, 對 log1/(1?/n)t, 臺勞展開 ln(1?/n), |Li|=k+2?2+log1/(1?/n)t =2+(lnt/ln(1?/n))?2+nlnt/?. 算法的運(yùn)行時間是 ?Li?的多項(xiàng)式 , 即 n和 1/?的多項(xiàng)式 . HIT CSamp。E HIT CSamp。E HIT CSamp。E HIT CSamp。E HIT CSamp。E HIT CSamp。E HIT CSamp。E
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1