分治演算法凸包

❶ 什麼是分治演算法

分治法就是將一個復雜的問題分成多個相對簡單的獨立問題進行求解，並且綜合所有簡單問題的解可以組成這個復雜問題的解。
例如快速排序演算法就是一個分治法的例子。即將一個大的無序序列排序成有序序列，等於將兩個無序的子序列排序成有序，且兩個子序列之間滿足一個序列的元素普遍大於另一個序列中的元素。

❷ 分治法的步驟

分治法在每一層遞歸上都有三個步驟：
分解：將原問題分解為若干個規模較小，相互獨立，與原問題形式相同的子問題；
解決：若子問題規模較小而容易被解決則直接解，否則遞歸地解各個子問題；
合並：將各個子問題的解合並為原問題的解。
它的一般的演算法設計模式如下：
Divide-and-Conquer(P)
1. if |P|≤n0
2. then return(ADHOC(P))
3. 將P分解為較小的子問題 P1 ,P2 ,...,Pk
4. for i←1 to k
5. do yi ← Divide-and-Conquer(Pi) △ 遞歸解決Pi
6. T ← MERGE(y1,y2,...,yk) △ 合並子問題
7. return(T)
其中|P|表示問題P的規模；n0為一閾值，表示當問題P的規模不超過n0時，問題已容易直接解出，不必再繼續分解。ADHOC(P)是該分治法中的基本子演算法，用於直接解小規模的問題P。因此，當P的規模不超過n0時直接用演算法ADHOC(P)求解。演算法MERGE(y1,y2,...,yk)是該分治法中的合並子演算法，用於將P的子問題P1 ,P2 ,...,Pk的相應的解y1,y2,...,yk合並為P的解。
根據分治法的分割原則，原問題應該分為多少個子問題才較適宜？
各個子問題的規模應該怎樣才為適當？
答: 但人們從大量實踐中發現，在用分治法設計演算法時，最好使子問題的規模大致相同。換句話說，將一個問題分成大小相等的k個子問題的處理方法是行之有效的。許多問題可以取 k = 2。這種使子問題規模大致相等的做法是出自一種平衡(balancing)子問題的思想，它幾乎總是比子問題規模不等的做法要好。
出處：網路
實踐題目：
給定一個順序表，編寫一個求出其最大值和最小值的分治演算法。
分析：
由於順序表的結構沒有給出，作為演示分治法這里從簡順序表取一整形數組數組大小由用戶定義，數據隨機生成。我們知道如果數組大小為 1 則可以直接給出結果，如果大小為 2則一次比較即可得出結果，於是我們找到求解該問題的子問題即: 數組大小 <= 2。到此我們就可以進行分治運算了，只要求解的問題數組長度比 2 大就繼續分治，否則求解子問題的解並更新全局解
以下是代碼。
*/
/*** 編譯環境TC ***/
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#define M 40
/* 分治法獲取最優解 */
void PartionGet(int s,int e,int *meter,int *max,int *min){
/* 參數:
* s 當前分治段的開始下標
* e 當前分治段的結束下標
* meter 表的地址
* max 存儲當前搜索到的最大值
* min 存儲當前搜索到的最小值
*/
int i;
if(e-s <= 1){ /* 獲取局部解，並更新全局解 */
if(meter[s] > meter[e]){
if(meter[s] > *max)
*max = meter[s];
if(meter[e] < *min)
*min = meter[e];
}
else{
if(meter[e] > *max)
*max = meter[e];
if(meter[s] < *min)
*min = meter[s];
}
return ;
}
i = s + (e-s)/2; /* 不是子問題繼續分治,這里使用了二分，也可以是其它 */
PartionGet(s,i,meter,max,min);
PartionGet(i+1,e,meter,max,min);
}
int main(){
int i,meter[M];
int max = INT_MIN; /* 用最小值初始化 */
int min = INT_MAX; /* 用最大值初始化 */
printf(The array's element as followed: );
rand(); /* 初始化隨機數發生器 */
for(i = 0; i < M; i ++){ /* 隨機數據填充數組 */
meter[i] = rand()%10000;
if(!((i+1)%10)) /* 輸出表的隨機數據 */
printf(%-6d ,meter[i]);
else
printf(%-6d,meter[i]);
}
PartionGet(0,M - 1,meter,&max,&min); /* 分治法獲取最值 */
printf( Max : %d Min : %d ,max,min);
system(pause);
return 0;
}

❸ 凸包 支撐線

點集Q的凸包(convex hull)是指一個最小凸多邊形，滿足Q中的點或者在多邊形邊上或者在其內。下圖中由紅色線段表示的多邊形就是點集Q={p0,p1,...p12}的凸包。
為了解決分治演算法、插入演算法和生長演算法都要求在構網之前給出所有點數據這個問題,實時三角網剖分演算法先利用部分離散點生成一個外輪廓為凸包的初始三角網.然後將點加入到既有三角網中,如點落在既有三角網的某一三角形中,將該點與三角形的頂點相連構建新的三角網;如點落在既有三角網外,找出該點向既有三角網外輪廓圍成的凸包發出的兩條支撐線,這兩條支撐線與既有凸包圍成了一個多邊形,再將這個多邊形剖分成三角網即可.最後利用局部優化演算法對所生成的三角網進行優化,使之成為Delaunay三角網.該演算法構網時無需預先給定所有數據點,可用於實時生成三角網;此外,通過對凸包進行分區管理,在搜尋凸包支撐線時,能預先確定出支撐點的范圍,減少了搜索工作量,提高了三角網的生成速度.

❹ 使用分治演算法解決的問題具備什麼特徵

分治法能解決的問題一般具有以下幾個特徵：

1、該問題的規模縮小到一定的程度就可以容易的解決。

2、該問題可以分解為若干個規模較小的相同問題，即該問題具有最優子結構性質。

3、利用該問題分解出的子問題的解可以合並為該問題的解。

4、該問題所分解出的自問題是相互獨立的，即子問題之間不包含子子問題。

(4)分治演算法凸包擴展閱讀

思想及策略

分治演算法的設計思想是：將一個難以直接解決的大問題，分割成一些規模小的相同的問題，一邊各個擊破，分而治之。

分治演算法的策略是：對於一個規模為n的問題，若該問題可以容易地解決（比如規模n比較小）則直接解決，否則將其分解成k個規模較小的自問題，這些子問題相互獨立且與元問題形式相同，遞歸地解這些子問題，然後將各子問題的解合並得到原問題的解。

❺ 分治演算法幾個經典例子

分治法，字面意思是「分而治之」，就是把一個復雜的1問題分成兩個或多個相同或相似的子問題，再把子問題分成更小的子問題直到最後子問題可以簡單地直接求解，原問題的解即子問題的解的合並，這個思想是很多高效演算法的基礎。

圖二

大整數乘法

Strassen矩陣乘法

棋盤覆蓋

合並排序

快速排序

線性時間選擇

最接近點對問題

循環賽日程表

漢諾塔

❻ 分治法指的是什麼呢

分治法指的是將原問題遞歸地分成若干個子問題，直到子問題滿足邊界條件，停止遞歸，將子問題逐個解決（一般是同種方法），將已經解決的子問題合並，最後，演算法會層層合並得到原問題的答案。

分治演算法步驟：

分：遞歸地將問題分解為各個的子問題（性質相同的，相互獨立的子問題）。

治：將這些規模更小的子問題逐個擊破。

合：將已解決的問題逐層合並，最終得出原問題的解。

分治法適用條件

1、問題的規模縮小到一定的規模就可以較容易地解決。

2、問題可以分解為若干個規模較小的模式相同的子問題，即該問題具有最優子結構性質。

3、合並問題分解出的子問題的解可以得到問題的解。

4、問題所分解出的各個子問題之間是獨立的，即子問題之間不存在公共的子問題。

❼ 點集的Delaunay三角剖分方法

3.2.1.1 基本理論

B.Delaunay於1934年提出了Delaunay三角網格的概念，它是Voronoi圖(簡稱V圖)的幾何對偶圖，具有嚴格的數學定義和完備的理論基礎。

圖3.1 Voronoi圖(虛線)及對應的Delaunay三角剖分(實線)

3.2.1.1.1 Voronoi圖

假設V={v₁，v₂，…，v_N}，N≥3是歐幾里得平面上的一個點集，並且這些點不共線，四點不共圓。用d(v_i，v_j)表示點v_i與v_j間的歐幾里得距離。

設x為平面上的點，則:

區域V_(i)={x∈E²d(x，v_i)≤d(x，v_j)，j=1，2，…，N，j≠i}稱為Voronoi多邊形，也稱為該點的鄰域。點集中所有點的Voronoi多邊形組成Voronoi圖，如圖3.1所示。

平面上的Voronoi圖可以看做是點集V中的每個點作為生長核，以相同的速率向外擴張，直到彼此相遇為止而在平面上形成的圖形。除最外層的點形成開放的區域外，其餘每個點都形成一個凸多邊形。

3.2.1.1.2 Delaunay三角剖分

Delaunay三角形網格為V圖的幾何對偶圖。在二維平面中，點集中若無四點共圓，則該點集V圖中每個頂點恰好是3個邊的公共頂點，並且是3個Voronoi多邊形的公共頂點;上述3個Voronoi多邊形所對應的點集中的點連成的三角形稱為與該Voronoi頂點對應的Delaunay三角形，如圖3.1所示。如果一個二維點集中有四點共圓的情況，此時，這些點對應的Voronoi多邊形共用一個Voronoi頂點，這個公共的Voronoi頂點對應多於3個Voronoi多邊形，也就是對應於點集中多於3個的點;這些點可以連成多於一個的三角形。此時，可以任意將上述幾個點形成的凸包劃分為若干三角形，這些三角形也稱為和這個Voronoi頂點對應的Delaunay三角形。

所有與Voronoi頂點對應的Delaunay三角形就構成了Delaunay三角剖分。當無退化情況(四點共圓)出現時，點集的Delaunay三角剖分是唯一的。

3.2.1.1.3 Delaunay三角剖分的特性

Delaunay三角剖分具有兩個重要特性:

(1)最小角最大化特性:即要求三角形的最小內角盡量最大，具體地說是指在兩個相鄰的三角形構成凸四邊形的對角線，在相互交換後，6個內角的最小角不再增大，並且使三角形盡量接近等邊。

(2)空外接圓特性:即三角形的外接圓中不包含其他三角形的頂點(任意四點不能共圓)，該特性保證了最鄰近的點構成三角形，使三角形的邊長之和盡量最小。

3.2.1.2 常用演算法

Delaunay三角剖分方法是目前最流行的通用的全自動網格生成方法之一。比較有效的Delaunay三角剖分演算法有分治演算法、逐點插入法和三角網生長法等(Tsai，1993)，其中逐點插入法由於其演算法的簡潔性且易於實現，因而獲得廣泛的應用。其主要思路是先構建一個包含點集或區域的初始網格，再依次向初始網格中插入點，最後形成Delaunay三角剖分。

採用逐點插入法建立Delaunay三角網的演算法思想最初是由Lawson於1977年提出的(Lawson，1977)，Bowyer和Watson等先後對該演算法進行了發展和完善(Bowyer，1981;Watson，1981)。目前涌現出的大量逐點插入法中，主要為以Lawson演算法代表的對角線交換演算法和以Bowyer-Watson演算法代表的空外接圓法。

3.2.1.2.1 Lawson演算法

Lawson演算法的主要思想是將要插入的數據點逐一插入到一個已存在的Delaunay三角網內，然後再用局部優化演算法(Local Optimization Procere，LOP)優化使其滿足Delau-nay三角網的要求，其主要步驟如下:

圖3.7 Bowyer-Watson演算法剖分實例

❽ 《演算法導論》（第三版）目錄

1.1 演算法

1.2 作為一種技術的演算法

2.1 插入排序

2.2 分析演算法

2.3 設計演算法

2.3.1 分治法

2.3.2 分析分治演算法

3.1 漸近記號

3.2 標准記號與常用函數

4.1 最大子數組問題

4.2 矩陣乘法的 Strassen 演算法

4.3 用代入法求解遞歸式

4.4 用遞歸樹方法求解遞歸式

4.5 用主方法求解遞歸式

*4.6 證明主定理

4.6.1 對 b 的冪證明主定理

4.6.2 向下取整和向上取整

5.1 僱傭問題

5.2 指示器隨機變數

5.3 隨機演算法

*5.4 概率分析和指示器隨機變數的進一步使用

5.4.1 生日悖論

5.4.2 球與箱子

5.4.3 特徵序列

5.4.4 在線僱傭問題

6.1 堆

6.2 維護堆的性質

6.3 建堆

6.4 堆排序演算法

6.5 優先隊列

7.1 快速排序的描述

7.2 快速排序的性能

7.3 快速排序的隨機化版本

7.4 快速排序分析

7.4.1 最壞情況分析

7.4.2 期望運行時間

8.1 排序演算法的下界

8.2 計數排序

8.3 基數排序

8.4 桶排序

9.1 最小值和最大值

9.2 期望為線性時間的選擇演算法

9.3 最壞情況為線性時間的選擇演算法

10.1 棧和隊列

10.2 鏈表

10.3 指針和對象的實現

10.4 有根樹的表示

11.1 直接定址表

11.2 散列表

11.3 散列函數

11.3.1 除法散列法

11.3.2 乘法散列法

*11.3.3 全域散列法

11.4 開放定址法

11.5 完全散列

12.1 什麼是二叉樹

12.2 查詢二叉搜索樹

12.3 插入和刪除

12.4 隨機構建二叉搜索樹

13.1 紅黑樹的性質

13.2 旋轉

13.3 插入

13.4 刪除

14.1 動態順序統計

14.2 如何擴張數據結構

14.3 區間樹

15.1 鋼條切割

15.2 矩陣鏈乘法

15.3 動態規劃原理

15.4 最長公共子序列

15.5 最優二叉搜索樹

16.1 活動選擇問題

16.2 貪心演算法原理

16.3 赫夫曼編碼

*16.4 擬陣和貪心演算法

*16.5 用擬陣求解任務調度問題

17.1 聚合分析

17.2 核演算法

17.3 勢能法

17.4 動態表

17.4.1 表擴張

17.4.2 表擴張和收縮

18.1 B 樹的定義

18.2 B 樹上的基本操作

18.3 從 B 樹上刪除關鍵字

19.1 斐波那契結構

19.2 可合並堆操作

19.3 關鍵字減值和刪除一個結點

19.4 最大度數的界

20.1 基本方法

20.2 遞歸結構

20.2.1 原型 van Emde Boas 結構

20.2.2 原型 van Emde Boas 結構上的操作

20.3 van Emde Boas 樹及其操作

20.3.1 van Emde Boas 樹

20.3.2 van Emde Boas 樹的操作

21.1 不相交集合的操作

21.2 不相交集合的鏈表表示

21.3 不相交集合森林

*21.4 帶路徑壓縮的按秩合並的分析

22.1 圖的表示

22.2 廣度優先搜索

22.3 深度優先搜索

22.4 拓撲排序

22.5 強連通分量

23.1 最小生成樹的形成

23.2 Kruskal 演算法和 Prim 演算法

24.1 Bellman-Ford 演算法

24.2 有向無環圖中的單源最短路徑問題

24.3 Dijkstra 演算法

24.4 差分約束和最短路徑

24.5 最短路徑性質的證明

25.1 最短路徑和矩陣乘法

25.2 Floyd-Warshall 演算法

25.3 用於稀疏圖的 Johnson 演算法

26.1 流網路

26.2 Ford-Fulkerson 方法

26.3 最大二分匹配

*26.4 推送-重貼標簽演算法

*26.5 前置重貼標簽演算法

27.1 動態多線程基礎

27.2 多線程矩陣乘法

27.3 多線程歸並排序

28.1 求解線性方程組

28.2 矩陣求逆

28.3 對稱正定矩陣和最小二乘逼近

29.1 標准型和鬆弛型

29.2 將問題表達為線性規劃

29.3 單純形演算法

29.4 對偶性

29.5 初始基本可行解

30.1 多項式的表示

30.2 DFT 和 FFT

30.3 高效 FFT 實現

31.1 基礎數論概念

31.2 最大公約數

31.3 模運算

31.4 求解模線性方程

31.5 中國余數定理

31.6 元素的冪

31.7 RSA 公鑰加密系統

*31.8 素數的測試

*31.9 整數的因子分解

32.1 樸素字元串匹配演算法

32.2 Rabin-Karp 演算法

32.3 利用有限自動機進行字元串匹配

32.4 Knuth-Morris-Pratt 演算法

33.1 線段的性質

33.2 確定任意一對線段是否相交

33.3 尋找凸包

33.4 尋找最近點對

34.1 多項式時間

34.2 多項式時間的驗證

34.3 NP 完全性與可歸約性

34.4 NP 完全性的證明

34.5 NP 完全問題

34.5.1 團問題

34.5.2 頂點覆蓋問題

34.5.3 哈密頓迴路問題

34.5.4 旅行商問題

34.5.5 子集和問題

35.1 頂點覆蓋問題

35.2 旅行商問題

35.2.1 滿足三角不等式的旅行商問題

35.2.2 一般旅行商問題

35.3 集合覆蓋問題

35.4 隨機化和線性規劃

35.5 子集和問題

A.1 求和公式及其性質

A.2 確定求和時間的界

B.1 集合

B.2 關系

B.3 函數

B.4 圖

B.5 樹

B.5.1 自由樹

B.5.2 有根樹和有序樹

B.5.3 二叉樹和位置樹

C.1 計數

C.2 概率

C.3 離散隨機變數

C.4 幾何分布與二項分布

C.5 二項分布的尾部

D.1 矩陣與矩陣運算

D.2 矩陣的基本性質

❾ 分治演算法是什麼呢

分治演算法的基本思想是將一個規模為N的問題分解為K個規模較小的子問題，這些子問題相互獨立且與原問題性質相同。求出子問題的解，就可得到原問題的解。即一種分目標完成程序演算法，簡單問題可用二分法完成。

解題步驟

分治法解題的一般步驟：

（1）分解，將要解決的問題劃分成若干規模較小的同類問題；

（2）求解，當子問題劃分得足夠小時，用較簡單的方法解決；

（3）合並，按原問題的要求，將子問題的解逐層合並構成原問題的解。

❿ 一、分治法

分治演算法的主要思想是將原問題遞歸地分成若干個子問題，直到子問題滿足邊界條件，停止遞歸。將子問題逐個擊破(一般是同種方法)，將已經解決的子問題合並，最後，演算法會層層合並得到原問題的答案。

使用分治演算法其中一個要求是，子問題合並的代價不能太大，否則就起不了降低時間復雜度的效果了。

如果用傳統的遍歷法，時間復雜度過大，若使用分治法，則時間復雜度大大降低。