第十章on-linealgorithms-在線瀏覽
2024-08-31 17:16本頁面
【正文】 1 3 5 2 6 4 算法工作過程 優(yōu)化解 1 3 5 2 6 4 HIT CSamp。E Online Euclidean Spanning Tree Problem ?問題的定義 ?實(shí)時(shí)算法設(shè)計(jì) ?算法性能分析 HIT CSamp。E GreedyOnlineST(S) 1. n=|S|。 3. While n?0 Do 4. Input(v)。 /*V(T)是 T節(jié)點(diǎn)集合 */ 6. Endwhile OnLine算法 HIT CSamp。E 引理 1. Tonl中第 k最長邊的長度最多為 2l/k, 1?k?n1. 證 . 令 Sk={v | v加入 Tonl后 , Tonl中出現(xiàn)長度大于 2l/k的邊 }. 如果 |Sk|k, 則 Tonl中至多 k1條邊的長度大于 2l/k, 即 Tonl中第 k最長邊的長度最多為 2l/k. 往證 |Sk|k. 由算法的 Greedy方法可知 , Sk中每個(gè)點(diǎn)對(duì)之間的距離必 大于 2l/k. 若不然 , 設(shè) u和 v之間距離小于 2l/k, 則加入 u(或 v)以后 , 再加 入 v(或 u)時(shí) , 不會(huì)產(chǎn)生大于 2l/k的邊 . HIT CSamp。E Online Algorithm for Convex hull problems ? 問題的定義 ? Online算法的基本思想 ? Online算法 ?算法的性能分析 HIT CSamp。E ? 基本思想 – 當(dāng) k個(gè)節(jié)點(diǎn)已經(jīng)到達(dá)后 , 我們得到一個(gè)部分 CH Online算法的思想 – 當(dāng)?shù)?k+1個(gè)節(jié)點(diǎn) v到達(dá)時(shí) ? 如果 v落在 CH內(nèi)部 , 不需做任何事 ? 如果 v落在 CH外部 , 需要調(diào)整 CH的邊界 ? 關(guān)鍵是 : 記住和調(diào)整部分 CH邊界 HIT CSamp。E ? 平行線的一般形式 – 取 m對(duì)平行線 , 其斜率分別為 : 0, tan(?/m), tan(2?/m), … , tan((m1)?/m). – 這 m對(duì)平行線必須滿足 : ? 每個(gè)輸入節(jié)點(diǎn)必須在所有平行線對(duì)內(nèi) 。E ? 輸入 – 節(jié)點(diǎn)序列 p1, p2, … – 滿足前面條件的 m對(duì)平行線 ? 輸出 – 近似 convex hull序列 a1, a2, … – ai是覆蓋 p1, p2, … , pi的近似 convex hull Online算法 HIT CSamp。 搜索平行線相交在第一個(gè)點(diǎn) p1. 第一步 : 對(duì)于任意一個(gè)新到達(dá)點(diǎn) pi, 如果 pi落在所有平行線對(duì) 之間 , 不執(zhí)行任何操作 。 否則令 i=i+1, 接受下一
語文相關(guān)推薦
鄂ICP備17016276號(hào)-1