刪尋演算法 蠶食而盡 《韓非子·存韓》：“諸侯可蠶食而盡，趙氏可得與敵矣。” 國立中央大學 資工系 江振瑞 教授.

Presentation on theme: "刪尋演算法 蠶食而盡 《韓非子·存韓》：“諸侯可蠶食而盡，趙氏可得與敵矣。” 國立中央大學 資工系 江振瑞 教授."— Presentation transcript:

1 刪尋演算法 蠶食而盡 《韓非子·存韓》：“諸侯可蠶食而盡，趙氏可得與敵矣。” 國立中央大學 資工系 江振瑞 教授

2 1. 刪尋演算法基本概念

3 刪尋解題策略 刪尋(prune-and-search)解題策略使用多次迭代(iteration)解決問題。
在每次迭代都刪除(prune)輸入資料的一部份(假設為f部份, 0<f<1)，而後採用相同的演算法遞迴地(recursively)從剩餘資料中搜尋(search)出解答。 而經過幾次迭代後，輸入資料的規模將會小到足以讓問題使用常數時間複雜度直接解決。

4 使用刪尋解題策略的演算法 二元搜尋演算法 選取與中位數演算法 限制的一圓心演算法 簡化的二變數線性規劃演算法

5 一般刪尋演算法時間複雜度 假設輸入規模為n，而刪尋演算法每次迭代都刪除(prune)輸入資料的f 部份(0<f<1)，若在每次迭代執行所需的時間複雜度為cnk=O(nk), k >0，則在最差狀況下刪尋演算法的時間複雜度T(n)為: T(n) = T((1-f ) n) + cnk

6 一般刪尋演算法時間複雜度(續) 迭代p次,假定(1-f)p+1n 1  (1-f)pn 等比級數公式

7 補充: 等比級數 假設一個等比級數Sn的首項為a1，末項為an，公比為r，則
Sn=a1(1-rn)/(1-r)=(a1-ran)/(1-r) 假設一個無窮等比級數S的首項為a1，公比為r。若r<1，則 S=a1/(1-r)

8 2. 二元搜尋演算法

9 二元搜尋演算法 給定一個已依由小到大順序排列的數值陣列A，假設我們要在索引 l 與 索引 r 之間找出目標數值t的索引，則我們可以使用二元搜尋(binary search)演算法採用刪尋策略來有效率地進行這項工作。

10 二元搜尋演算法(續)

11 二元搜尋演算法範例 已排序好的陣列A: (搜尋 43) 索引: -1 0 1 2 3 4 5 6
索引: 數值: (搜尋43) 迭代 l m r 迭代2 l m r (傳回索引5) (搜尋1) 迭代 l m r 迭代 l m r 迭代 l,r,m 迭代4 r l (因r<l，故傳回索引-1代表t不在陣列中)

12 二元搜尋演算法 是刪尋還是分治演算法? 二元搜尋演算法可視為刪尋(prune-and-search)演算法。在每一個迭代的比較之後，會有一半的資料被刪除(prune away )。 二元搜尋演算法亦可視為分治(divide-and-conquer)演算法。在每一次分割之後，一個分割可能存在解答，另一個分割一定不存在解答。

13 二元搜尋演算法時間複雜度分析 假設搜尋範圍內有n個元素，則時間複雜度T(n)為: T(n) = T(n/2)+1 = T(n/4)+1+1
=T(n/2k)+k*1 令n/2k=1 ，則n = 2k 且k=log n, 我們可得 T(n) = T(1)+k = 1+k = O(log n)

14 3. 選取與中位數演算法

15 選取與中位數問題 給定一個擁有n個元素的集合S，選取問題 (selection problem)欲尋找S中第k小的元素。
給定一個擁有n個元素的集合S，中位數(median) 問題欲尋找S中第 小的元素。 最直接的演算法: 步驟1: 將n個元素依由小而大排序 步驟2: 從排序好的元素中找出第k個或第 個元素 時間複雜度: O(n log n)

16 以刪尋策略解決選取問題 令S={a1, a2, …, an}
找出 p  S, 用 p 將 S 分割成 3 個子集合 S1 , S2 , S3: S1={ ai | ai < p , 1  i  n} S2={ ai | ai = p , 1  i  n} S3={ ai | ai > p , 1  i  n} 若 |S1| > k ，代表第k小的元素在S1中，我們可刪除S2和S3。 否則，若 |S1| + |S2| > k，則 p 就是 S 中第 k 小的元素。 否則，代表第 k 小的元素是S3中第(k - |S1| - |S2|)小的元素，我們可刪除S1和S2。

17 以刪尋策略解決選取問題(續) p Q: 如何選擇 p? A: 中位數的中位數
How: 將n個元素分割成n/5個大小為5的子集合，找出每個子集合的中位數，然後再找出這些中位數的中位數。 問題: 為什麼選擇子集合的大小為5?3可以嗎?4可以嗎?6可以嗎? S中至少有1/4的元素小於或等於p (S1至少有1/4的元素) 針對每一個大小為5的子集合，直接將其元素由小到大排列並找出其中位數。 p 再找出中位數的中位數p S中至少有1/4的元素大於或等於p (S3至少有1/4的元素)

18 刪尋選取演算法 Algorithm 刪尋選取演算法 Input: 一個有n個元素的集合S，以及整數k。
Output: 集合S內第k小的元素。 步驟1: 將S分割為n/5個大小為5的子集合。若n不能被5整除的話則在最後一個子集合內增加值為的元素，使其補滿5個元素。 步驟2: 直接排序每個子集合內的元素。 步驟3: 從每個子集合內找出中位數，再遞迴地從找出的中位數中找出中位數(也就是找出所有子集合中位數的中位數)，令其為p。

19 刪尋選取演算法(續) 步驟4: 將S分成 S1, S2, S3三個子集合，每個子集合分別包含小於、等於、大於p的元素。
步驟5: 若 |S1| k, 則捨棄 S2 與 S3 並且在下一次迭代中從S1 內找出第k小的元素為輸出(令S=S1；跳回步驟1)；否則，若|S1| + |S2| k 則輸出p為S內第K小的元素; 否則，令 k = k - |S1| - |S2|，在下一次的迭代中從S3 找出第 k’ 小的元素為輸出(令S=S3；k=k’；跳回步驟1) 。

20 刪尋選取演算法時間複雜度分析 總時間複雜度: T(n) = T(3n/4)+T(n/5)+cn
一次的迭代至少可以刪除n/4個元素，剩餘的3n/4個元素，可以在步驟5遞迴地處理。 步驟3以遞迴的方式找出n/5個中位數的中位數。 步驟時間複雜度: 步驟1: O(n) 步驟2: O(n) 步驟3: T(n/5) 步驟4: O(n) 步驟5: T(3n/4) 總時間複雜度: T(n) = T(3n/4)+T(n/5)+cn

21 刪尋選取演算法時間複雜度分析(續) 等比級數公式 令 T(n) = a0 + a1n + a2n2 + … , a1  0
T(3n/4 + n/5) = T(19n/20) = a0 + (19/20)a1n + (361/400)a2n2 + … T(3n/4) + T(n/5)  a0 + T(19n/20)  T(n)  c’n + T(19n/20)  c’n + (19/20)c’n +T((19/20)2n) …  c’n + (19/20)c’n + (19/20)2c’n + … +(19/20)pc’n + T((19/20)p+1n) , (19/20)p+1n 1  (19/20)pn  T(n) =  20 cn + c ’’ = O(n) 等比級數公式

22 4. 限制的一圓心演算法

23 一圓心問題 一圓心問題(1-center problem): 給定n個平面點，找出一個最小可覆蓋此n個點的圓。
Given n planar points, find a smallest circle to cover these n points.

24 一圓心問題(續) 基本暴力(brute force)法: 列出每一個可能的候選圓並檢查其是否能夠覆蓋所有的點: 總時間複雜度: O(n4)
Given n planar points, find a smallest circle to cover these n points.

25 限制的一圓心問題 限制的一圓心問題(constrained 1-center problem):
給定n個平面點，找出一個最小可覆蓋此n個點的圓，但是限制圓心r必須座落在y=c(例如y=0)的直線上。 The constrained 1-center problem The center is restricted to lying on a straight line, say y=y’=0.

26 限制的一圓心演算法 Algorithm 限制的一圓心演算法 Input: n個平面點p1, p2, …, pn與直線y = c
Output: 圓心在y=c上可覆蓋p1, p2, …, pn的最小圓 步驟1: 若n2，則直接找出圓。 步驟2: 若n為偶數，則形成n/2個點對(p1, p2), …,(pn-1, pn)；反之，若n為奇數，則形成n/2個點對(p1, p2), …, (pn-2, pn-1), (pn, p1)。 步驟3: 對於每一點對(pi, pi+1)，做出其中垂線Lij，交於直線y=c，以找出一個在直線y=c上的等距點qi,i+1，使得d(pi, qi,i+1)= d(pi+1, qi,i+1)，其中d(p, q)代表點p與點q的距離。 Input : n points and a straight line y = y’. Output : The constrained center on the straight line y = y’. Step 1. If n is no more than 2, solve this problem by a brute-force method. Step 2. Form disjoint pairs of points (p1, p2), (p3, p4), …,(pn-1, pn). If there are odd number of points, just let the final pair be (pn, p1). Step 3. For each pair of points, (pi, pi+1), find the point xi,i+1 on the line y = y’ such that d(pi, xi,i+1) = d(pi+1, xi,i+1).

27 限制的一圓心演算法(續) 步驟4: 找出所有等距點的X座標值的中位數xm，令對應的等距點為qm=(xm, c)。
步驟5: 以qm來評估最佳解圓心q*在y=c的位置: 計算每個pi與點qm的距離，並令pj為距qm最遠的點。令qj表示pj 在直線 y=c上的投影點，若 qj 落在qm左側(右側)，則最佳解圓心q* 亦必定會落在qm的左側(右側)。 步驟6: 若q*落在qm的左側，則針對每個X軸值大於xm的等距點qi,i+1，刪除其對應點pi與pi+1中靠qm較近的點;反之，若q*落在qm的右側，則針對每個X軸值小於xm的等距點qi,i+1，刪除其對應點pi與pi+1中靠qm較近的點。 步驟7: 跳到步驟1繼續執行。 Step 4. Find the median of the xi,i+1’s. Denote it as xm. Step 5. Calculate the distance between pi and xm for all i. Let pj be the point which is farthest from xm. Let xj denote the projection of pj onto y = y’. If xj is to the left (right) of xm, then the optimal solution, x*, must be to the left (right) of xm. Step 6. If x* < xm, for each xi,i+1 > xm, prune the point pi if pi is closer to xm than pi+1, otherwise prune the point pi+1; If x* > xm, for each xi,i+1 < xm, prune the point pi if pi is closer to xm than pi+1; otherwise prune the point pi+1. Step 7. Go to Step 1.

28 限制的一圓心演算法執行展示 q* qi,i+1 qm=(xm, c) qj
Lij pj pi pi+1 q* y = c qi,i+1 qm=(xm, c) qj 步驟4: 找出所有等距點的X座標值的中位數xm，令對應的等距點為qm=(xm, c)。 步驟5: 以qm來評估最佳解圓心q*在y=c的位置: 計算每個pi與點qm的距離，並令pj為距qm最遠的點。令qj表示pj 在直線 y=c上的投影點，若 qj 落在qm左側(右側)，則最佳解圓心q* 亦必定會落在qm的左側(右側)。 步驟6: 若q*落在qm的左側，則針對每個X軸值大於xm的等距點qi,i+1，刪除其對應點pi與pi+1中靠qm較近的點;反之，若q*落在qm的右側，則針對每個X軸值小於xm的等距點qi,i+1，刪除其對應點pi與pi+1中靠qm較近的點。 The Pruning of Points in the Constrained 1-Center Problem

29 限制的一圓心演算法時間複雜度分析 限制的一圓心演算法使用刪尋策略解決問題，在每個迭代均刪除一部份輸入資料。由於每個迭代均有n/4個等距點在qm的左方(或右方)，故演算法每次迭代均可刪除n/4個點。 由於步驟2-6的時間複雜度均為O(n)，根據前述「一般刪尋演算法時間複雜度」的說明，限制的一圓心演算法的時間複雜度為 T(n)=T(3n/4)+cn=O(n) Since there are xi,i+1’s lying in the left (right) side of xm, we can prune away points for each iteration of the algorithm. Each iteration takes O(n) time. Hence the time-complexity of this algorithm is T(n)=T(3n/4)+O(n)=O(n), as n  Time complexity: O(n)

30 5. 簡化的二變數線性規劃演算法

31 線性規劃或線性最佳化問題 線性規劃(linear programming)或 線性最佳化(linear optimization)問題:
欲最大化或最小化目標函數: 限制條件(限制式)為: a, c為係數，x為變量，因為皆為一次方，因此稱為線性。若大於等於改為等號則形成線性系統(linear system)，或線性聯立方程式，n個變量就有n個等式，一般情況可以用高斯消去法求出一個解答，或無解。x1,…,xd>=0有時省略，因為所有變量都為非負。 Linear programming為大於或小於，表示是限制條件，表示解答必須在hyperplane的上方或下方。

32 二變數線性規劃範例

33 線性規劃或線性最佳化(續) 線性規劃 (linear programming, LP)問題: 目標函數(objective function)和限制條件(constraints)都是線性(變數都是一次方)的最佳化(optimization)問題。是多項式時間複雜度(polynomial time complexity)問題。 要求所有變數都限定為整數的線性規劃問題叫做整數線性規劃 (integer linear programming, ILP)或整數規劃(integer programming, IP)問題。是NP困難(NP-hard)問題。 0/1 整數規劃(0/1 integer linear programming, 0/1 ILP)是整數線性規劃的特殊情況，要求所有的變數都要是0或1。是NP困難(NP-hard)問題。 根據一般的說法, 線性規劃問題是由現 在美國史丹褔大學任教的 G. B. Dantzig 教授在1947年前後孕育出來的。 那個時候他 擔任 美國空軍的數學顧問, 負責發展一套 機械式的方法來做兵力調遣, 人員訓練, 以 及後勤補給這些計劃方案。 由於這類問題牽 涉很廣也很複雜, 所以Dantzig 博士先考慮 最簡單的線性結構, 將有關的函數一律簡化 成線性形式來處理。 其結果便在 1948 年以 「線性結構的規劃」(Programming in Lin- ear Structure) 的標題發表。 在 1947 到 1949 兩年間, 線性 規劃裡的一些重要觀念, 包括最有名的 「單 形法」(Simplex method), 都陸續見諸於世。 而且從1947年開始,T. C. Koopmans 便明 確指出線性規劃可以做為傳統經濟分析的利 器。 1975年, 瑞典皇 家科學院決定將當年的諾貝爾經濟獎頒發給 前面提到的L. V. Kantorovich 和 T. C. Koopmans 以表彰他們在 「資源最佳分配理 論」 的貢獻。 由於這項最佳分配是藉由線性規 劃模式來達成, 所以線性規劃便成了萬眾矚 目的焦點。 1979 年), 線性規劃 再次成了報章雜誌的頭條新聞。 這次是因為 一位蘇聯數學家 L. G. Khachian, 他 利用 N. Z. Shor,D. B. Yudin, 以及 A. S. Nemirovskii的 「橢球法」 (ellipsoid method) 概念印證出線性規劃問題可 在多項式時間內求得解答。 不幸的是理論歸於理論, 在實際計 算上,「橢球法」 的一般表現反倒不如傳統的 「單形法」來得有效。於是這方面的學者 專家重新構想是否能設計出一套解法無論 在理論上和實際計算上均能超越 「單形 法」? 這個問題的答案到了 1984 年由一位 美國電話電報公司貝爾實驗室的印度裔科學 家N. Karmarkar 揭曉。 他設計出一項 「內 點法」 來解線性規劃問題, 不但理論上較 「單 形法」 為優, 而且經由實際驗證適合解決超大 型的問題。

34 著名的線性規劃演算法 1947: 單形演算法(simplex alg.): George Dantzig, O(2n), n為限制式的個數
1975: 諾貝爾經濟獎: L. V. Kantorovich 和 T. C. Koopmans (基於線性規劃的「資源最佳分配理論」) 1979: 橢球演算法(ellipsoid alg.): Leonid Khachiyan, 第一個最差狀況時間複雜度為多項式的線性規劃演算法, O(n6L2  log L  log log L), L為輸入的位元數。但是這個演算法實際使用時效能並不好。 1984: 投射演算法(projective alg.): N. Karmarkar, O(n3.5L2  log L  log log L) Where n is the number of variables and L is the number of bits of input to the algorithm, Karmarkar's algorithm requires  operations on  digit numbers, as compared to  such operations for the ellipsoid algorithm. The runtime of Karmarkar's algorithm is thus using FFT-based multiplication (see Big O notation). Karmarkar's algorithm falls within the class of interior point methods: the current guess for the solution does not follow the boundary of the feasible set as in thesimplex method, but it moves through the interior of the feasible region, improving the approximation of the optimal solution by a definite fraction with every iteration, and converging to an optimal solution with rational data.[1] 以上資料參考維基百科:

35 簡化的二變數線性規劃問題 簡化的二變數線性規劃(simplified two-variable linear programming)問題:
給定n個限制條件，其中第i個限制條件為: y  kix + ti, i = 1, 2, …, n (ki為斜率，ti為y截距) 欲最小化目標函數y

36 簡化的二變數線性規劃問題範例 給定n(n=6)個限制條件， 欲最小化目標函數y 可行解區域之邊界(boundary)函數B(x):
最佳解(x*, y*): y*=B(x*) = B(x)

37 簡化的二變數線性規劃演算法

38 簡化的二變數線性規劃演算法說明 步驟2總共產生n/2對限制式
步驟4產生邊界函數值ym=B(xm)的限制式可能為一個、兩個或兩個以上。但是不管有幾個限制式，在步驟5中，我們只要找出限制式中最大的斜率smax與最小的斜率smin就可以判斷xm與x*的關係 步驟6刪除n/4對限制式中的一個限制式，總計刪除n/4個限制式

39 xm與x*的關係 假設xm是成對方程式交點x座標中位數， x*是最佳解x座標
Q: x*<xm? 或 x*=xm? 或 x*>xm?

40 限制式刪除範例 如左圖，因為x*>xm=x12 ，而且限制式k5x + t5和k6x + t6交點的x座標x56是小於xm ，因此我們可以刪除限制式k5x + t5。 這是因為當x>x56時，k5x + t5 < k6x + t6，這代表當x=x*>xm時，k5x + t5不可能是boundary function。 因此可以刪除條件式 k5x + t5(一對限制式中的一個)

41 簡化的二變數線性規劃演算法 時間複雜度分析
因為在每個迭代中，總是有限制式配對中的一個限制式會被刪除，因為總共有 n/2對限制式，因此有n/4個限制式在每一次的迭代中被刪除。 時間複雜度: T(n) = T(3n/4)+cn = O(n)

42 The End