《算法分析與設計》 課件 3.5 凸多邊形的最優(yōu)三角剖分

§3.5凸多邊形的最優(yōu)三角剖分問題補充：Catalan數(shù)

一個凸多邊形通過不相交于n邊形的對角線，把n邊形拆分成若干三角形，不同拆分的數(shù)

目用hn表示，如h3=1,h5=5。1.遞推關系兩條定理：(a)hn+1=h2hn+h3hn-1+...hnh2證明：如右圖所示，V1Vn+1Vi將凸n+1邊形分割成三部分：1

n+1

iV

V V、k邊形以及n-k+2邊形。令Vi取V2，V3，……Vn，對應K=2，3，……nVn+1V1V2VnV3Vin-k+2邊形k邊形hn+1=h2hn+h3hn-1+...hnh2(b)(n-3)hn=n/2*(h3hn-1+h4hn-2...hn-1h3)證明：如右圖所示，從

V1點向其它n-3(除V1、V2、Vn)個頂點引出n-3條對角線。對角線V1Vk將凸n邊形分割成兩部分，以V1Vk為拆分線的方案數(shù)為：hkhn-k+2

。Vk取V3，V4,……

Vn-1對應K=3，4，……n-1求和為h3hn-1+h4hn-2+...hn-1h3V1V2VnVn-1VkV3以V2、V3、Vn取代V1點，也有類似的結(jié)果?？紤]

到對角線在兩個頂點重復計算，故有總對角線數(shù)：h3hn-1+h4hn-2+...hn-1h3又因為一個凸n邊形的剖分有n-3條對角線，每一條邊在計算剖分數(shù)時重復

n-3次，故有：(n-3)hn=n/2(h3hn-1+h4hn-2+...hn-1h3)V2V1

VnVn-1VkV32.Catalan數(shù)計算公式由(a)hn+1=h2hn+h3hn-1+...hnh2(b)(n-3)hn=n/2*(h3hn-1+h4hn-2...hn-1h3)及h2=1，得(n-3)hn=

n/2*(hn+1-2hn)2(n-3)hn=

nhn+1-2nhn(4n-6)

hn=

nhn+1令fn+1=nhn+1，即hn+1=fn+1/n，則有3.5.1問題描述多邊形是平面上一條分段線性的閉曲線。也就是說，多邊形是由一系列首尾相接的直線段組成的。組成多邊形的各直線段稱為該多邊形的邊。多邊形相接兩條邊的連接點稱為多邊形的頂點。若多邊形的邊之間除了連接頂點外沒有別的公共點，則稱該多邊形為簡單多邊形。一個簡單多邊形將平面分為3個部分：被包圍在多邊形內(nèi)的所有點構(gòu)成了多邊形的內(nèi)部；多邊形本身構(gòu)成多邊形的邊界；而平面上其余的點構(gòu)成了多邊形的外部。當一個簡單多邊形及其內(nèi)部構(gòu)成一個閉凸集時，稱該簡單多邊形為凸多邊形。也就是說凸多邊形邊界上或內(nèi)部的任意兩點所連成的直線段上所有的點均在該凸多邊形的內(nèi)部或邊界上。通常，用多邊形頂點的逆時針序列來表示一個凸多邊形，即

P=<v0,v1,…,vn-1>表示具有n條邊v0v1，v1v2，…,vn-1vn的一個凸多邊形，其中，約定v0=vn。若vi與vj是多邊形上不相鄰的兩個頂點，則線段vivj稱為多邊的一條弦。弦

將多邊形分割成凸的兩個子多邊形<v

,v

,…i

i+1和<vj

,vj+1

,…,vi>。多邊形的三角剖分是一個將多邊形分割互不重迭的三角形的弦的集合T。V0V1V2V3V4(a)

(b)圖1一個凸7邊形的4個不同的三角剖分V5V6V0V1V2V3V4V5V6圖1一個凸7邊形的4個不同的三角剖分V0V0V1V6V1V6V2V4V3(c)V5V2V4V3(d)V5

在凸多邊形P的一個三角剖分T中，各弦互不相交且弦數(shù)已達到最大，即P的任一不在T中的弦必與T中某一弦相交。在一個有n個頂點的凸多邊形的三角剖分中，恰好有n-3條弦和n-2個三角形。

凸多邊形最優(yōu)三角剖分的問題是：給定一個凸多邊形P=<v0

,v1

,…,vn-1>以及定義在由多邊形的邊和弦組成的三角形上的權(quán)函數(shù)ω。要求確定該凸多邊形的一個三角剖分，使得該三角剖分對應的權(quán)即剖分中諸三角形上的權(quán)之和為最小?？梢远x三角形上各種各樣的權(quán)函數(shù)ω

。例如：定義

ω(△vivjvk)=|vivj|+|vivk|+|vkvj|,

其中，|vivj|是點vi到vj的歐氏距離。相應于此權(quán)函數(shù)的最優(yōu)三角剖分即為最小弦長三角剖分。注意：解決此問題的算法必須適用于任意的權(quán)函數(shù)。盡管凸多邊形的最優(yōu)三角剖分問題是一個計算幾何學問題，但在本質(zhì)上，它與矩陣連乘積的最優(yōu)計算次序問題極為相似，用動態(tài)規(guī)劃算法也能有效地求解。凸多邊形的三角剖分與表達式的完全加括號方式之間具有十分緊密的聯(lián)系。正如所看到過的，矩陣連乘積的最優(yōu)計算次序問題等價于矩陣鏈的完全加括號方式。這些問題之間的相關性可從它們所對應的完全二叉樹的同構(gòu)性看出。這里的所謂完全二叉樹是指葉結(jié)點以外的所有結(jié)點的度數(shù)都為2的二叉樹(注意與滿二叉樹和近似滿二叉樹的區(qū)別)。一個表達式的完全加括號方式對應于一棵完全二叉樹，人們稱這棵二叉樹為表達式的語法樹。例如，與完全加括號的矩陣連乘積((A1(A2A3))(A4(A5A6)))相對應的語法樹如圖2(a)所示。3.5.2三角剖分的結(jié)構(gòu)及其相關問題圖2表達式語法樹與三角剖分的對應((A1(A2A3))(A4(A5A6)))語法樹中每一個葉子表示表達式中一個原子。在語法樹中，若一結(jié)點有一個表示表達式E1的左子樹，以及一個表示表達式Er的右子樹，則以該結(jié)點為根的子樹表示表達式(E1Er)。因此，有n個原子的完全加括號表達式對應于唯一的一棵有n個葉結(jié)點的語法樹，反之亦然。凸多邊形<v0

,v1

,…

,vn-1>的三角剖分也可以用語法樹來表示。例如，圖1(a)中凸多邊形的三角剖分可用圖2(b)所示的語法樹來表示。該語法樹的根結(jié)點為邊v0v6，三角剖分中的弦組成其余的內(nèi)部結(jié)點。多邊形中除v0v6邊外的每一條邊是語法樹的一個葉結(jié)點。樹根v0v6是三角形v0v3v6的一條邊，該三角形將原多邊形分為3個部分：三角形v0v3v6，凸多邊形<v

0

,v1

,…

,v3>和凸多邊形<v3

,v4

,…

,v6>。三角形v0v3v6的另外兩條邊，即弦v3v6和v0v3為根的兩個兒子。以它們?yōu)楦淖訕浞謩e表示凸多邊形<v0

,v1

,…,v3>和凸多邊形<v3

,v4

,…,v6>的三角剖在一般情況下，一個凸n邊形的三角剖分對應于一棵有n-1個葉子的語法樹。反之，也可根據(jù)一棵有n-1個葉子的語法樹產(chǎn)生相應的一個凸n邊形的三角剖分。也就是說，凸n邊形的三角剖分與n-1個葉子的語法樹之間存在一一對應關系。由于n個矩陣的完全加括號乘積與n個葉子的語法樹之間存在一一對應關系，因此n個矩陣的完全加括號乘

積也與凸(n+1)邊形的三角剖分之間存在一一對應關系圖2的(a)和(b)表示出了這種對應關系，這時n=6。矩陣連乘積A1A2..A6中的每個矩陣Ai對應于凸(n+1)邊形中的一條邊vi-1vi。三角剖分中的一條弦vivj，i<j，對應于矩陣連乘積A[i+1:j]。事實上，矩陣連乘積的最優(yōu)計算次序問題是凸多邊形最優(yōu)三角剖分問題的一個特殊情形。

對于給定的矩陣鏈A1A2..An，定義一個與之相應的凸(n+1)邊形P=<v0

,v1

,…,vn>，使得矩陣Ai與凸多邊形的邊vi-1vi一一對應。若矩陣Ai的維數(shù)為pi-1×pi,i=1,2,…,n，則定義三形vivjvk上的權(quán)函數(shù)值為：ω(△vivjvk)=pipjpk。依此權(quán)函數(shù)的定義，凸多邊形P的最優(yōu)三角剖分所對應的語法樹給出矩陣鏈A1A2..An的最優(yōu)完全加括號方式?！ね苟噙呅蔚淖顑?yōu)三角剖分問題有最優(yōu)子結(jié)構(gòu)性質(zhì)?！な聦嵣?，若凸(n+1)邊形P=<v0

,v1

,…,vn>的一個最優(yōu)三角剖分T包含三角形v0vkvn，1≤k≤n-1，則T的權(quán)為3個部分權(quán)的和，即三角形v0vkvn的權(quán)，子多邊形<v0

,v1

,…,vk>的權(quán)和<vk

,vk+1

,…,vn>的權(quán)之和?！た梢詳嘌杂蒚所確定的這兩個子多邊形的三角剖分也是最優(yōu)的，因為若有<v0

,v1

,…,vk>或<vk

,vk+1

,…vn>的更小權(quán)的三角剖分，將會導致T不是最優(yōu)三角剖分的矛盾。3.5.3最優(yōu)子結(jié)構(gòu)性質(zhì)首先，定義t[i,j]，1≤i<j≤n，為凸子多邊形<vi-1

,vi

,…,vj>的最優(yōu)三角剖分所對應的權(quán)值，即最優(yōu)值。為方便起見，設退化的多邊形<Vi-1

,vi>具有權(quán)值0。據(jù)此定義，要計算的凸(n+1)邊多邊形P對應的權(quán)的最優(yōu)值為t[1,n]。t[i,j]的值可以利用最優(yōu)子結(jié)構(gòu)性質(zhì)遞歸地計算。由于退化的2頂點多邊形的權(quán)值為0，所以t[i,i]=0，i=1,2,…,n。當j一i≥1時，子多邊形<vi-1,vi,…,vj>至少有3個頂點。由最優(yōu)于結(jié)構(gòu)性質(zhì),t[i,j]的值應為t[i,k]的值加上

t[k+1,j]的值，再加上△vi-1vkvj的權(quán)值，并在i≤k≤j-1的范圍內(nèi)取最小。3.5.4最優(yōu)三角剖分對應的權(quán)的遞歸結(jié)構(gòu)t[i,j]可遞歸地定義為：

將上式與矩陣連乘積的最優(yōu)計算次序問題中計算m[i,j]的(2.l進行比較容易看出，除了權(quán)函數(shù)的定義外，兩個遞歸式是完全一樣的。因此只要對計算m[i,j]的算法MatrixChain做很小的修改就完全適用于計算t[i,j]。下面描述的計算凸(n+1)邊形P=<v0

,v1

,…,vn>的三角剖分最優(yōu)值的動態(tài)規(guī)劃算法Minweigh_triangulation，輸入是凸多邊形P=<v0

,v1

,…,vn>的權(quán)函數(shù)ω，輸出是最優(yōu)值t[i,j]和使得t[i,k]+t[k+1,j]+ω(△vi-1vkvj)達到最優(yōu)的位置(k=)s[i,j]，n。與MatrixChain一樣，算法Minweigh_triangulation占用θ(n2)耗時θ(n3)。3.5.5計算最優(yōu)值

凸n+1邊形P={v0,v1,...,vn}的最優(yōu)三角剖分動態(tài)規(guī)劃算法Minweigh_tri：void

MinWT(int

n,

type

**t,

int

**s){for

(int

i=1;i<=n;i++)

t[i][i]=0;for

(int

r=2;i<=n;r++){int

j=i+r-1;t[i][j]=t[i][i]+t[i+1][j]+w(i-1,i,j);s[i][j]=i;for

(int

k=i+1;k<j;k++){int

u=t[i][k]+t[k+1][j]+w(i-1,k,j);if

(u<t[i][j]){t[i][j]=u;s[i][j]=k;}}}}復雜性：T(n)=O(n3)S(n)=O(n2)3.5.6

構(gòu)造最優(yōu)三角剖分

思考：如何構(gòu)