平面點(diǎn)的曼哈頓最小生成樹

平面點(diǎn)的曼哈頓最小生成樹

ID:10252505

大?。?5.00 KB

頁數(shù):9頁

時(shí)間:2018-06-13

平面點(diǎn)的曼哈頓最小生成樹_第1頁
平面點(diǎn)的曼哈頓最小生成樹_第2頁
平面點(diǎn)的曼哈頓最小生成樹_第3頁
平面點(diǎn)的曼哈頓最小生成樹_第4頁
平面點(diǎn)的曼哈頓最小生成樹_第5頁
資源描述:

《平面點(diǎn)的曼哈頓最小生成樹》由會(huì)員上傳分享,免費(fèi)在線閱讀,更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、平面點(diǎn)的曼哈頓最小生成樹引言作者閱讀并研究了由HaiZhou(ElectricalandComputerEngineering,NorthwesternUniversity,Evanston,IL60208,USA),NarendraShenoy和WilliamNicholls(AdvancedTechnologyGroup,Synopsys,Inc.,MountainView,CA94043,USA)撰寫的論文《EfficientminimumspanningtreeconstructionwithoutDe

2、launaytriangulation》,現(xiàn)將一些收獲體會(huì)總結(jié)如下。?問題描述平面上有n個(gè)不重合的點(diǎn),你的任務(wù)是求這些點(diǎn)的最小生成樹。兩個(gè)點(diǎn)(x0,y0)和(x1,y1)之間的距離定義為

3、x0-x1

4、+

5、y0-y1

6、。(即曼哈頓距離)如果在任意兩個(gè)點(diǎn)之間都連一條邊,邊的權(quán)值等于兩點(diǎn)的曼哈頓距離,那么這個(gè)題目就是標(biāo)準(zhǔn)的最小生成樹問題。一個(gè)包含n個(gè)點(diǎn)n2條邊的圖,求最小生成樹的代價(jià)是O(n2)。但是這種一般性的做法沒有考慮到“平面”的性質(zhì)。下面將通過分析最小生成樹的性質(zhì)和平面性質(zhì)的結(jié)合,得到一個(gè)O(nlogn)的算

7、法。?最小生成樹的“環(huán)切”性質(zhì)先拋開“平面”,我們考慮一般的離散圖的最小生成樹有什么性質(zhì)。環(huán)切性質(zhì)在圖G=(V,E)中,如果存在一個(gè)環(huán),把環(huán)中權(quán)最大的邊e刪除得到圖G’=(V,E{e})(如果有多條最大邊,則刪除任意一條),則G和G’的最小生成樹權(quán)和相同。證明:假設(shè)e(e∈E)在G的一個(gè)環(huán)C上,并且是環(huán)上的權(quán)最大邊。假設(shè)G的某棵最小生成樹T包含了e,考慮e連接的兩個(gè)點(diǎn)u和v。把e從T中刪除,就把T分成兩個(gè)連通分量,u,v分處不同的連通分量。在環(huán)C上對(duì)應(yīng)的把e刪除,從u到v還是有一條通路,并且通路上的所有邊權(quán)值

8、都不大于e的權(quán)值;假設(shè)這條通路是(u,x1,x2,…,xL,v)。在點(diǎn)集S={u,x1,x2,…,xL,v}中,和u屬于同一個(gè)集合的點(diǎn)稱之為紅點(diǎn),和v屬于同一個(gè)集合的稱之為藍(lán)點(diǎn)。顯然S中至少有一個(gè)紅點(diǎn)(u)、至少有一個(gè)藍(lán)點(diǎn)(v)。所以在序列(u,x1,x2,…,xL,v)中必然存在相鄰的兩個(gè)點(diǎn)顏色不同,不妨設(shè)為a和b。將加入到被刪除了e的T中,就得到了一棵新的生成樹T’:即T’=(T{e})∪{}。前面提到了通路(u,x1,x2,…,xL,v)中任意一條邊都不大于e,所以的權(quán)不大

9、于e的權(quán)。即T’也是G的一棵最小生成樹。因?yàn)镚’是G的子圖,所以T’也是G’的最小生成樹。而T和T’的權(quán)和相等(都是G的最小生成樹)。證畢。?區(qū)域分類法通過最小生成樹的“環(huán)切”性質(zhì),我們可以發(fā)現(xiàn)有很多邊是沒有用的。如果圖中存在一個(gè)環(huán),那么就至少能刪掉一條邊而保持最小生成樹不變。我們回到“平面”問題?;舅悸愤€是構(gòu)建一個(gè)離散圖——但是這個(gè)圖的邊數(shù)必須遠(yuǎn)遠(yuǎn)小于n2。換句話說我們要想辦法利用“環(huán)切”性質(zhì),只保留一些有用的邊。考察某個(gè)點(diǎn)s。我們從s發(fā)出8條射線將平面均分成八個(gè)部分:如果點(diǎn)落在射線上,按如下方法劃分:實(shí)線

10、上的點(diǎn)屬于這個(gè)區(qū)域、虛線上的點(diǎn)不屬于。上圖中p,q都屬于該區(qū)域。下面我們證明:在每個(gè)區(qū)域里面,s只要和至多一個(gè)點(diǎn)連邊即可。八個(gè)扇形區(qū)域是對(duì)稱的,我們只考慮R1。把s看作原點(diǎn),R1里面的點(diǎn)(x,y)都滿足:x≥0,y>x.考察R1里面兩個(gè)點(diǎn)p和q,不失一般性設(shè)xp≤xq。1.??????yp≤yq

11、PQ

12、=xq+yq-(xp+xq)

13、SP

14、=xp+yp

15、SQ

16、=xq+yq所以

17、PQ

18、=

19、SQ

20、-

21、SP

22、≤

23、SQ

24、可見當(dāng)yp≤yq時(shí),

25、PQ

26、不是三角形SPQ的最長(zhǎng)邊。(在曼哈頓距離下的“最長(zhǎng)”)2.??????yp

27、>yq0≤xp≤xq≤yq

28、PQ

29、=xq-xp+yp-yq

30、SP

31、=xp+yp

32、SQ

33、=xq+yq即

34、PQ

35、=(yp-xp)+(xq-yq)因?yàn)閤q≤yq,所以

36、PQ

37、≤yp-xp≤yp≤xp+yp=

38、SP

39、也就是說,當(dāng)yp>yq時(shí),

40、PQ

41、仍然不是三角形SPQ的最長(zhǎng)邊。(曼哈頓距離意義下的“最長(zhǎng)”)綜上,

42、PQ

43、無論如何也不可能是三角形SPQ的最長(zhǎng)邊。即:在環(huán)中,最大邊只可能是

44、SP

45、和

46、SQ

47、。根據(jù)“環(huán)切”性質(zhì),我們把

48、SP

49、和

50、SQ

51、中的較長(zhǎng)邊刪除即可。假設(shè)R1里面有m個(gè)頂點(diǎn):P1,

52、P2,…,Pm,假設(shè)距離s最近的點(diǎn)是Pk,那么只要在S和Pk之間連邊即可。所謂距離s最近的點(diǎn),實(shí)際上就是xk+yk最小的點(diǎn)。?圖的構(gòu)建方法按照上一節(jié)介紹的方法,我們可以構(gòu)建出一個(gè)至多含有8n條邊的圖??墒侨绾螛?gòu)造呢?如果對(duì)于每個(gè)點(diǎn)s,把所有的點(diǎn)都判斷一次取最小值,那么復(fù)雜度是O(n2),沒有任何意義。下面我們考慮設(shè)計(jì)一個(gè)高效的算法,實(shí)現(xiàn)“找到每個(gè)點(diǎn)的R1區(qū)域內(nèi),離其最近的點(diǎn)”的操作。找

當(dāng)前文檔最多預(yù)覽五頁,下載文檔查看全文

此文檔下載收益歸作者所有

當(dāng)前文檔最多預(yù)覽五頁,下載文檔查看全文
溫馨提示:
1. 部分包含數(shù)學(xué)公式或PPT動(dòng)畫的文件,查看預(yù)覽時(shí)可能會(huì)顯示錯(cuò)亂或異常,文件下載后無此問題,請(qǐng)放心下載。
2. 本文檔由用戶上傳,版權(quán)歸屬用戶,天天文庫負(fù)責(zé)整理代發(fā)布。如果您對(duì)本文檔版權(quán)有爭(zhēng)議請(qǐng)及時(shí)聯(lián)系客服。
3. 下載前請(qǐng)仔細(xì)閱讀文檔內(nèi)容,確認(rèn)文檔內(nèi)容符合您的需求后進(jìn)行下載,若出現(xiàn)內(nèi)容與標(biāo)題不符可向本站投訴處理。
4. 下載文檔時(shí)可能由于網(wǎng)絡(luò)波動(dòng)等原因無法下載或下載錯(cuò)誤,付費(fèi)完成后未能成功下載的用戶請(qǐng)聯(lián)系客服處理。