分治演算法 與 刪尋演算法 各個擊破與化整為零.

Presentation on theme: "分治演算法 與 刪尋演算法 各個擊破與化整為零."— Presentation transcript:

1 分治演算法 與 刪尋演算法 各個擊破與化整為零

2 2.1 分治演算法基本概念

3 分治解題策略 分治(divide and conquer)演算法使用分治解題策略解決問題。分治是很好的解題策略，可以很有效率的解決問題，又稱為分割再征服策略或各個擊破策略。一般而言，分治演算法具有三個階段: 分割階段:如果問題規模很小，就直接解決此問題；否則，將原本的問題分割(divide)成2個或多個子問題(subproblem)。 克服階段:用相同的演算法遞迴地(recirsively)解決或克服(conquer)所有的子問題。 合併階段:合併(merge)所有子問題的解答成為原本問題的解答。

4 使用分治解題策略的演算法 合併排序演算法 快速排序演算法 缺陷棋盤填滿演算法 二維求秩演算法 二維極大點演算法 最近二維點對演算法

5 2.2 合併排序演算法

6 合併排序演算法 在本單元中，我們介紹使用分治解題策略的合併排序(merge sort) 演算法。
合併排序演算法由現代電腦之父，內儲程式(stored program)電腦架構發明之人之一的紐曼博士， 在西元1945 年發明。 約翰·馮·紐曼（John von Neumann，1903年12月28日－1957年2月8日），出生於匈牙利的美國籍猶太人數學家，現代電腦創始人之一。他在電腦科學、經濟、物理學中的量子力學及幾乎所有數學領域都作過重大貢獻。(圖及說明摘自維基百科)

7 合併排序演算法(續) 假設我們要使用合併排序演算法來將陣列A 中的n 個元素或資料(索引為0,...,n−1) 依照其值以由小而大的次序排列
克服: 遞迴地排序兩個子陣列。 合併: 最後合併兩個已完成排序的子陣列，即可完成原來陣列的排序。 合併排序演算法如Algorithm 6 (MergeSort)所示，而在此演算法中另外使用到如Algorithm 7所示的Merge演算法以合併二個子陣列。

8 合併排序演算法(續)

9 合併排序演算法(續)

10 合併排序演算法(續) 我們以下頁圖中的實例來看合併排序演算法的運作過程：
假設有一個陣列具有8 個元素85、24、63、50、17、31、96、50’，索引(index) 為0,...,7，其中50 與50’二個元素的值都是50，但是為了區別起見，我們將之標示為50 與50’。

11 合併排序演算法(續)

12 合併排序演算法(續) 在整個合併排序演算法的執行過程中，50 與50’的相對位置一直保持不變，因此如同氣泡排序與插入排序演算法一樣，合併排序演算法也是一個穩定(stable) 排序演算法。 合併排序演算法需要額外的與原來陣列大小相同的記憶體空間來輔助排序的進行，因此合併排序演算法不是就地(in place) 演算法，它的空間複雜度為O(n)，n 為需要排序陣列的元素個數。

13 合併排序演算法(續) T(n)=2T(n/2)+n 以下我們分析合併排序演算法的時間複雜度。

14 合併排序演算法(續) 我們遞迴地將T(n)=2T(n/2)+n中的n取代為n/2, n/4, ...，則我們可以得到:
T(n) = 2T(n/2) + n = 2(2T(n/4)+(n/2)) + n = 4T(n/4) + n + n = 4(2T(n/8)+(n/4)) + 2n= 8T(n/8) + 3n = .... = 2k T(n/2k) + kn 當陣列只有一個元素時，合併排序演算法不會再進行遞迴呼叫，會直接回轉(return)，因此我們可得T(1) = 1。

15 合併排序演算法(續) 假設n = 2k，則k = log2 n。請注意，未來若我們不特別指定log函數的基底，則代表基底為2。
T(n) = n log n + 2k = n log n + n = O(n log n) 對所有的狀況(最佳、最差與平均狀況) 而言，合併排序演算法的時間複雜度都是O(n log n)。

16 2.3 快速排序演算法

17 快速排序演算法 以下我們首先介紹快速排序(quick sort)演算法。此演算法由獲得計算機領域最高榮譽圖靈獎(Turing Award)的Hoare博士於1962年發表。 如其名稱所示，此排序演算法的排序速度相當快，因此使用相當廣泛。 查爾斯·安東尼·理察·霍爾爵士(Charles Antony Richard Hoare，縮寫為 C. A. R. Hoare，1934年1月11日－ )，生於斯里蘭卡可倫坡，英國計算機科學家，圖靈獎得主。他設計了可快速進行排序程序的快速排序(quick sort)演算法，提出可驗證程式正確性的霍爾邏輯(Hoare logic) 、以及提出可訂定並時程序(concurrent process)的交互作用(如哲學家用餐問題(dining philosophers problem)的交談循序程續(CSP, Communicating Sequential Processes)架構 。 (圖及說明摘自維基百科)

18 快速排序演算法(續) 快速排序演算法使用分治解題策略，其做法如下所述:
分割: 選一個元素p當作中樞(pivot)元素將陣列分割為2部份：SP及LP，其中SP (smaller part)包含所有小於或等於p的元素；而LP(larger part)則包含所有大於p的元素。 克服:完成陣列分割(partition)之後，快速排序演算法持續遞迴地(recursively)進行SP部份與LP部份的元素排序。 合併: 最後再將SP、p及LP合併即可完成排序。

19 快速排序演算法(續) Algorithm 8為快速排序演算法，此演算法使用二個指標(「左指標」l 與「右指標」r) 將陣列中索引在「左界」lb 及「右界」rb 範圍內的元素分割為二部份。

20 快速排序演算法(續)

21 快速排序演算法(續) 以下我們舉實例來看快速排序演算法的運作過程。
假設有一個陣列具有8個元素85、24、63、50、17、50'、96、58 ，索引(index)為0,...,7，其中50與50’二個元素的值都是50，但是為了區別起見，我們將之標示為50與50’。 下圖展示快速排序演算法第一次將陣列分割為二個部份的過程。

22 快速排序演算法(續)

23 快速排序演算法(續) 在整個快速排序演算法的執行過程中，50與50’的相對位置產生變化，因此快速排序演算法不是一個穩定(stable)排序演算法。 快速排序演算法不需要額外的記憶體空間來輔助排序的進行，因此快速排序演算法是就地(in place)演算法，它的空間複雜度為O(1)。

24 快速排序演算法(續) 以下我們分析快速排序演算法的時間複雜度。
在最佳狀況下，快速排序演算法每次都將陣列分割為二個大小相同或幾乎相同的子陣列(我們可以將分割後的二個子陣列都視為是原陣列的1/2大小) 。 假設利用快速排序演算法針對具有n 個元素的陣列(也就是說輸入規模為n) 進行排序的時間複雜度為T(n)，針對最佳狀況，我們可以得到以下的式子: T(n)=n+2T(n/2) 這是因為當指標l 持續往右移，而同時指標r 持續往左移而交叉時(也就是說 l  r 時)，代表陣列分割完成。指標每次移動一個位置需要一次的數值比較操作，因此要完成陣列分割需要執行n 次數值比較操作。而陣列分割完成之後，快速排序演算法就利用遞迴的方式分別完成二個大小相同的(均為n/2) 子陣列排序。 如合併排序演算法的分析一樣，我們可得 T(n)=O(n log n)

25 快速排序演算法(續) 以下我們分析快速排序演算法的最差狀況時間複雜度。 當陣列的n 個元素已經依由小而大的方式排列的情況下會產生最差狀況。
在此情況下，快速排序演算法首先在經過n 次數值比較操作之後，將陣列分割為單一一個所有元素都比中樞元素小，具有n − 1 個元素的子陣列。 經過遞迴呼叫，快速排序演算法再利用n − 1 次數值比較操作將陣列分割為單一一個所有元素都比新中樞元素小，具有n − 2 個元素的子陣列。 如此不斷遞迴執行，直到陣列分割出僅包含一個元素的子陣列為止。 同樣假設快速排序演算法的時間複雜度為T(n)，針對最差狀況，我們可以得到以下的式子: T(n) = n + (n − 1) + (n − 2) =n(n − 1)/2 = O(n2)

26 快速排序演算法(續)

27 快速排序演算法(續)

28 快速排序演算法(續) n-1, n-2,…,1

29 快速排序演算法(續)

30 排序演算法比較

31 2.4 缺陷棋盤填滿演算法

32 缺陷棋盤填滿演算法說明 缺陷棋盤填滿演算法使用分治策略解決缺陷棋盤填滿問題，使用三格骨牌填滿缺陷棋盤
以下我們先定義甚麼是棋盤、缺陷棋盤及三格骨牌 然後我們定義缺陷棋盤填滿問題 最後我們介紹缺陷棋盤填滿演算法

33 棋盤的定義 一個棋盤是一個 n x n方格(grid)，具有n2個單格(cell)，其中n2而且n是2的幂(a power a 2)

34 缺陷棋盤的定義 缺陷棋盤是有一單格(cell)無法使用的棋盤。 X 8x8 X 4x4 X 2x2

35 三格骨牌的定義 三格骨牌(Triomino)為一L型骨牌，可填滿一棋盤上的3個單格。 三格骨牌有4種方向。

36 缺陷棋盤填滿問題 放置(n2 - 1)/3 個三格骨牌在n x n缺陷棋盤上，使得全部(n2 – 1)個非缺陷單格都被填滿。 X 8x8
For the tiling to be possible, (n2 - 1) must be divisible by 3 whenever n is a power of 2. So, the tiling algorithm that follows actually provides a proof the this is so. 4x4 X X 2x2

37 缺陷棋盤填滿演算法 Algorithm 缺陷棋盤填滿演算法 Input: n x n缺陷棋盤， n2而且n是2的幂
Output: 以三格骨牌填滿的n x n缺陷棋盤 步驟1: 若n=2，則旋轉一個三格骨牌直接填滿缺陷棋盤，回傳此2 x 2缺陷棋盤並結束。 步驟2: 將缺陷棋盤分為3個(n/2) x (n/2)棋盤及1個(n/2) x (n/2)缺陷棋盤，旋轉一個三格骨牌填滿3個棋盤中相鄰的單格，可使3個棋盤成為缺陷棋盤，我們可得4個(n/2) x (n/2)缺陷棋盤。 步驟3: 遞迴地使用缺陷棋盤填滿演算法以三格骨牌填滿步驟2的4個(n/2) x (n/2)缺陷棋盤，回傳原始n x n缺陷棋盤並結束。

38 缺陷棋盤填滿演算法實例 將8 x 8缺陷棋盤分割成4個更小的 4 x 4 棋盤。

39 缺陷棋盤填滿演算法實例(續) 放置1個三格骨牌在3個4 x 4正常棋盤的相鄰單格，讓他們也變成缺陷棋盤。

40 缺陷棋盤填滿演算法實例(續) 以遞迴方式填滿右上角之缺陷4 x 4棋盤。 X 以遞迴方式填滿左上角之缺陷4 x 4棋盤….。

41 2.5 二維求秩演算法

42 二維求秩演算法說明 二維求秩(2D rank finding)演算法使用分治策略解決二維求秩問題
以下我們先定義支配(dominate)及 秩(rank) 然後我們定義二維求秩問題 最後我們介紹二維求秩演算法

43 支配及秩的定義 令A = (ax, ay), B = (bx, by)為二維XY平面上的點，則我們說A支配(dominate)B(記為AB)若且唯若 ax> bx 且 ay > by。 給定一個由二維平面點所構成的集合S，點A之秩(rank)定義為集合S中有多少個點被A所支配。 E.G.: BA, CA, DC, EA E.G.: rank(A)=0, rank(B)=1, rank(C)=1, rank(D)=2, rank(E)=2

44 二維求秩問題 給定一個由n個二維平面點所構成的集合S，求出S中所有點的秩。
可以用窮舉(exhaustive)演算法，比較所有的可能成對點，時間複雜度為O(n2)。

45 二維求秩演算法 Algorithm 二維求秩演算法 Input: n個二維平面點所構成的集合S，n1
Output: 集合S中所有點的秩(rank) 步驟1: 若n=1，則回傳S中唯一一個點的秩為0並結束。 步驟2: 找出所有點的X軸中位數(median)畫出垂直於X軸的直線L，將S中的點分為二個集合SL與SR。 步驟3: 遞迴地使用二維求秩演算法分別求出SL與SR中所有點的秩。 步驟4: 根據Y軸值排序所有在S(S=SLSR)中的點，依序掃描所有點且求出每一個在SR的點i排在多少在SL的點的後面(記為updatei)，並將點i的秩加上updatei；最後回傳S中所有點的秩並結束。

46 二維求秩演算法範例 假定給定平面上10個點，依其X軸中位數(median)畫出直線L將之分為二個集合SL與SR。下圖顯示SR中所有點的秩的更新。

47 二維求秩演算法時間複雜度分析 步驟時間複雜度: 步驟2: c1n log n (排序) 步驟4: c2n log n (排序)
Algorithm 二維求秩演算法 Input: n個二維平面點所構成的集合S，n1 Output: 集合S中所有點的秩(rank) 步驟1: 若n=1，則回傳S中唯一一個點的秩為0並結束。 步驟2: 找出所有點的X軸中位數(median)畫出垂直於X軸的直線L，將S中的點分為二個集合SL與SR。 步驟3: 遞迴地使用二維求秩演算法分別求出SL與SR中所有點的秩。 步驟4: 根據Y軸值排序所有在S(S=SLSR)中的點，依序掃描所有點且求出每一個在SR的點i排在多少在SL的點的後面(記為updatei)，並將點i的秩加上updatei；最後回傳S中所有點的秩並結束。 步驟時間複雜度: 步驟2: c1n log n (排序) 步驟4: c2n log n (排序) 總時間複雜度: T(n) = 2T(n/2) + c1n log n + c2n log n = 2T(n/2) + cn log n = 2(2T(n/4)+c(n/2) log (n/2))+ cn log n = 4T(n/4) + cn log (n/2) + cn log n = nT(1) + cn(log n + log (n/2)+ log (n/4) +…+ log 2)  nT(1) + cn (log n (log n+ log 2))/2 (其中T(1)=1) = O(n log2n)

48 2.6 二維極大點演算法

49 二維極大點演算法說明 二維極大點(2D maxima finding)演算法使用分治策略解決二維極大點問題
以下我們先定義支配(dominate)及 極大點(maxima) 然後我們定義二維極大點問題 最後我們介紹二維極大點演算法

50 支配及極大點的定義 令A = (ax, ay), B = (bx, by)為二維XY平面上的點，則我們說A支配(dominate)B(記為AB)若且唯若 ax> bx 且 ax > by。 如果一個點不被任何其他點所支配，我們就稱此點不被支配(non-dominated)，或稱此點為極大點(maxima)。 極大點不只一個。

51 二維極大點問題 給定一個由n個二維平面點所構成的集合S，求出S中的極大點(maxima)。
可以用窮舉(exhaustive)演算法，比較所有的可能成對點，其時間複雜度為O(n2)。

52 二維極大點演算法 Algorithm 二維極大點演算法 Input: n個二維平面點所構成的集合S，n1
Output: 集合S中所有的極大點(maxima) 步驟1: 若n=1，則回傳S中唯一一個點為極大點並結束。 步驟2: 找出所有點的X軸中位數(median)畫出垂直於X軸的直線L，將S中的點分為二個集合SL與SR。 步驟3: 遞迴地使用二維極大點演算法分別求出SL與SR中所有的極大點。 步驟4: 在SR的極大點中找出最大的Y軸值y*。 對每個在SL中的極大點，如果該點的Y軸值小於y*，則標示該點為不是極大點。回傳SR中的極大點和SL中未被標示的極大點。

53 二維極大點演算法範例 假定給定平面上10個點，依其X軸中位數(median)畫出直線L將之分為二個集合SL與SR。下圖顯示SL中極大點的更新。

54 二維極大點演算法時間複雜度分析 步驟時間複雜度: 步驟2: c1n log n (排序) 步驟4: c2n (依序檢查) 總時間複雜度:
Algorithm 二維極大點演算法 Input: n個二維平面點所構成的集合S，n1 Output: 集合S中所有的極大點(maxima) 步驟1: 若n=1，則回傳S中唯一一個點為極大點並結束。 步驟2: 找出所有點的X軸中位數(median)畫出垂直於X軸的直線L，將S中的點分為二個集合SL與SR。 步驟3: 遞迴地使用二維極大點演算法分別求出SL與SR中所有的極大點。 步驟4: 在SR的極大點中找出最大的Y軸值y*。 對每個在SL中的極大點，如果該點的Y軸值小於y*，則標示該點為不是極大點。回傳SR中的極大點和SL中未被標示的極大點。 步驟時間複雜度: 步驟2: c1n log n (排序) 步驟4: c2n (依序檢查) 總時間複雜度: T(n) = 2T(n/2) + c1n log n + c2n = 2T(n/2) + cn log n = 2(2T(n/4)+c(n/2) log (n/2))+ cn log n = 4T(n/4) + cn log (n/2) + cn log n = nT(1) + cn(log n + log (n/2)+ log (n/4) +…+ log 2) = nT(1) + cn (log n (log n+ log 2))/2 (其中T(1)=1) = O(n log2n)

55 二維極大點演算法時間複雜度分析(續) 步驟時間複雜度: 步驟2: c1n (以刪尋演算法求中位數) 步驟4: c2n (依序檢查)
Algorithm 二維極大點演算法 Input: n個二維平面點所構成的集合S，n1 Output: 集合S中所有的極大點(maxima) 步驟1: 若n=1，則回傳S中唯一一個點為極大點並結束。 步驟2: 找出所有點的X軸中位數(median)畫出垂直於X軸的直線L，將S中的點分為二個集合SL與SR。 步驟3: 遞迴地使用二維極大點演算法分別求出SL與SR中所有的極大點。 步驟4: 在SR的極大點中找出最大的Y軸值y*。 對每個在SL中的極大點，如果該點的Y軸值小於y*，則標示該點為不是極大點。回傳SR中的極大點和SL中未被標示的極大點。 步驟時間複雜度: 步驟2: c1n (以刪尋演算法求中位數) 步驟4: c2n (依序檢查) 總時間複雜度: T(n) = 2T(n/2) + c1n + c2n = 2T(n/2) + cn = 2(2T(n/4)+c(n/2))+ cn = 4T(n/4) + cn + cn = nT(1) + cn+cn+…+cn (其中總共log n個cn) = nT(1) + cn log n (其中T(1)=1) = O(n log n)

56 2.7 最近二維點對演算法

57 最近二維點對演算法說明 最近二維點對(closest pair of 2D points) 演算法使用分治策略解決最近二維點對問題
以下我們先定義最近二維點對問題 然後我們介紹最近二維點對演算法

58 最近二維點對問題 給定n個二維平面點，找出其中距離最近的二個點的距離。
可以用窮舉(exhaustive)演算法，比較所有的成對點，其時間複雜度為O(n2)。

59 最近二維點對演算法 Algorithm 最近二維點對演算法 Input: n個二維平面點所構成的集合S，n2
Output: 集合S中距離最近的二個點的距離d 步驟1: 根據X軸值與Y軸值來事先排序S中的點。 步驟2: 若n=2，則回傳S中二點的距離d並結束。 步驟3: 找出所有點的X軸中位數(median)m畫出垂直於X軸的直線L，將S中的點分為二個集合SL與SR。 步驟4: 遞迴地使用二維點對演算法分別求出SL與SR中最近二維點對的距離dL與dR，且令 d = min(dL, dR)。

60 最近二維點對演算法(續) 步驟5: 將X軸值介於m-d與m+d的所有點的Y軸值投射至直線L上。針對於每個X軸值落在範圍介於m-d與m之間的點p，以yp記錄其Y軸值，並尋找所有X軸值落在範圍介於m與m+d之間，且Y軸值介於yP+d 與 yP-d之間的所有點，若存在一點與p之距離為小於d的d’，則令d=d’。回傳d並結束執行。

61 最近二維點對演算法執行說明

62 最近二維點對演算法時間複雜度分析 步驟時間複雜度: 步驟 1: c1n log n (事先排序) 步驟 2~5:
Algorithm 最近二維點對演算法 Input: n個二維平面點所構成的集合S，n2 Output: 集合S中距離最近的二個點的距離d 步驟1: 根據X軸值與Y軸值來事先排序S中的點。 步驟2: 若n=2，則回傳S中二點的距離d並結束。 步驟3: 找出所有點的X軸中位數(median)m畫出垂直於X軸的直線L，將S中的點分為二個集合SL與SR。 步驟4: 遞迴地使用二維點對演算法分別求出SL與SR中最近二維點對的距離dL與dR，且令 d = min(dL, dR)。 步驟5: 將X軸值介於m-d與m+d的所有點的Y軸值投射至直線L上。針對於每個X軸值落在範圍介於m-d與m之間的點p，以yp記錄其Y軸值，並尋找所有X軸值落在範圍介於m與m+d之間，且Y軸值介於yP+d 與 yP-d之間的所有點，若存在一點與p之距離為小於d的d’，則令d=d’。回傳d並結束執行。 步驟時間複雜度: 步驟 1: c1n log n (事先排序) 步驟 2~5: T’(n) = c2n log n 總時間複雜度: T(n) = c1n log n + c2n log n = O(n log n)

63 2.8 刪尋演算法基本概念

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

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

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

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

68 2.9 二元搜尋演算法

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

70 二元搜尋演算法(續)

71 二元搜尋演算法範例 已排序好的陣列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不在陣列中)

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

73 二元搜尋演算法時間複雜度分析 假設搜尋範圍內有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)

74 2.10 選取與中位數演算法

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

76 以刪尋策略解決選取問題 令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。

77 以刪尋策略解決選取問題(續) 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的元素)

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

79 刪尋選取演算法(續) 步驟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) 。

80 刪尋選取演算法時間複雜度分析 總時間複雜度: 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

81 刪尋選取演算法時間複雜度分析(續) 等比級數公式 令 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) 等比級數公式

82 2.11 限制的一圓心演算法

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

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

85 限制的一圓心問題 限制的一圓心問題(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.

86 限制的一圓心演算法 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).

87 限制的一圓心演算法(續) 步驟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.

88 限制的一圓心演算法執行展示 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

89 限制的一圓心演算法時間複雜度分析 限制的一圓心演算法使用刪尋策略解決問題，在每個迭代均刪除一部份輸入資料。由於每個迭代均有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)

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

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

92 二變數線性規劃範例

93 線性規劃或線性最佳化(續) 線性規劃 (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 揭曉。 他設計出一項 「內 點法」 來解線性規劃問題, 不但理論上較 「單 形法」 為優, 而且經由實際驗證適合解決超大 型的問題。

94 著名的線性規劃演算法 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] 以上資料參考維基百科:

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

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

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

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

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

100 限制式刪除範例 如左圖，因為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(一對限制式中的一個)

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

102 The End

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